Project Euler #372 - Page 5

voidme · 2012-03-02, 18:39

That still won't guarantee integer coordinates because the y=N line means we cut off x at any moment. integer^2/decimal^2 does not guarantee an integer, nor does decimal^2 for that matter

the idea is looking at the straight x vs y lattice plane and determining which areas are valid vs invalid based on y^2/x^2, but the arbitrary cutoff at the top kills pick's theorem i'm sure. unless you can round it off and just-so-happen to not lose any/gain any lattice points?

seems possible but you never know with large scale numbers, especially since i'm sure the x-cutoff will be all over the place with respect to one whole x value to the next, and I don't think changing that is a trivial matter

PdB · 2012-03-02, 20:43

@lavalamp I investigated the triangles approach after you mentioned in a previous post that someone on the Euler forum posted a code that executes in 1 sec or so. Although you added that you didn't understand the algo, can you confirm that it is not dealing with triangles areas ? This would help !

lavalamp · 2012-03-02, 22:36

Quote:

Originally Posted by voidme

That still won't guarantee integer coordinates because the y=N line means we cut off x at any moment. integer^2/decimal^2 does not guarantee an integer, nor does decimal^2 for that matter

the idea is looking at the straight x vs y lattice plane and determining which areas are valid vs invalid based on y^2/x^2, but the arbitrary cutoff at the top kills pick's theorem i'm sure. unless you can round it off and just-so-happen to not lose any/gain any lattice points?

seems possible but you never know with large scale numbers, especially since i'm sure the x-cutoff will be all over the place with respect to one whole x value to the next, and I don't think changing that is a trivial matter

Perhaps we're thinking of different approaches, but in my head, only integer coordinates would be used.

Quote:

Originally Posted by PdB

@lavalamp I investigated the triangles approach after you mentioned in a previous post that someone on the Euler forum posted a code that executes in 1 sec or so. Although you added that you didn't understand the algo, can you confirm that it is not dealing with triangles areas ? This would help !

At least one person did use Pick's theorem as PART of their solution, yes. It seems that many more did not.

voidme · 2012-03-02, 22:54

Quote:

Originally Posted by lavalamp

Perhaps we're thinking of different approaches, but in my head, only integer coordinates would be used.

At least one person did use Pick's theorem as PART of their solution, yes. It seems that many more did not.

I refer to the sort of picture on the front page. straight x-y plane lattice ranging from (M,M) to (N,N) with bands representing valid areas where floor(y^2/x^2) is odd

lavalamp · 2012-03-03, 01:33

I understand that, and I saw Jaxon's plot. But rather than fitting triangles (trapeziums) on that plot (on shapes that aren't actually triangular (trapeziar?)), do it for y^2 against x^2.

For example, for R(100,10000), instead of marking curves for the range 101 to 10000 on both axes, mark trapeziums between the range 10201 and 100000000 on both axes and count the lattice points enclosed (and on the lower boundry).

This may or may not help, since now the problem is subtracting all pairs where either x or y or both are not perfect squares. It may turn out to be equally as hard.

TimeWizid · 2012-03-03, 02:58

I am so close but am getting bogged down by corner cases and possibly precision errors. My algorithm correctly calculates the first two examples, and incorrectly calculates the actual problem within a second. I use the strategy of calculating the triangle area, like others have mentioned. The tricky part is calculating the area efficiently. Here is a visualization that gives a general idea of how to do so. I hope this helps!

voidme · 2012-03-05, 21:19

I am close myself but precision errors are owning me. This program takes so damn long to run. debug hell

PdB · 2012-03-06, 20:01

At last, after switching from Ruby to C++ and increasing the computational precision, I got the right answer...

lavalamp · 2012-03-06, 21:49

I bet it ran faster too!

voidme · 2012-03-06, 23:44

you all make me weep :( So close yet so far

voidme · 2012-03-07, 14:28

yeah this is absurd, tired of running this thing to find that it's wrong because of lame precision issues

2012-03-02, 18:39	#45
voidme Feb 2012 67 Posts	That still won't guarantee integer coordinates because the y=N line means we cut off x at any moment. integer^2/decimal^2 does not guarantee an integer, nor does decimal^2 for that matter the idea is looking at the straight x vs y lattice plane and determining which areas are valid vs invalid based on y^2/x^2, but the arbitrary cutoff at the top kills pick's theorem i'm sure. unless you can round it off and just-so-happen to not lose any/gain any lattice points? seems possible but you never know with large scale numbers, especially since i'm sure the x-cutoff will be all over the place with respect to one whole x value to the next, and I don't think changing that is a trivial matter Last fiddled with by voidme on 2012-03-02 at 18:54

2012-03-02, 20:43	#46
PdB Feb 2012 11₁₀ Posts	@lavalamp I investigated the triangles approach after you mentioned in a previous post that someone on the Euler forum posted a code that executes in 1 sec or so. Although you added that you didn't understand the algo, can you confirm that it is not dealing with triangles areas ? This would help ! Last fiddled with by PdB on 2012-03-02 at 20:44

2012-03-03, 01:33	#49
lavalamp Oct 2007 Manchester, UK 5·271 Posts	I understand that, and I saw Jaxon's plot. But rather than fitting triangles (trapeziums) on that plot (on shapes that aren't actually triangular (trapeziar?)), do it for y^2 against x^2. For example, for R(100,10000), instead of marking curves for the range 101 to 10000 on both axes, mark trapeziums between the range 10201 and 100000000 on both axes and count the lattice points enclosed (and on the lower boundry). This may or may not help, since now the problem is subtracting all pairs where either x or y or both are not perfect squares. It may turn out to be equally as hard. Last fiddled with by lavalamp on 2012-03-03 at 01:33

2012-03-06, 20:01	#52
PdB Feb 2012 11 Posts	Got it ! At last, after switching from Ruby to C++ and increasing the computational precision, I got the right answer...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Project Euler	jhs	Puzzles	32	2021-01-19 04:05
Project Euler 486	lavalamp	Puzzles	8	2015-02-04 14:28
Euler (6,2,5) details.	Death	Math	10	2011-08-03 13:49
Project Euler	Mini-Geek	Lounge	2	2009-10-23 17:19
Bernoulli and Euler numbers (Sam Wagstaff project)	fivemack	Factoring	4	2008-02-24 00:39

2012-03-03, 02:58	#50
TimeWizid Mar 2012 United States 3₁₆ Posts	I am so close but am getting bogged down by corner cases and possibly precision errors. My algorithm correctly calculates the first two examples, and incorrectly calculates the actual problem within a second. I use the strategy of calculating the triangle area, like others have mentioned. The tricky part is calculating the area efficiently. Here is a visualization that gives a general idea of how to do so. I hope this helps!

2012-03-05, 21:19	#51
voidme Feb 2012 67 Posts	I am close myself but precision errors are owning me. This program takes so damn long to run. debug hell

2012-03-06, 21:49	#53
lavalamp Oct 2007 Manchester, UK 5×271 Posts	I bet it ran faster too!

2012-03-06, 23:44	#54
voidme Feb 2012 67 Posts	you all make me weep :( So close yet so far

2012-03-07, 14:28	#55
voidme Feb 2012 67 Posts	yeah this is absurd, tired of running this thing to find that it's wrong because of lame precision issues