Coin partitions


Fork me on GitHub
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