A355884 - OEIS

%I #33 Sep 24 2022 08:17:30

%S 0,0,1,34,223,997,3402,9141,21665,46390,90874,167539,293443,487082,

%T 781537,1209469,1816528,2661113,3822203,5369662,7420495,10086360,

%U 13494376

%N Number of circles in an n X n grid passing through at least three points.

%H C. Lin, <a href="https://math.stackexchange.com/questions/273348/number-of-circles-in-configuration">Number of circles in configuration</a>, Mathematics Stack Exchange, 2013.

%o (PARI) \\ after user joriki's Java code at Mathematics Stack Exchange link

%o circles(n) = {

%o   my(C = List());

%o   for (x1 = 1, n,

%o     for (y1 = 1, n,

%o       for (x2 = 1, x1,

%o         for (y2 = 1, n,

%o           for (x3 = 1, x2,

%o             for (y3 = 1, n,

%o                 my( ax2 = 2 * (x2 - x1),

%o                   ay2 = 2 * (y2 - y1),

%o                   ax3 = 2 * (x3 - x1),

%o                   ay3 = 2 * (y3 - y1),

%o                   den = ax2 * ay3 - ax3 * ay2

%o                 );

%o               if (den == 0, next);

%o                 my( b2 = x2^2 + y2^2 - x1^2 - y1^2,

%o                   b3 = x3^2 + y3^2 - x1^2 - y1^2,

%o                   x = b2 * ay3 - b3 * ay2,

%o                   y = ax2 * b3 - ax3 * b2,

%o                   gc = gcd(gcd(x, y), den)

%o                 );

%o               if (den < 0, gc = -gc);

%o                 x /= gc; y /= gc; den /= gc;

%o                 my( dx = x - den * x1,

%o                   dy = y - den * y1,

%o                   s = dx^2 + dy^2

%o                 );

%o               listput(C, [x, y, s, den])

%o   ))))));

%o   Set(C)

%o };

%o for (k = 0, 10, print1(#circles(k), ", "))  \\ _Hugo Pfoertner_, Sep 22 2022

%Y Cf. A192493, A192494, A357301.

%K nonn,hard,more

%O 0,4

%A _Sharvil Kesarwani_, Jul 20 2022