Partitions

I've been thinking about partions off and on lately. If the term sounds familiar, it was at the center of the movie The Man Who Knew Infinity.

If you didn't see the movie, it is the number of ways you can break down an integer into other integers of lesser or equal size. For example, let's say a blackjack dealer has chips in denominations from $1 to $5. You ask to break down a $5 chip and she asks "how?" How many ways can it be done?

The answer is 7:

1-1-1-1-1
2-1-1-1
2-2-1
3-1-1
3-2
4-1
5

Granted, getting another $5 chip back isn't breaking it down, but to be consistent, it counts as a partition.

I wrote both a spreadsheet and a program to get at answers for large numbers. Here they are for 1 to 405. At 406, I exceed the size of a 64-bit unsigned integer.



I'll put my code in spoiler tags, if anyone wants to tackle this as a programming exercise.



All that said, I'm not sure what my question is. Has anyone else messed with this? Please don't just plop in a Numberfile video and call it a day, let's try to have a discussion.

One of the mysteries of mathematics is a simple formula to the number of partitions of x, that doesn't just sum partitions of smaller numbers (as I did). As the movie I linked to goes into, Srinivasa Ramanujan found some relationships between a number and its number of partitions.

The question for the poll is how do you feel about partitions?

A similar concept is sometimes used as an interview question for software development roles. "Given standard USA coins, write a function that will take a dollar amount and return the number of different ways you can make that dollar amount in coins." I think I tried to solve it with recursion, but iteration would work too. Your function is also printing out the combinations which wasn't a requirement the one time I was asked this.

Because I hate interviewing, I don't feel good about partitions :P

I've been working on math behind the Grand Jackpot for the Lightning Link / Dragon Link games and I had to research and use partitions in that. Crazy that you mention it right now, because I'm about ready to share my work if anyone is interested.

Not sure how helpful this is, but here is a link to an article on Discovery.com that indicates something is there waiting to be described.

Quote: rsactuary

I'm about ready to share my work if anyone is interested.

I'm interested.

PM me an email address? We might need to get on the phone for me to walk you through it. It's a LOT of math.

Quote: Wizard

I'm interested.

I would also be interested.

I have recently been doing some analytical/theoretical work on partitions, although going in a completely different direction than you have. I'm writing it up in a way suitable for WOV and I'll try to post some of it in a day or two and hope for some feedback.

Quote: tringlomane

I would also be interested.

Let me run it by Wiz and see what he thinks. I stress that it is strictly a theoretical exercise as there are too many unknowns without the PAR sheets to be able to apply it.

I noticed the total number of partitions is often prime or primey* . Just look at the first five total partitions: 2,3,5,7,11.

That caused me to factor the number of partitions to see how primey they were.



* To coin my own term, meaning to have rather few factors, compared to the size of the number. Is there a more technical term for this, and please don't say "relatively prime."