Problem 078

[axelbrz]

Hi, I built a recursive function with 2 parameters. Both are below N where N is the number of coins that I want to test for the ways to separate those coins into piles.

So I have a squared matrix to memorize the recursive function, but when N = 15,000 I'm using 800 MB (4 bytes per element) and the memory is full.

I want to know if my algorithm is not working because the N has to be below to 15,000, or if exists another recursive algorithm with only one parameter (so I will be able to calculate more values of N), or if exists a closed formula to get the ways to separate those coins into different piles, because I really don't know how can I resolve this problem for N > 15,000 when I have a squared matrix that uses 800 MB for N < 15,000.

Thanks,

Axel.

[daniel.is.fischer]

There is a recursive algorithm using only one parameter.

[axelbrz]

Thanks! I'll think it! :)

[enderw88]

Just so I am not beating a really wrong bush, the problem statement "Find the least value of n for which p(n) is divisible by one million." really means that there is a p(n) = k x 10^6, where k is a (potentially large) integer...

I know its stupid, but I can't get my head around a partition number like that...

[Francky]

Just so I am not beating a really wrong bush, the problem statement "Find the least value of n for which p(n) is divisible by one million." really means that there is a p(n) = k x 10^6, where k is a (potentially large) integer...

I know its stupid, but I can't get my head around a partition number like that...

The number is a really HUGE number.

[enderw88]

The number is a really HUGE number.

Finally solved it, and yes it was a ridiculously large number.

[tijko]

Problem 78 (View Problem)

I was hoping someone could clarify a couple of things on this problem.

"For example, five coins can separated into piles in exactly seven different ways, so p(5)=7."

Is this suppose to be "For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7."? or
"For example, five can separate into piles in exactly seven different ways, so p(5)=7."?

Probably just a small typo but, I'm not clear on what exactly the question is asking. Are we suppose to find the value n, when p(n) is at least a million p(n)/1000000 >= 1 or is evenly divide by a million, p(n) % 1000000 == 0?

[mpiotte]

...

Probably just a small typo but, I'm not clear on what exactly the question is asking. Are we suppose to find the value n, when p(n) is at least a million p(n)/1000000 >= 1 or is evenly divide by a million, p(n) % 1000000 == 0?

It is evenly divide by a million, i.e. p(n) % 1000000 == 0.

[Fogmeister]

I still need to find this "one parameter function" but just wanted to check.

Does "ridiculously big" mean bigger than long long? Do I need to break out BigInteger?

[TheEvil]

As a simple brute force could show with increasing n, the value of p(n) increases so much that it is hard to imagine, it would fit in the long long type. And it is the case, so if you would like to calculate it you will need bigger type, but it is solvable without that (as almost all of the PE problems ), with some trick.

[alxcoh]

Are you expected to do some mathematical research into certain questions? For instance I was having a lot of trouble with p78, and have heard that there is a generating function for partitions. Are we expected to look up this function, or figure it out for ourselves. Is looking it up considered cheating?

[mpiotte]

Are you expected to do some mathematical research into certain questions? For instance I was having a lot of trouble with p78, and have heard that there is a generating function for partitions. Are we expected to look up this function, or figure it out for ourselves. Is looking it up considered cheating?

1) Please don't create a new topic for a problem when one already exists.
2) Project Euler is about learning. As problems get more difficult, it is perfectly normal to study topics you may be unfamiliar with. This is not the same as looking up the answer on the Internet. You must be the judge of what constitute legitimate research as opposed to simply spoiling the problem.

[Svartskägg]

For instance I was having a lot of trouble with p78, and have heard that there is a generating function for partitions. Are we expected to look up this function, or figure it out for ourselves.

For this problem you don't have to look up anything. There is a simple solution without difficult math.

[srinathmkce]

I used python to solve this problem by generating each partition count . My code returns correct partition numbers (cross checked with https://oeis.org/A000041) . for p(100) i am getting 190569292. I did break loop once p(n) % 1000000 == 0.

i am getting answer within n = 5000. However the answer is wrong.

Am confused, i didnt compute enough N or the code is unable to hold the value p(n) in memory.

Just a random number p(234) = 6.58515859703e+13 . Can someone tell me if the result for 234 is wrong , if so i can correct the algorithm.

[hk]

It looks like you calculated a floating point number. For divisibility checks this won't work.

(Actually p(234)=65851585970275)

[S_r]

this is an irritating question for me. even after euler's hint in thread of previous problems i cannot get it. what exactly is the trick i should look for as p(1000) using only primes is large number and i dont think i can go upto many digits with six zeroes at end. what should i do

[dawghaus4]

The problem doesn't ask for p(n). You need the least n such that p(n) is divisible by 1000000; that is, you need only the last 6 digits of p(n).

Tom