3
$\begingroup$

What is the most number of integer lattice points that lie on the circumference of a single circle whose radius is 80 or less? Please no computer computations.

$\endgroup$
3
  • 2
    $\begingroup$ See OEIS: A000448 (possible spoiler) $\endgroup$ Sep 12 at 15:14
  • 1
    $\begingroup$ Does the centre of the circle have to be located on a lattice point? $\endgroup$
    – trolley813
    Sep 12 at 16:25
  • $\begingroup$ @trolley813 no it can be anywhere and the radius doesn't have to be integer. $\endgroup$ Sep 13 at 1:41
8
$\begingroup$

From OEIS: A000448

5525 is the smallest number that is the sum of two squares in at least six ways.

For a circle centered at the origin, this gives these lattice points:

(7, 74) (14, 73) (22, 71) (25, 70) (41, 62) (50, 55) along with their reflections.

For a total of

48 points on a circle with radius $\sqrt{5525}\approx74.33$

$\endgroup$
4
  • $\begingroup$ Oh, I totally missed this solution. Very nice! $\endgroup$ Sep 13 at 1:40
  • $\begingroup$ I verified with a program that this answer is optimal. Well done! $\endgroup$ Sep 13 at 7:23
  • $\begingroup$ @DmitryKamenetsky So, this question has the [no-computers] tag, but the accepted answer requires a computer simulation as a proof? $\endgroup$
    – Stef
    Sep 13 at 14:58
  • $\begingroup$ @Stef I am pretty sure it can be proven without a computer, but I am just lazy :) $\endgroup$ Sep 13 at 15:24
3
$\begingroup$

A little experimentation with Euclids formula, demonstrates that there are only

12

primitive Pythagorean triples with largest element less than or equal to 80. If, from these, we choose the sets

(3,4,5), (5, 12, 13), (16, 63, 65), (33, 56, 65)

and note that 65=5*13, then we can produce the triples

(39, 52, 65), (25, 60, 65), (16, 63, 65), (33, 56, 65)

Using them, plus their reflections about the lines y=x, y=-x, y=0, and x=0, plus the four extra points sitting on the x and y axes, we can get a total of

36

points in a circle with radius

65

$\endgroup$
6
  • 1
    $\begingroup$ This answer seems like it assumes that the centre of the circle is a lattice point, and it's not obvious that that's always the best you can do. (E.g., if the question had said "with radius strictly less than 1", then on those terms the best you can do is 1 with a radius-0 "circle", but in fact you can run a radius-1/sqrt2 circle through four lattice points.) My guess is that this actually is best, but it seems to me the proof has a gap. Am I missing something? $\endgroup$
    – Gareth McCaughan
    Sep 12 at 23:21
  • $\begingroup$ I did look for a solution with the centre placed at (1/2,1/2), which required looking at radii up to 160*(1/2). But the smaller (orthogonal) terms of all primitive triples have one even and one odd term, so the circles don't fit well with the lattice points. I considered an irregular centre position but, without any formal proof, I doubt that the loss of symmetry could possibly increase the number of points - although to prove that might trequire a computer-based search. $\endgroup$
    – Penguino
    Sep 13 at 0:25
  • 1
    $\begingroup$ The question does not require the radius to be an integer. $\endgroup$ Sep 13 at 1:13
  • $\begingroup$ True, and I am quite happy to see a better solution. $\endgroup$
    – Penguino
    Sep 13 at 2:47
  • $\begingroup$ @GarethMcCaughan A radius-0 circle would technically be a "better" solution if you contort the reading of the problem a bit, in that all of its points lie on a lattice point, and there are an infinite number of points on a circle - it just so happens that in this case all of them are on the same point, but this does break the problem somewhat and I'm sure was not the intent. $\endgroup$ Sep 13 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.