Project Euler #372 - Page 4

PdB · 2012-03-01, 16:14

If I am not mistaken, rasterizing means a loop on x from M to N (N decreasing) with an inner loop from 1 to 250,000, which I try to avoid.

voidme · 2012-03-01, 16:32

how do you determine the size of the triangles?

PdB · 2012-03-01, 17:08

Quote:

Originally Posted by voidme

how do you determine the size of the triangles?

Take the graph posted by Jaxon (page 1 on this thread), draw a square of side N-M (bottom-left corner is (M,M)), and consider all triangles aligned on the top left corner, whose hypothenuses are on the lines y=sqrt(n).x where n=1..250,000. Sum the surfaces of these triangles, affected by a minus sign for those where n is even. Hope this is clear enough

voidme · 2012-03-01, 21:54

I suspect they are not clean triangles all the way through. Stuff gets messy towards the lefthand side

PdB · 2012-03-01, 22:48

Quote:

Originally Posted by voidme

I suspect they are not clean triangles all the way through. Stuff gets messy towards the lefthand side

Alas !... I agree and I don't know where to go from there...

lavalamp · 2012-03-01, 23:21

PdB, I assumed that you had made the simple error of running from 2000000 instead of 2000001, but if that is not the case I do not know how you missed it without seeing your code. You were ever so eye-wateringly close.

PdB · 2012-03-02, 13:04

I didn't. Check your mailbox

voidme · 2012-03-02, 13:58

I now get similar answers to PdB but I know why it's wrong... I don't think the area itself is sufficient. there are things like pick's theorem that show you how to calculate # of lattice points in polygons from the area so it seems like a matter of converting area into a count of points by figuring out how many points are inside the triangle vs. how many are on the sides. problem is the coordinates wouldn't all be whole numbers which may pose an issue.

try it out with lower numbers etc, area gets you close but it's only an approx.

PdB · 2012-03-02, 15:47

I tried to apply Pick S = i + b/2 -1 :
- S = top side * left side / 2
- b = b top + b left + b hypothenus (b hypothenus = 0 when sqrt(n) is not an integer) (beware not to count each vertice more than once)
- both lead to i
- i+b is the number of points in triangle
- result = triangle 1 - triangle 2 + triangle 3..... - triangle 250000

Not surprisingly, I obtained again approx values, close to the previous ones.

Any (new) idea ?

voidme · 2012-03-02, 15:50

well pick's theorem requires that all the vertices of the triangle are integers, which in this case isn't necessarily true because the upper right vertex of a triangle is cut off arbitrarily at y=N and so the hypotenuse line is not guaranteed at all to end on a nice clean number

lavalamp · 2012-03-02, 18:21

Since Pick's theorem requires integer coordinates for the vertices, perhaps it could be used, not for x and y, but for x^2 and y^2, then subtract out any pairs that include non-square lattice points.

Of course, the problem then becomes determinining how many pairs to discount.

2012-03-02, 13:58	#41
voidme Feb 2012 67 Posts	I now get similar answers to PdB but I know why it's wrong... I don't think the area itself is sufficient. there are things like pick's theorem that show you how to calculate # of lattice points in polygons from the area so it seems like a matter of converting area into a count of points by figuring out how many points are inside the triangle vs. how many are on the sides. problem is the coordinates wouldn't all be whole numbers which may pose an issue. try it out with lower numbers etc, area gets you close but it's only an approx. Last fiddled with by voidme on 2012-03-02 at 14:03

2012-03-02, 15:47	#42
PdB Feb 2012 11 Posts	I tried to apply Pick S = i + b/2 -1 : - S = top side * left side / 2 - b = b top + b left + b hypothenus (b hypothenus = 0 when sqrt(n) is not an integer) (beware not to count each vertice more than once) - both lead to i - i+b is the number of points in triangle - result = triangle 1 - triangle 2 + triangle 3..... - triangle 250000 Not surprisingly, I obtained again approx values, close to the previous ones. Any (new) idea ? Last fiddled with by PdB on 2012-03-02 at 15:48

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-01, 16:14	#34
PdB Feb 2012 1011₂ Posts	If I am not mistaken, rasterizing means a loop on x from M to N (N decreasing) with an inner loop from 1 to 250,000, which I try to avoid.

2012-03-01, 16:32	#35
voidme Feb 2012 67 Posts	how do you determine the size of the triangles?

2012-03-01, 21:54	#37
voidme Feb 2012 67 Posts	I suspect they are not clean triangles all the way through. Stuff gets messy towards the lefthand side

2012-03-01, 23:21	#39
lavalamp Oct 2007 Manchester, UK 10101001011₂ Posts	PdB, I assumed that you had made the simple error of running from 2000000 instead of 2000001, but if that is not the case I do not know how you missed it without seeing your code. You were ever so eye-wateringly close.

2012-03-02, 13:04	#40
PdB Feb 2012 1011₂ Posts	I didn't. Check your mailbox

2012-03-02, 15:50	#43
voidme Feb 2012 67 Posts	well pick's theorem requires that all the vertices of the triangle are integers, which in this case isn't necessarily true because the upper right vertex of a triangle is cut off arbitrarily at y=N and so the hypotenuse line is not guaranteed at all to end on a nice clean number

2012-03-02, 18:21	#44
lavalamp Oct 2007 Manchester, UK 54B₁₆ Posts	Since Pick's theorem requires integer coordinates for the vertices, perhaps it could be used, not for x and y, but for x^2 and y^2, then subtract out any pairs that include non-square lattice points. Of course, the problem then becomes determinining how many pairs to discount.