Coin partitions

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<

Download

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