Project Euler #372

[science_man_88]

Originally Posted by lavalamp

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 4.6324, but R(0,100) is given to be 3019.

the code I made above gave me 5247 for the method it used. but:

b=0;for(x=1,100,for(y=1,100,if(floor((y^2)/(x^2))%2==1,b=b+1)));b

give 3019.

[voidme]

I think this is possible to do in log-time, just a matter of finding the differences and how long those blocks will be

[voidme]

That's the "naive" brute force approach

[science_man_88]

Originally Posted by science_man_88

the code I made above gave me 5247 for the method it used. but:

b=0;for(x=1,100,for(y=1,100,if(floor((y^2)/(x^2))%2==1,b=b+1)));b

give 3019.

I think I have 3 changes to this to make it correctly done and faster.

1) set the smallest at M+1 and the limit at N
2) note that floor(y^2/x^2) == floor((y/x)^2)
3) note that if (x,y) works so are all (zx,zy) such that zx and zy are multiples of (x,y) such that they both stay under N+1.

[ATH]

Finally got my brute force program to give the correct result, runtime is 70min.

Someone in the forum made a smart program that gets the result in 1sec, but I don't understand his method.

[science_man_88]

Originally Posted by ATH

Finally got my brute force program to give the correct result, runtime is 70min.

Someone in the forum made a smart program that gets the result in 1sec, but I don't understand his method.

I found another optimization to my program that I could make ( I have to remake the others because I had to copy it from here again).

my new optimization is to not be 0 y>=x because if not y<x (y^2/x^2)<1 and hence floor(y^2/x^2)==0

[voidme]

Originally Posted by science_man_88

I found another optimization to my program that I could make ( I have to remake the others because I had to copy it from here again).

my new optimization is to not be 0 y>=x because if not y<x (y^2/x^2)<1 and hence floor(y^2/x^2)==0

That approach will still take more time than is reasonable to run

[science_man_88]

Originally Posted by voidme

That approach will still take more time than is reasonable to run

I'll admit this alone doesn't because it only cuts the amount of possibilities by around half.

PS:

(14:11)>b=0;for(x=100,10000,for(y=x,10000,if(floor((y/x)^2)%2==1,b=b+1)));b
%44 = 29755324
(14:25)>##
  ***   last result computed in 55,396 ms.
(14:25)>b=0;for(x=100,10000,for(y=1,10000,if(floor((y/x)^2)%2==1,b=b+1)));b
%45 = 29755324
(14:27)>##
  ***   last result computed in 1mn, 31,775 ms.

both got above what the page can "verify"

[lavalamp]

I'll just leave this here.

You don't need to loop through each individual value of y.

[science_man_88]

Originally Posted by lavalamp

I'll just leave this here.

You don't need to loop through each individual value of y.

unless I'm counting something twice that shouldn't affect the resulting number, also I know that like I said the first code cuts the amount of checks by half.

[lavalamp]

It doesn't affect the answer, but it sure as hell affects the run time.

By a factor of millions.

Edit: Or at least it does for the much larger range required by the problem.

Edit 2: Just noticed that you get the wrong answer because you're running the loop from 100 instead of 101. The problem specifies M < x <= N.