Problem 078
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Problem 078
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.
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.
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 11:15 pm
 Location: Bremen, Germany
Re: Problem 78
There is a recursive algorithm using only one parameter.
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: Problem 78
Thanks! I'll think it! :)
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"
Re: Problem 078
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...
I know its stupid, but I can't get my head around a partition number like that...
Re: Problem 078
The number is a really HUGE number.enderw88 wrote: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...
Entia non sunt multiplicanda praeter necessitatem
Re: Problem 078
Finally solved it, and yes it was a ridiculously large number.Francky wrote: The number is a really HUGE number.
Re: Problem 078
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?
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?
Re: Problem 078
It is evenly divide by a million, i.e. p(n) % 1000000 == 0.tijko wrote: ...
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?
Last edited by mpiotte on Fri May 17, 2013 1:07 pm, edited 1 time in total.

 Posts: 27
 Joined: Mon Aug 22, 2011 11:20 am
Re: Problem 078
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?
Does "ridiculously big" mean bigger than long long? Do I need to break out BigInteger?
Re: Problem 078
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.
Problem 78: Mathematical Background
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?
Re: Problem 78: Mathematical Background
1) Please don't create a new topic for a problem when one already exists.alxcoh wrote: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?
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.

 Posts: 55
 Joined: Thu Mar 29, 2012 12:55 pm
 Location: Sweden
Re: Problem 78: Mathematical Background
For this problem you don't have to look up anything. There is a simple solution without difficult math.alxcoh wrote: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.
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 < my friend key

 Posts: 5
 Joined: Fri Jun 19, 2015 2:50 pm
Re: Problem 078
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.
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.
Re: Problem 078
It looks like you calculated a floating point number. For divisibility checks this won't work.
(Actually p(234)=65851585970275)
(Actually p(234)=65851585970275)
Re: Problem 078
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
Re: Problem 078
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
Tom