Problem 078

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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 post any spoilers
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

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.
"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&egrave;tes sont l&agrave;.
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

Re: Problem 78

Thanks! I'll think it! :)
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

enderw88
Posts: 9
Joined: Tue Feb 07, 2012 4:18 am

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...
Francky
Posts: 90
Joined: Sat May 07, 2011 3:49 pm
Location: South of France

Re: Problem 078

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...
The number is a really HUGE number.
Entia non sunt multiplicanda praeter necessitatem
enderw88
Posts: 9
Joined: Tue Feb 07, 2012 4:18 am

Re: Problem 078

Francky wrote: The number is a really HUGE number.
Finally solved it, and yes it was a ridiculously large number.
tijko
Posts: 6
Joined: Sun Jun 17, 2012 11:59 pm

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?
mpiotte
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm

Re: Problem 078

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?
It is evenly divide by a million, i.e. p(n) % 1000000 == 0.
Last edited by mpiotte on Fri May 17, 2013 1:07 pm, edited 1 time in total.
Fogmeister
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?
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

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.
alxcoh
Posts: 1
Joined: Mon Dec 29, 2014 3:31 am

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?
mpiotte
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm

Re: Problem 78: Mathematical Background

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?
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
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

Re: Problem 78: Mathematical Background

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.
For this problem you don't have to look up anything. There is a simple solution without difficult math.

320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key
srinathmkce
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.
hk
Posts: 11122
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 078

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

(Actually p(234)=65851585970275)
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

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
dawghaus4
Posts: 56
Joined: Fri Nov 29, 2013 2:22 am

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