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.
$\begingroup$
$\endgroup$
3
asked Sep 12, 2021 at 14:07
-
2$\begingroup$ See OEIS: A000448 (possible spoiler) $\endgroup$– Daniel MathiasSep 12, 2021 at 15:14
-
1$\begingroup$ Does the centre of the circle have to be located on a lattice point? $\endgroup$– trolley813Sep 12, 2021 at 16:25
-
$\begingroup$ @trolley813 no it can be anywhere and the radius doesn't have to be integer. $\endgroup$– Dmitry KamenetskySep 13, 2021 at 1:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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$
answered Sep 13, 2021 at 1:24
-
$\begingroup$ Oh, I totally missed this solution. Very nice! $\endgroup$ Sep 13, 2021 at 1:40
-
$\begingroup$ I verified with a program that this answer is optimal. Well done! $\endgroup$ Sep 13, 2021 at 7:23
-
1$\begingroup$ @DmitryKamenetsky So, this question has the [no-computers] tag, but the accepted answer requires a computer simulation as a proof? $\endgroup$– StefSep 13, 2021 at 14:58
-
$\begingroup$ @Stef I am pretty sure it can be proven without a computer, but I am just lazy :) $\endgroup$ Sep 13, 2021 at 15:24
$\begingroup$
$\endgroup$
6
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
-
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, 2021 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$– PenguinoSep 13, 2021 at 0:25
-
1$\begingroup$ The question does not require the radius to be an integer. $\endgroup$ Sep 13, 2021 at 1:13
-
$\begingroup$ True, and I am quite happy to see a better solution. $\endgroup$– PenguinoSep 13, 2021 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, 2021 at 13:28