Project Euler #372
 

I'm sure a lot people here are already familiar with Project Euler, but nevertheless, I found the latest puzzle to be quite interesting and thought I'd share it here.

It's a fairly easy one to understand, but coming up with an elegant solution was extremely hard. So hard that I in fact did not manage it, and instead took a brute force approach, albeit a very well optimised one.

For anyone that wants to have at it, here's the link:
[url]http://projecteuler.net/problem=372[/url]

Of course, there are many more problems on there that are fun too.

Project Euler is what lead me here!!!

Did you notice that you can immediately halve the size of the search space by noting that on one side of x=y, the answer is always even?

Indeedily, I made many optimisations, but when all was said and done it was still a fairly long run time. Many people in the forum for that problem (which you can only see when you have completed the problem) had code that ran much much faster because they used far cleverer methods.

Very interesting. I drew a quick graph of the solution set for R(0,500), and it's definitely a very pretty pattern.

[QUOTE=lavalamp;290358]...code that ran much much faster because they used far cleverer methods.[/QUOTE]

Among these "clever" methods, did you see by chance something ressembling to computing the following sum :

sqrt(2)-sqrt(1) + sqrt(4)-sqrt(3) + .... + sqrt(n+1)-sqrt(n) ?

And if so, do you know the name os such a serie ?
Many thanks

[QUOTE=PdB;290704]Among these "clever" methods, did you see by chance something ressembling to computing the following sum :

sqrt(2)-sqrt(1) + sqrt(4)-sqrt(3) + .... + sqrt(n+1)-sqrt(n) ?

And if so, do you know the name os such a serie ?
Many thanks[/QUOTE]

[url]http://www.wolframalpha.com/input/?i=sum+from+n%3D1+to+infinity+%28sqrt%28n%2B1%29-sqrt%28n%29%29[/url]
The sum from n=1 to m is equal to [TEX]sqrt{m+1}-1[/TEX]. I don't know if such a series has a name, but it seems an awfully roundabout way of getting that value.

[QUOTE=Mini-Geek;290746][url]http://www.wolframalpha.com/input/?i=sum+from+n%3D1+to+infinity+%28sqrt%28n%2B1%29-sqrt%28n%29%29[/url]
The sum from n=1 to m is equal to [TEX]sqrt{m+1}-1[/TEX]. I don't know if such a series has a name, but it seems an awfully roundabout way of getting that value.[/QUOTE]

that's not how I interpreted his idea:

[CODE]sum(X=2,8,sqrt(X)-sqrt(X-1);X=X+2)[/CODE]

is how I interpreted it

[CODE](16:21)>sum(X=1,6,sqrt(X)-sqrt(X-1))[/CODE] seems to be how you seem to interpret it.

[QUOTE=science_man_88;290747]that's not how I interpreted his idea:

[CODE]sum(X=2,8,sqrt(X)-sqrt(X-1);X=X+2)[/CODE]

is how I interpreted it

[CODE](16:21)>sum(X=1,6,sqrt(X)-sqrt(X-1))[/CODE] seems to be how you seem to interpret it.[/QUOTE]

Oh, you're right, I didn't notice that n went up by 2 each time. This is the corrected one: [url]http://www.wolframalpha.com/input/?i=sum+from+n%3D1+to+infinity+%28sqrt%282*n%29-sqrt%282*n-1%29%29[/url] Wolfram Alpha wasn't able to equate it to a simple equation like the other one, but it does diverge.

[QUOTE=Mini-Geek;290749]Oh, you're right, I didn't notice that n went up by 2 each time. This is the corrected one: [url]http://www.wolframalpha.com/input/?i=sum+from+n%3D1+to+infinity+%28sqrt%282*n%29-sqrt%282*n-1%29%29[/url] Wolfram Alpha wasn't able to equate it to a simple equation like the other one, but it does diverge.[/QUOTE]

[CODE](16:15)>sum(X=2,2,sqrt(X)-sqrt(X-1);X=X+2)
%112 = 4
(16:15)>sum(X=2,4,sqrt(X)-sqrt(X-1);X=X+2)
%113 = 15
(16:15)>sum(X=2,6,sqrt(X)-sqrt(X-1);X=X+2)
%114 = 30
(16:15)>sum(X=2,8,sqrt(X)-sqrt(X-1);X=X+2)
%115 = 49[/CODE]

49-30=19
30-15=15
15-4=11

second order differences:

19-15=4
15-11 = 4

second order differences are the same ( and yes I tested at least one more of these now) so it starts for x steps in 4*x^2 ... :

the second order differences of the result of subtracting 4*x^2 from each appears to be constant at -4.

There's a pastebin for this problem [url]http://pastebin.com/ZMk5jK1b[/url]

But it seems to be a very unoptimized algorithm

[QUOTE=PdB;290704]Among these "clever" methods, did you see by chance something ressembling to computing the following sum :

sqrt(2)-sqrt(1) + sqrt(4)-sqrt(3) + .... + sqrt(n+1)-sqrt(n) ?

And if so, do you know the name os such a serie ?
Many thanks[/QUOTE]I did not see anyone using such a method, and I'm also not sure how that method would work. The sum to sqrt(100)-sqrt(99) for example is [url=http://www.wolframalpha.com/input/?i=sum+from+n%3D1+to+50+%28sqrt%282*n%29-sqrt%282*n-1%29%29]4.6324[/url], but R(0,100) is given to be 3019.