[Tutor] Find Integer co-ordinates lying on a circle

[Gerard Flanagan]

Shashwat Anand wrote:
 > How to find all possible integer co-ordinates lying on a circle of 
given radius 'r'.
 > If given the upper bound of 'r', I want to calculate all given 
co-ordinates lying for 0 <= r <= n
 >
 > Let's say the upper bound of radius is 5
 > All possible results are:
 > radius 'r' - (x, y)
 > 0 - (0, 0)
 > 1 - (1, 0), (0, 1), (-1, 0), (0, -1)
 > 2 - (2, 0), (0, 2), (-2, 0), (0, -2)
 > 3 - (3, 0), (0, 3), (-3, 0), (0, -3)
 > 4 - (4, 0), (0, 4), (-4, 0), (0, -4)
 > 5 - (5, 0), (0, 5), (-5, 0), (0, -5), (3, 4), (4,3), (3, -4), (4, 
-3), (-3, 4), (-4, 3), (-3, -4), (-4, -3)
 >
 > Also for a particular radius, lots of possible combination of (x, y) 
is possible so best datastructure could be defaultdict for further 
operations IMHO.
 > So my desired output is:
 > defaultdict(<type 'list'>, {0 : [(0, 0)], 1: [(1, 0), (0, 1), (-1, 
0), (0, -1)], 2: [(2, 0), (0, 2), (-2, 0), (0, -2)], 3: [(3, 0), (0, 3), 
(-3, 0), (0, -3)], 4: [(4, 0), (0, 4), (-4, 0), (0, -4)], 5: [(5, 0), 
(0, 5), (-5, 0), (0, -5), (3, 4), (4,3), (3, -4), (4, -3), (-3, 4), (-4, 
3), (-3, -4), (-4, -3)]})
 >

I think you only need to consider the first quadrant (positive  x and 
y). So if you find one result you can determine the other seven (or 
three for a point on the axis). One approach might be to use complex 
numbers:


m = complex(0, 1).__mul__

rng4 = range(4)

def rotate_and_mirror(z):
    for _ in rng4:
        yield z
        yield z.conjugate()
        z = m(z)

or:

def rotate_and_mirror2(x, y):
    z = complex(x, y)
    for _ in rng4:
        yield z
        yield z.conjugate()
        z = m(z)

for z in rotate_and_mirror2(3, 4):
    print z

(3+4j)
(3-4j)
(-4+3j)
(-4-3j)
(-3-4j)
(-3+4j)
(4-3j)
(4+3j)


 > My approach using pythagorean triplets:
 > >>> d = collections.defaultdict(list)
 > >>> s = list(set([((u*u + v*v), (v*v - u*u, 2*u*v)) for u in 
range(10) for v in range(u+1, 10)]))
 > >>> [d[k].append(v) for k,v in s]
 > However it sure is wrong and fails in my case.
 >
 > Any suggestions as to how can I reach my desired goal, or are there 
any other options to tackle this problem?
 >

I think there are formulas for finding triples, eg.

def primitive_triples(N):
    for i in xrange(1, N):
        m = 2 * i
        h = m * (i+1)
        yield m+1, h, h+1

So it seems the problem is finding primitive triples and multiples of 
those triples. ie. (3, 4) is on the circle with radius 5, so (6, 8) is 
on the circle with radius 10 etc.

That's the best I've got - my "maths brain" is much atrophied! Good luck.

Gerard