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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

Problem 078

Post by 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.
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 78

Post by daniel.is.fischer »

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

Post by axelbrz »

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

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

Re: Problem 078

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

Re: Problem 078

Post by Francky »

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.
ImageEntia non sunt multiplicanda praeter necessitatem
enderw88
Posts: 9
Joined: Tue Feb 07, 2012 4:18 am

Re: Problem 078

Post by enderw88 »

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

Re: Problem 078

Post by 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?
User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm
Location: Montréal, Canada

Re: Problem 078

Post by mpiotte »

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.
Image
Fogmeister
Posts: 27
Joined: Mon Aug 22, 2011 11:20 am

Re: Problem 078

Post by 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?
Image
User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 078

Post by 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 :D), with some trick.
Image
alxcoh
Posts: 1
Joined: Mon Dec 29, 2014 3:31 am

Problem 78: Mathematical Background

Post by 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?
User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm
Location: Montréal, Canada

Re: Problem 78: Mathematical Background

Post by mpiotte »

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.
Image
Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

Re: Problem 78: Mathematical Background

Post by Svartskägg »

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.
Image
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key
srinathmkce
Posts: 5
Joined: Fri Jun 19, 2015 2:50 pm

Re: Problem 078

Post by 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.
User avatar
hk
Administrator
Posts: 11122
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 078

Post by hk »

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

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

Re: Problem 078

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

Re: Problem 078

Post by 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
Post Reply