Circle Grid Points

Number Theory Level 5

A circle centered at the origin is given by

$x^2 + y^2 = R^2$

It turns out that it is possible to determine how many points are on the circumference of the circle that have both integer $x$ and $y$ coordinates, depending on the radius $R$ .

In this problem we want to determine the sum of the smallest and the largest radius that are less than 1000, such that the circles with these radii intersect the grid (i.e. the intersection point has both integer $x$ and $y$ coordinates) at exactly 36 distinct points.

The answer is 1051.

1 solution

David Jedelsky
Feb 10, 2019

Is this supposed to be solved without computer aid?

As the problem is highly symmetrical, we can consider just single octant. We are looking for $36$ integer points in total. Thus, after removing four trivial points laying on axes we can count number of points inside each octant: $(36-4)/8 = 4$ . That means we are looking for exactly $4$ right triangles in single octant. It can be easily checked by Pythagorean theorem for integer $x$ values corresponding to single octant (e.g. for $x \in ( 1, R / \sqrt{2})$ ) with following code:

R=1000
CNT=4 # (36-4)/8
INVSQRT2=0.707 # Fair enough for our purposes

issq = { r*r: r for r in range(0,R+1) }

first, last = R, 0
for r in range(1,R+1):
    cnt = len( [x for x in range(1, int(INVSQRT2*r)) if (r*r-x*x) in issq] )
    if cnt == CNT:
        first, last = min(first,r), r

print("{} + {} = {}".format(first, last, first+last))

The question never states that R is an integer. In fact, it need not be; if R=697sqrt(2), then there are 36 solutions for (x,y).

Joe Mansley - 1 year, 2 months ago

Circle Grid Points

The answer is 1051.

1 solution

0 pending reports