1
$\begingroup$

In a 2D integer grid, the points in increasing distance from the origin are:
$(0,0)$
$(\pm1,0)$ and $(0,\pm1)$
$(\pm1,\pm1)$
etc

By symmetry we need only consider one-eighth of the lattice, $x\ge0$ and $y\ge x$. In this octant, the points in increasing norm are:
(0,0)
(1,0)
...
(3,2)
(4,0)
(3,3)
...
(4,2)
(4,3) and (5,0)
(5,1)
etc

Given some point $(n,m)$ at a distance $r=\sqrt{n^2+m^2}$ from the origin, how can I find the point $(p,q)$ with the next-greatest distance from the origin? That is, which integers $p,q$ minimise $p^2+q^2$ subject to $p\ge 0$ , $q\ge p$ and $(p^2+q^2) > r^2$?

$\endgroup$
2
  • $\begingroup$ All these numbers are known, see mathworld.wolfram.com/SumofSquaresFunction.html $\endgroup$ Dec 8, 2015 at 14:40
  • $\begingroup$ The related oeis.org/A004018 states "The zeros in this sequence correspond to those integers with an equal number of 4k+1 and 4k+3 divisors, or equivalently to those that have at least one 4k+3 prime factor with an odd exponent". This would seem to hint that it is hard to find $p^2+q^2$, let alone $p$ and $q$. $\endgroup$
    – jeq
    Dec 8, 2015 at 16:01

0

Browse other questions tagged or ask your own question.