The Circles Puzzle - Solution

The following is the output of a small program I wrote to find some circles going through exactly N (N >= 3) lattice points. I do not claim that this list is complete - just because the program didn't find a circle going through 17 points doesn't mean there isn't one!

In fact, there is. MathWorld has a rather nice entry on the whole issue. A Mr. Schinzel proved in

Schinzel, A.: "Sur l'existence d'un cercle passant par un nombre donné de points aux coordonnées entières." L'Enseignement Math. Ser. 2(4), pp. 71-72; 1958.

that there is such a circle for any positive N. He even gave a formula for such "Schinzel circles". Only -- it appears to be unknown what the centers and radii of the smallest such circles are.

In addition to the solutions below, there is of course the trivial solution for N = 2: a circle centered at (0, 0.5) with radius 0.5.

There's also a plot of those circles whose radius is smaller than 16.

I have omitted the full list of lattice points hit for larger N. I just give the first few of them. If you want the full list, re-run the program!

Entries in bold print are odd or otherwise interesting (e.g. because their center is at an unusual spot). Entries in italics (at least my web browser displays the <EM> tag as italics) are not necessarily the smallest possible circle for a given N. It's possible that there are smaller circles also going through the same number of lattice points, but it's equally well possible that the printed solution indeed is the smallest circle for that N.

N=  3: c = (1.166667, 0.833333), r = 1.178511
(    0,    1) (    1,    2) (    2,    0)

N=  4: c = (0.500000, 0.500000), r = 0.707107
(    0,    1) (    0,    0) (    1,    1) (    1,    0)

N=  5: c = (0.166667, 0.833333), r = 5.892557
(   -5,   -2) (   -4,    5) (    1,   -5) (    3,    6) (    6,    0)

N=  6: c = (0.000000, 0.500000), r = 2.500000
(   -2,    2) (   -2,   -1) (    0,    3) (    0,   -2) (    2,    2)
(    2,   -1)

N=  7: c = (0.772727, 0.590909), r = 23.890677
(  -19,   14) (   -7,  -22) (   -4,   24) (   -3,  -23) (   11,  -21)
(   16,   19) (   24,   -5)

N=  8: c = (0.500000, 0.500000), r = 1.581139
(   -1,    1) (   -1,    0) (    0,    2) (    0,   -1) (    1,    2)
(    1,   -1) (    2,    1) (    2,    0)

N=  9: c = (0.166667, 0.166667), r = 15.320647
(  -15,   -2) (  -14,    6) (  -13,    8) (   -2,  -15) (    4,   15)
(    6,  -14) (    8,  -13) (   11,   11) (   15,    4)

N= 10: c = (0.000000, 0.500000), r = 12.500000
(  -12,    4) (  -12,   -3) (  -10,    8) (  -10,   -7) (    0,   13)
(    0,  -12) (   10,    8) (   10,   -7) (   12,    4) (   12,   -3)

N= 11: c = (0.863636, 0.772727), r = 83.227384
(  -82,   -7) (  -75,   35) (  -56,  -60) (  -26,  -78) (  -12,   83)
(    1,   84) (   19,   82) (   33,  -76) (   43,  -71) (   64,   55)
(   80,  -25)

N= 12: c = (0.500000, 0.500000), r = 3.535534
(   -3,    1) (   -3,    0) (   -2,    3) (   -2,   -2) (    0,    4)
(    0,   -3) (    1,    4) (    1,   -3) (    3,    3) (    3,   -2)
(    4,    1) (    4,    0)

N= 13: c = (0.045455, 0.681818), r = 145.321317
( -142,  -30) ( -132,  -60) ( -123,   78) ( -113,   92) (  -52, -135)
(  -24,  144) (  -17,  145) (    1,  146) (   73, -125) (   83,  120)
(   88, -115) (  138,  -45) (  145,   11)

N= 14: c = (0.500000, 0.166667), r = 121.478164
( -119,   22) ( -117,   31) ( -112,   46) (  -82,  -89) (  -75,  -95)
(  -62, -104) (  -12,  121) (   13,  121) (   63, -104) (   76,  -95)
(   83,  -89) (  113,   46) (  118,   31) (  120,   22)

N= 15: c = (0.000000, 0.250000), r = 81.250000
(  -78,   23) (  -75,  -31) (  -70,  -41) (  -65,   49) (  -51,  -63)
(  -20,   79) (   -9,   81) (    0,  -81) (    9,   81) (   20,   79)
(   51,  -63) (   65,   49) (   70,  -41) (   75,  -31) (   78,   23)

N= 16: c = (0.500000, 0.500000), r = 5.700877
(   -5,    2) (   -5,   -1) (   -4,    4) (   -4,   -3) (   -3,    5)
(   -3,   -4) (   -1,    6) (   -1,   -5) (    2,    6) (    2,   -5)
(    4,    5) (    4,   -4) (    5,    4) (    5,   -3) (    6,    2)
(    6,   -1)

N= 18: c = (0.000000, 0.500000), r = 32.500000
(  -30,   13) (  -30,  -12) (  -28,   17) (  -28,  -16) (  -26,   20)
(  -26,  -19) (   -8,   32) (   -8,  -31) (    0,   33) (    0,  -32)
(    8,   32) (    8,  -31) (   26,   20) (   26,  -19) (   28,   17)
(   28,  -16) (   30,   13) (   30,  -12)

N= 20: c = (0.500000, 0.500000), r = 17.677670
(  -17,    3) (  -17,   -2) (  -15,    9) (  -15,   -8) (  -12,   13)
(  -12,  -12) (   -8,   16) (   -8,  -15) (   -2,   18) (   -2,  -17)
(    3,   18) (    3,  -17) (    9,   16) (    9,  -15) (   13,   13)
(   13,  -12) (   16,    9) (   16,   -8) (   18,    3) (   18,   -2)

N= 21: c = (0.227273, 0.681818), r = 368.412526
( -368,  -11) ( -353, -104) ( -350,  115) ( -315, -190) ( -255, -265)
( -249,  272) ( -240,  280) ( -224,  293) ( -140, -340) (  -92, -356)
(  -39,  367) (   45, -365) (   55,  365) (  138, -341) (  175,  325)
(  220, -295) (  294,  223) (  313, -194) (  349, -118) (  355,  100)
(  360,   80)

N= 22: c = (0.227273, 0.772727), r = 874.346568
( -873,   45) ( -870,  -84) ( -824, -291) ( -695,  531) ( -624,  613)
( -612,  625) ( -563, -668) ( -530,  696) ( -405, -774) ( -290, -824)
(  -44,  874) (   85,  871) (  292,  825) (  330, -809) (  349, -801)
(  369, -792) (  669,  564) (  775,  406) (  793, -368) (  802, -348)
(  810, -329) (  825,  291)

N= 24: c = (0.500000, 0.500000), r = 12.747549
(  -12,    3) (  -12,   -2) (  -11,    6) (  -11,   -5) (   -9,    9)
...

N= 28: c = (0.500000, 0.500000), r = 88.388348
(  -87,   13) (  -87,  -12) (  -80,   37) (  -80,  -36) (  -77,   43)
...

N= 30: c = (0.000000, 0.500000), r = 162.500000
( -156,   46) ( -156,  -45) ( -150,   63) ( -150,  -62) ( -140,   83)
...

N= 31: c = (0.833333, 0.833333), r = 486.166695
( -482,  -56) ( -459, -157) ( -448, -186) ( -444,  197) ( -441, -202)
( -423,  239) ( -406,  267) ( -388, -291) ( -329,  358) ( -291, -388)
( -202, -441) ( -186, -448) ( -157, -459) ( -119,  472) ( -102,  476)
(  -87,  479) (  -56, -482) (    1,  487) (   32,  486) (  197, -444)
(  239, -423) (  267, -406) (  274,  403) (  336,  353) (  353,  336)
(  358, -329) (  403,  274) (  472, -119) (  476, -102) (  479,  -87)
(  486,   32)

N= 32: c = (0.500000, 0.500000), r = 23.505319
(  -23,    1) (  -23,    0) (  -21,   10) (  -21,   -9) (  -20,   12)
...

N= 36: c = (0.500000, 0.500000), r = 45.961941
(  -45,    7) (  -45,   -6) (  -44,   12) (  -44,  -11) (  -42,   18)
...

N= 40: c = (0.500000, 0.500000), r = 63.737744
(  -63,    6) (  -63,   -5) (  -62,   13) (  -62,  -12) (  -57,   28)
...

N= 47: c = (0.166667, 0.166667), r = 1206.835278
(-1206,  -40) (-1201,  117) (-1199,  136) (-1169, -299) (-1159,  336)
(-1113, -466) (-1094, -509) (-1083, -532) ( -994, -684) ( -964,  726)
( -935,  763) ( -828,  878) ( -814,  891) ( -795,  908) ( -684, -994)
( -532,-1083) ( -509,-1094) ( -466,-1113) ( -462, 1115) ( -299,-1169)
( -249, 1181) ( -224, 1186) (  -49, 1206) (  -40,-1206) (   -2, 1207)
(  117,-1201) (  136,-1199) (  336,-1159) (  385, 1144) (  427, 1129)
(  570, 1064) (  611, 1041) (  726, -964) (  756,  941) (  763, -935)
(  878, -828) (  891, -814) (  908, -795) (  941,  756) ( 1041,  611)
( 1064,  570) ( 1115, -462) ( 1129,  427) ( 1144,  385) ( 1181, -249)
( 1186, -224) ( 1206,  -49)

N= 48: c = (0.500000, 0.500000), r = 52.559490
(  -52,    3) (  -52,   -2) (  -51,   11) (  -51,  -10) (  -47,   23)
...

N= 56: c = (0.500000, 0.500000), r = 537.645329
( -537,   13) ( -537,  -12) ( -519,  139) ( -519, -138) ( -512,  163)
...

N= 60: c = (0.500000, 0.500000), r = 229.809704
( -228,   25) ( -228,  -24) ( -227,   33) ( -227,  -32) ( -222,   58)
...

N= 64: c = (0.500000, 0.500000), r = 117.526593
( -117,    3) ( -117,   -2) ( -116,   16) ( -116,  -15) ( -114,   27)
...

N= 72: c = (0.500000, 0.500000), r = 189.505937
( -189,    2) ( -189,   -1) ( -188,   20) ( -188,  -19) ( -187,   28)
...

N= 80: c = (0.500000, 0.500000), r = 262.797451
( -262,   13) ( -262,  -12) ( -259,   42) ( -259,  -41) ( -257,   53)
...

N= 96: c = (0.500000, 0.500000), r = 336.544945
( -336,    6) ( -336,   -5) ( -335,   27) ( -335,  -26) ( -330,   64)
...

N=120: c = (0.500000, 0.500000), r = 2463.577176
(-2463,   20) (-2463,  -19) (-2450,  254) (-2450, -253) (-2437,  358)
...

N=128: c = (0.500000, 0.500000), r = 2065.142247
(-2064,   52) (-2064,  -51) (-2058,  166) (-2058, -165) (-2057,  178)
...

N=144: c = (0.500000, 0.500000), r = 1020.520700
(-1020,    7) (-1020,   -6) (-1016,   91) (-1016,  -90) (-1013,  120)
...

N=160: c = (0.500000, 0.500000), r = 2498.812218
(-2498,   40) (-2498,  -39) (-2492,  178) (-2492, -177) (-2487,  238)
...

N=192: c = (0.500000, 0.500000), r = 2060.573343
(-2059,   67) (-2059,  -66) (-2057,  113) (-2057, -112) (-2056,  130)
...

N=256: c = (0.500000, 0.500000), r = 5407.500578
(-5407,    3) (-5407,   -2) (-5402,  233) (-5402, -232) (-5392,  403)
...

The odd centers in this list are:

N=  3: c = ( 7/6 ,  5/6 )
N=  5: c = ( 1/6 ,  5/6 )
N=  7: c = (17/22, 13/22)
N=  9: c = ( 1/6 ,  1/6 )
N= 11: c = (19/22, 17/22)
N= 13: c = ( 1/22, 15/22)
N= 14: c = ( 1/2 ,  1/6 )
N= 15: c = (  0  ,  1/4 )
N= 21: c = ( 5/22, 15/22)
N= 22: c = ( 5/22, 17/22)
N= 31: c = ( 5/6 ,  5/6 )
N= 47: c = ( 1/6 ,  1/6 )

There's also a plot of those circles whose radius is smaller than 16.

(Actually, the program centers the circles for N=3 and N=6 differently. I chose new centers to avoid overlaps in the graph plot.)