• Announcements

Archived

This topic is now archived and is closed to further replies.

Circles!

Recommended Posts

Heza64    122
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

Share on other sites
Punty50    122
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.

Share on other sites
LilBudyWizer    491
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]

Share on other sites
Guest Anonymous Poster
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).

Share on other sites
LilBudyWizer    491
Just out of curiosity how did you come up with those?

Share on other sites
jperalta    356
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 --

Share on other sites
Guest Anonymous Poster
25 I knew out of my head. 1105 I wrote a couple of lines in Haskell to find.

Share on other sites
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]

Share on other sites
Punty50    122
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

Share on other sites
Colin Jeanne    1114
quote:
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

Share on other sites
I think it's called "Fermat's 2 squares theorem".

The proof (the one I studied anyway, in Rings & Factorisation lectures) involves factoristation of Gaussian integers, which form a UFD (unique factorisation domain).

a^2 + b^2 = (a+ib)(a-ib)

Looks like it was Euler not Gauss who published the first prrof.

That link also mentions the analogy for sums of three squares, it says the proof is a lot harder than the one for sums of 4 squares. It also tells you how to work out how many combinations there are:

Jacobi's Two Square Theorem: The number of representations of a positive integer as the sum of two squares is equal to four times the difference of the numbers of divisors congruent to 1 and 3 modulo 4.

"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 31, 2003 9:47:08 AM]

Share on other sites
alvaro    21246
You can find circles with arbitrarily large numbers of points with integer coordinates. I''ll sketch the idea. Imagine you want a circle with at least 5000 points with integer coordinates. Start by selecting 5000 rational numbers. On a plane, draw those numbers on the x axis. Now draw a circle of radius one centered in (0,1). For each point that you draw on the x axis, draw a line that joins it with (0,2). The line will intersect the circle in two points: (0,2) and (a,b). You can verify that a and b are rational numbers. Now select the least common multiple of all the a''s and b''s generated this way. Scale the figure by that factor, and the radius one circle is now a big circle that has at least 5000 points with integer coordinates.

Share on other sites
Colin Jeanne    1114
Paradigm Shifter, thank you very much!

Qui fut tout, et qui ne fut rien