Problem 044

[frogjg2003]

I saw that a lot of people said that simply finding the first pair is the correct answer, so I created a code that does that, took 5 1/2 seconds. I then spent a few days trying to come up with a code that proves it's the minimal solution. I'm pretty sure I have it (gives the right answer) but it takes about an hour to run. Can some of you look at my code and give me some optimization tips? I really don't want to move on to the next problem until I completely understand this one.

EDIT: If the optimization is to find the first pair, and then just test all pairs less than that, then I haven't tried that yet, but I'll probably tomorrow.

[thundre]

Can some of you look at my code and give me some optimization tips?

After you enter the correct answer, you can go to http://projecteuler.net/index.php?section=forum&id=44 to see dozens of example programs that solve it quickly. Since those perform better than yours, the burden of reading code and comparing algorithms should be on you.

[JMW1994]

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk Pj| is minimised; what is the value of D?

Does the problem mean to take the two pentagonal numbers that you're adding and subtracting to or does it mean to take the result of Pj from the sum of the two pentagonal numbers and the result of Pk of the difference of two pentagonal numbers and subtract it from there and take the absolute value of it? If I'm wrong on either, can you tell exactly what the problem is asking for?

Thanks.

[PurpleBlu3s]

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk Pj| is minimised; what is the value of D?

Does the problem mean to take the two pentagonal numbers that you're adding and subtracting to or does it mean to take the result of Pj from the sum of the two pentagonal numbers and the result of Pk of the difference of two pentagonal numbers and subtract it from there and take the absolute value of it? If I'm wrong on either, can you tell exactly what the problem is asking for?

Thanks.

The difference of the two pentagonal numbers is what you should submit.

[JMW1994]

The difference of the two pentagonal numbers is what you should submit.

You don't take the sum and difference and then subtracting those value? For example, you don't mean this: (1247+715)-(1247-715), but rather: (1247-715) as long as the pentagonal numbers add up to another pentagonal number and the subtraction of the pentagonal numbers subtract to another pentagonal number? In addition, the result is supposed to be in the millions because 1) everyone tends to hit that and 2) I'm hitting the result only in a thousand, correct?

I'm only asking to verify.

[Francky]

Can some of you look at my code and give me some optimization tips?

After you enter the correct answer, you can go to http://projecteuler.net/index.php?section=forum&id=44 to see dozens of example programs that solve it quickly. Since those perform better than yours, the burden of reading code and comparing algorithms should be on you.

frogjg2003 is right, none in the first pages of the forum thread proove that D is the minimum !!!
It's a coincidence that the answer is correct for all those submissions.

I propose page 5 of this thread, a correct solution that proove D is THE minimum, in less than a second, the second solution is 3215928562 (much longer time machine).
I never wrote a math paper in english, so if someone could help me to translate it in a correct english, it would be kind for all non-french readers. Thanks.

--
I think the problem has been modified in the early times, and in the begining it wasn't ask for D minimum, but now it is ! (Euler said, it's a much much harder problem, but with the same answer).

[PurpleBlu3s]

The difference of the two pentagonal numbers is what you should submit.

You don't take the sum and difference and then subtracting those value? For example, you don't mean this: (1247+715)-(1247-715), but rather: (1247-715) as long as the pentagonal numbers add up to another pentagonal number and the subtraction of the pentagonal numbers subtract to another pentagonal number? In addition, the result is supposed to be in the millions because 1) everyone tends to hit that and 2) I'm hitting the result only in a thousand, correct?

I'm only asking to verify.

You have to find two pentagonal numbers, P_j and P_k, such that their sum and their difference are both pentagonal numbers as well. So if you look at the example of P₄ and P₇, 22 and 70, imagine that their difference was in fact pentagonal, then you would submit as your answer, 70 - 22 = 48.

[JMW1994]

It appears that these weren't answered.

In addition, the result is supposed to be in the millions because 1) everyone tends to hit that and 2) I'm hitting the result only in a thousand, correct?

Thanks.

[TripleM]

I'm not sure what you mean by you're hitting the result in the thousands, but if you have come up with an answer and it isn't being accepted, then it won't be the correct answer. There's no limit on how large the correct answer is.

[monkey68pl]

Hello everyone. I've been stuck with this problem for couple of days, and I'm wondering if I'm doing it correctly. Now, my solution takes a lot of time (for now, about 36 hours and still searching for solution) - and I'm not sure that I wrote it correctly, since I cannot check it as other problems (where answers for 'small probems' are given). Is anyone willing to recieve a PM from me, and tell me if I'm doing it correctly? I don't know if you allow it - but some hint about upper bound for which I should calculate would be great.

For me - the most difficult problem so far, due to my complete lack of ideas how to optimize my algorithm.

Best regards,

K.

[Svartskägg]

Now, my solution takes a lot of time (for now, about 36 hours and still searching for solution)

My solution takes 35 milliseconds, so you are obviously not doing it correctly.

[nicolas.patrois]

Mine takes a few seconds but my processors are already busy.

[monkey68pl]

I know that I'm wrong, yet I think that I used correct method. This means that I have some huge mistake in my program (which is possible, since I'm not programmer, at least in Python) or my method is completely wrong - but I can't think of anything better. I think that I'll find solution, and then I'll check how other people solved this - but this is similiar to just looking up the answer in google, which I want to avoid. So I thought that maybe someone can guide me to correct solution.

Is there any information about pentagonal numbers that would help me? I looked in the net, did some calculations on paper, but I havent found anything useful for this problem.

[TripleM]

If you want to PM me your program, plus a description of what it does and why you think this should solve the problem, I can try to help.

[solarmew]

sooooooo........ negative "n" don't count then?

[Georg]

n has to be a natural Number.

[Math_Max]

Hi everybody,

I was solving problem 44 just now, and again I came across this issue which I don't really understand how to approach.

Here's the problem:
Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

I approach the problem the brute-force way which I think works for most of the problems on page1. So I made some for loops, but what I don't understand is this. How do you know at what number you can stop looking. For instance how do you know that there doesn't exist a pair of Pentagonal numbers with a million digits which would be the answer. Obviously, this would take infinite time to calculate, but how would you know?

[mpiotte]

...I approach the problem the brute-force way which I think works for most of the problems on page1. So I made some for loops, but what I don't understand is this. How do you know at what number you can stop looking. For instance how do you know that there doesn't exist a pair of Pentagonal numbers with a million digits which would be the answer. Obviously, this would take infinite time to calculate, but how would you know?

Let's assume you found a pair (P_j, P_k) of pentagonal numbers that satisfy the problem statement.
Look at the difference between consecutive pentagonal numbers P_n+1 - P_n. As n grows larger, so does P_n+1 - P_n. There must be a value of n for which P_n+1 - P_n ≥ |P_j - P_k|. Thus, if there is a pair of pentagonal numbers with a smaller difference, it must occur at or before P_n, and P_n is an upper bound of the search space. This proves the search space is not infinite.

[Math_Max]

Let's assume you found a pair (P_j, P_k) of pentagonal numbers that satisfy the problem statement.
Look at the difference between consecutive pentagonal numbers P_n+1 - P_n. As n grows larger, so does P_n+1 - P_n. There must be a value of n for which P_n+1 - P_n ≥ |P_j - P_k|. Thus, if there is a pair of pentagonal numbers with a smaller difference, it must occur at or before P_n, and P_n is an upper bound of the search space. This proves the search space is not infinite.

Thanks dude, had to think for a minute but I understand it now . So in a sense you have add something to your program that limits the search space everytime you find a solution?

[hk]

Moved to the relevant forum and topic.