Project Euler #372

[science_man_88]

Originally Posted by 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.

my code works for 0,100 but doesn't give the suggest answer for 100,10000 is all I was trying to say.

[lavalamp]

See my second edit.

[voidme]

hard part is that even if you loop over x you have to be able to know, from x alone, how many ways there are to count whole number solutions between oddnumbered ranges

[science_man_88]

Originally Posted by voidme

hard part is that even if you loop over x you have to be able to know, from x alone, how many ways there are to count whole number solutions between oddnumbered ranges

looking at my prints lately in my code the easy part is:

1:odd
x:x*odd

but then there's still more of them. and that for me is the hard part to code I think. marking all odd numbers * a number not that hard I would think.

[PdB]

I found 301450082318808111, but it gets the red cross... can any solver tell me how close (or far...) I am ? Thanks

[voidme]

not sure

my method takes a long time but that seems like its in the right ballpark

what im doing is iterating from M to N and trying to be able to automatically count the lattice points that fall between the two bounds all the way up but i have no idea how to count lattice points automatically

for ex, floor(y/x)^2 is odd when

odd number <= (y/x)^2 < even number
x*sqrt(odd number) <= y < x*sqrt(even number)

so these bounds will extend as far as they can until you start to exceed N. somehow there should be a way to look at these bounds and know how many lattice points will exist in that segment but idk

[lavalamp]

Originally Posted by PdB

I found 301450082318808111, but it gets the red cross... can any solver tell me how close (or far...) I am ? Thanks

Remember what I said to SM88 before.

Originally Posted by lavalamp

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.

[voidme]

is there a much faster way to do it than my logic? I am hitting a wall here

[PdB]

@lavalamp : unfotunately, I did well start at 2e6+1.

@voidme : another path might be to compute triangles surfaces... N and M are so huge that maybye the boundary effets (ceil & floor on y=x.sqrt(n) lines) will compensate. We'll see.

[PdB]

The triangles surfaces method is pretty fast : 2 seconds to get 301257385700605400. It is still a wrong answer, but it's close to my previous result, obtained with a completely different way. Which means I'm close to the goal... the question is whether this fast but approximative method can be refined. Not sure !

[ldesnogu]

Originally Posted by PdB

The triangles surfaces method is pretty fast : 2 seconds to get 301257385700605400. It is still a wrong answer, but it's close to my previous result, obtained with a completely different way. Which means I'm close to the goal... the question is whether this fast but approximative method can be refined. Not sure !

For the triangle surface to work, you'd have to compute not the geometric surface but the surface you'd obtain by rasterizing your triangle.