Lattice Points on a Circle

Let $f(N)$ be the number of points with integer coordinates that are on a circle passing through $(0,0)$, $(N,0)$,$(0,N)$, and $(N,N)$.
It can be shown that $f(10000) = 36$.
What is the sum of all positive integers $N \le 10^{11}$ such that $f(N) = 420$?

The first step to problem-solving in math often involves noticing patterns or symmetries, or by simplification of the problem into easier sub-problems.

To simplify this problem: we first note that the circle defined by points $(0,0)$, $(N,0)$, $(0,N)$, $(N,N)$ has an equation of $(x-\frac{N}{2})^2 + (y-\frac{N}{2})^2 = 2(\frac{N}{2})^2 = \frac{N^2}{2}$, or $2x^2 – 2Nx + 2y^2 – 2Ny = 0$.

Rewriting it with the norm squared of the coordinate $(x,y)$, we get $2x^2 + 2y^2 = 2Nx + 2Ny$ or $x^2 + y^2 = Nx + Ny$.

For every point with integer coordinates on the circle, it will satisfy the above equation. So we wish to find all integers $N$ for which there are exactly 420 solutions $(x,y)$ to the given equation.

We can interpret the given equation $x^2 + y^2 = Nx + Ny$ as follows:

For a given $N$, and for a positive integer $M$ such that $M <= N$, the number of solutions to the equation $x^2 + y^2 = M(N-M)$ is exactly twice the number of divisors of $M(N-M)$ (excluding 1 and itself), since all divisors of $M(N-M)$ pair up into products that yield $M(N-M)$. Now to solve the problem, we wish to find the values of $N$ such that the number of solutions to $x^2 + y^2 = M(N-M)$ is 420, i.e., the number of divisors of the right side is exactly 210. A key to solve this is to note that if a positive integer has exactly 210 divisors, then its prime factorization is either $p^1 * q^2 * r^4$ or $s^4 * t^2$ where $p,q,r,s,t$ are distinct prime numbers. (There are only two possible cases since the number of divisors of a number $n = p_1^{a1} p_2^{a2}...p_k^{ak}$ is $(a1+1)(a2+1)...(ak+1)$, and the only way this can be 210 is either $2*3*5*7$ or $5*7*2$, up to rearrangement.) To solve $p^1 * q^2 * r^4 = M(N-M)$ for $M(N-M)$, there will only be a finite number of $M$ for fixed $p,q,r$. Similarly, to solve $s^4 * t^2 = M(N-M)$ for $M(N-M)$, there will only be a finite number of $M$ for fixed $s,t$. So by generating those finite number of possible $M$ and checking each to see if it yields a valid $N <= 10^{11}$, we can find all corresponding $N$ and sum them up. The result will involve number-theoretical algorithms such as divisor counting and prime factorization, which may be complex to implement and explain, but once understood, can be dealt with systematically. If you're looking for a specific numerical answer, this task involves a significant amount of computation and beyond the scope of a human without a computer. It's also important to note that certain results might have more than one corresponding $N$, so each $N$ must be recorded once and not duplicated in the final summation.

More Answers: