2015-09-08

# Problem 078: Coin partitions

Description:

Let `p(n)` represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so `p(5)=7`.

``````OOOOO
OOOO   O
OOO    OO
OOO    O   O
OO     OO  O
OO     O   O  O
O      O   O  O  O``````

Find the least value of n for which p(n) is divisible by one million.

Solution:
vXX OOO
# ... #
. . . .
.  .  .
. . . .
# ... #

>\$.@
v+1p+1/g01\+1%g01:g04_^#:%g02g05\$\$              <
>"}}@"**20p"~|"+10p111p1>:40p050p0>:60p::2/1+:*3*\:2/1+\2%2*1-*+2/:40g`#^_4 v
^+1p05-\g05*-1*2%2/2g06g+1/g01\+1%g01:-\g0<
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Again the algorithm is from MathBlog. I can't really say that I understand the algorithm fully (and the MathBlog guy says he neither).

But for the best explanation you better read his article.

 Interpreter steps: 1 191 633 332 Execution time (BefunExec): 2min 50s (6.97 MHz) Program size: 251 x 256 Solution: 55374 Solved at: 2015-09-08

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript