Problem 044

[JPGargoyle]

Thank you very much both
(and for your quick answers)

Now I know what to go after


Best regards

[userProjectEuler]

missing word: smallest pair in the problem text. The word is present in the list of problems, but not in the the text:
Find the pair of pentagonal numbers, ...

My (horrible) solution took 29 seconds. xD. But now I'm able to see how to do it the right way.

This site is GREAT. =D

edited: I just add a break when find the answer and it took <= 1s.

[daniel.is.fischer]

Actually, the text has been changed to what it is now because of complaints about the ambiguity of "smallest pair", so it was made "and D = |P_k − P_j| is minimised" to disambiguate.

[elendiastarman]

EDIT: Found a baaaaad bug in my code...I wasn't dividing by 2.
EDIT2: Yup. Solved it.

*sigh* My code only gives one solution, not matter how long I run it, yet it's not the right answer. My question is, is the difference between the indices of the two pentagonal numbers 19?

[rayfil]

is the difference between the indices of the two pentagonal numbers 19?

NO

[ccarr]

I used a similar method and got the correct answer, although it was awful slow. I still think it's the only way to ensure that the difference is minimized (many used faster algorithms that did not really minimize D, but nevertheless got the solution).

I used a method that I think guarantees that the first solution found is the one with minimal |P_j - P_k| using the fact that P_n+P_n+1 = 3n² + 2n + 1. As you go through P_n+P_n+2, P_n+P_n+3, ..., P_n+P_n+x, the equations evolve in a constant fashion. The only difficulty is determining what value of "x" is adequate to either accept or reject P_n as the lesser value of the desired pair [P_j, P_k]. I arbitrarily chose 1000, which resulted in an answer within 200ms, but I wonder if there is a more certain way?

[Cerno]

For completeness's sake it should be mentioned that the real optimal solution to this problem is trivial:

Expand

P₁-P₀ = 1-0 = 1 = P₁
P₁+P₀ = 1+0 = 1 = P₁

I spent the better part of the day figuring out problem 044 and wondered why my code did not converge until I realized that my function to test for pentagonal numbers was severely flawed:

• Compute the inverse P^-1of P
• test int(P^-1) == P^-1.

Really kind of embarrassing (floating point representation FTW)

[sstein]

I only solved this problem today but I'm really not happy with my solution.

It arrives at the correct number, but I had to guess at the upper limit for generating pentagonal numbers. How do you know that the correct D is actually minimised ?

I can't help but feel I just got lucky on this one.

[GenePeer]

Don't remember how I solved this at first, so I've been thinking about this for a while, and this is my best way to be sure no better solution exists. I hope this isn't revealing too much.

Once you've found a "minimal pair" (i,j), $D=P_{j}-P_{i}$, then you shouldn't check further than $m=\lfloor\frac{D+2}{3}\rfloor$. Checking any pairs (k,l), for l>m will always produce differences greater than D. So the upper-limit, m, is updated as smaller D's are found. This will give the program O(D²) running time. Knowing how large our current D is though, the program could take around 16hrs to finish. If a smaller D exists, we will find it.

edit: More deductions can be made to reduce the running time, but that would be spoiling the problem. I'll try and run this to see how quick it would be.

edit 2: The required D found in 0.5s, "certainty achieved" in 3s.

[xe3tec]

this problem rly makes me feel stupid
It never took me more than 4h to solve a problem, but this time I hv no more good ideas

A question: U hv to precalculate all pentagonal numbers till a certain limit, dont u?
And then u hav to checke "all" possible sums and differences between the numbers...
but this takes just too much time.

so could sb plz gimme a hint?

[Lord_Farin]

I am not inclined to give you a hint just because you haven't solved it fast enough to your liking. I remember being stuck on this problem for weeks and weeks before finally solving it.

Also, I think we (the forum members) would all (or at least mostly) greatly appreciate it if you at least tried to use correct English (as I can see you are capable of doing so), and not use excessive abbreviations. Thanks in advance.

[xe3tec]

You are absolutely right. I am deeply sorry. Seriously!

You said it took you weeks? I won't sleep if I can't solve it...I guess it's a long night again

edit 10min later:
Congratulations, the answer you gave to problem 44 is correct.

I had it right in the beginning, just optimized something. Easssy

[Lord_Farin]

It indeed took me weeks to realise that there was not an amazingly beautiful solution, and that using Java instead of Mathematica would yield the required iteration power

[xe3tec]

Yes, I also searched for a better solution but I had no idea. At the end it was 7 lines of python code which took 0,996sec. I think its fast enough.

[Francky]

I'm proud of the solution I've found for this problem particulary (the hard version, without bounds !)
Result in 2 second with Python.
Where can I share this solution ?
------

It's my first post, so :
I'm a math teacher in France, with a poor english.
I learned a little Turbo Pascal before my baccalauréat. After only "pure" math.
Now, I rediscover programmation with Python, I like it.
Your site is wonderfull. Thanks for all.
I've translated in french the first 50 problems and I've searched pretty solutions,
I wish this work will help french student to come here.

[xe3tec]

Not here. Maybe on your Blog or Website if you have one (like I do).
But you got a PM.

[Francky]

I did the real chalenge (|Pj-Pk| minimised, not the sum)
with no bounds, a priori.
--
Find D took 0.95 s
The second D in the list is
?--?8562 (only last digits), and took me 555 s of Python.

[GenePeer]

Not here. Maybe on your Blog or Website if you have one (like I do).

That's not a good idea as your Blog or Website is open to public.

I did the real chalenge (|Pj-Pk| minimised, not the sum)
with no bounds, a priori.
--
Find D took 0.95 s
The second D in the list is
?--?8562 (only last digits), and took me 555 s of Python.

You can PM me your solution, I'm not an admin but just interested in discussing the problem. I also solved it with no bounds, a priori.

[thedoctar]

Hey, I've just solved the problem, and it took me 1.5 seconds in Python to find the correct solution, though I only guessed the upper limit. Is there any way to mathematically obtain a limit for D? I thought that if P(n+1)-P(n)> Minimum obtained value of D, then you could stop searching, but it takes too long, I think.

[Francky]

There's others solutions, so...
A good algorithm proove that the solution is THE solution, without any bounds !
Mine does the job in 0.96s of uncompiled Python.
The second solution is reached in 555s.