Hey, I''ve gotta question. On a normal grid, if the circles radius is from one point to another, can the circle''s edge touch more than 8 points? Like this: * O * O * O * * * O * * X * * O * * * O * O * O * The O''s are the points of the circle''s edge that touch a grid point. There are 8 in this circle. Can there ever be any more? Thanx Ian

The question can be thought of also as this: How many unique pairs (x,y) exist such that x^2+y^2 = r^2. If there exists one pair (x,y), then there are 8 points: (x,y) (y,x) (-x,y) (-y,x) (x,-y) (y,-x) (-x,-y) (-y,-x). In the case of r = 5, the pair is (3,4). I think you are missing the "trivial" points of (0,5) (5,0) (0, -5) and (-5,0) So I find that 12 points exist. Im trying to find a proof that there exists only one unique pair (x,y) that satisfies the equation x^2 + y^2 = r^2, but haven''t really come across one yet. If you can prove that fact, then you prove the fact that there can only be at most 12 points.

Well, if a circle has a radius of 5 and is centered at the origin then (5,0), (4,3), (3,4), (0,5), (-3,4), (-4,3), (-5,0), (-4,-3), (-3,-4), (0,-5), (3,-4) and (4,-3) are all points on the circle. Since that is 12 points I guess the answer is yes. I have no idea if there can be more than twelve. Certainly sine and cosine take on an infinite number of rational values and it seems unlikely that there are only 12 places where they are both rational at the same time, but it is beyond my limited knowledge of number theory to say whether or not they do.

I think you would need to qualify that with x, y and r are all rational as well since otherwise every point on a circle of radius r centered at the origin meets that condition.

[edited by - LilBudyWizer on January 29, 2003 5:37:20 PM]

There sure can be more than 12 points. For example, with r = 25 you have the points (0, 25) (7, 24) (15, 20) plus symmetry, and with r = 1105 you have (0, 1105) (47, 1104) (105, 1100) (169, 1092) (264, 1073) (272, 1071) (425, 1020) (468, 1001) (520, 975) (561, 952) (576, 943) (663, 884) (700, 855) (744, 817).

Just out of curiosity how did you come up with those?

The fact is that given x^2+y^2=r^2 there are an indefinite number of points on a circle unless the points are forced to be integral.

-- Exitus Acta Probat --

25 I knew out of my head. 1105 I wrote a couple of lines in Haskell to find.

Fermat told us exactly which positive integers can be expressed as a sum of two squared integers. He left Gauss to provide a proof though, I think.

Firstly, if p is prime, then p is a sum of two squares if and only if p is NOT congruent to 3 modulo 4 (i.e. in C/C++, prime p is a sum of two squares if( p%4 != 3 ))

So 2 = 1*1 + 1*1, 5 = 1*1 + 2*2, but you can't express 3 as a sum of two squares. Primes can be expressed as a sum of two squares in essentially only one way (i.e. you could reverse the order of the addition (or negate one or both), but that is all).

If n is not prime, it is a sum of two squares if and only if, in the factorisation of n into prime factors, primes which are congruent to 3 modulo 4 occur only to EVEN powers. There will be several ways of expressing n as a sum of two squares.

The proof involves the use of Gaussian integers, i.e. complex numbers of the form w = x + iy with x,y integers and i = sqrt(-1). It's a fascinating topic though.



"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

[edited by - Paradigm Shifter on January 30, 2003 5:30:04 AM]

Good old number theory that a highschooler shouldn''t be dwelving into. I wasn''t quite sure about that thing, I knew the Fermat had some role in it, and that Gauss (my favorite mathematician) finished things off. I ended up looking through my books and finding it. Is there any function that returns the number of integral pairs such that x^2 + y^2 = z? I would be interested in this. You could always brute force it, but thats not as much fun as the pure math aspect of it.

Brendan

quote:

---

Original post by Paradigm Shifter
Firstly, if p is prime, then p is a sum of two squares if and only if p is NOT congruent to 3 modulo 4

---

Do you happen to know the name of this proof or (better yet) a place where the proof of this can be found? I have been looking off and on since last summer because I want to see if I can come up with an analogous theorem for 3 dimensions.

---

Qui fut tout, et qui ne fut rien
Invader''s Realm