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

0, 0, 1, 34, 223, 997, 3402, 9141, 21665, 46390, 90874, 167539, 293443, 487082, 781537, 1209469, 1816528, 2661113, 3822203, 5369662, 7420495, 10086360, 13494376, 17814938, 23256396, 29990654, 38309236, 48485593, 60815343, 75631629, 93401987, 114488127, 139471069

Offset

0,4

Links

Chai Wah Wu, Table of n, a(n) for n = 0..55

C. Lin, Number of circles in configuration, Mathematics Stack Exchange, 2013.

Prog

(PARI) \\ after user joriki's Java code at Mathematics Stack Exchange link
circles(n) = {
  my(C = List());
  for (x1 = 1, n,
    for (y1 = 1, n,
      for (x2 = 1, x1,
        for (y2 = 1, n,
          for (x3 = 1, x2,
            for (y3 = 1, n,
                my( ax2 = 2 * (x2 - x1),
                  ay2 = 2 * (y2 - y1),
                  ax3 = 2 * (x3 - x1),
                  ay3 = 2 * (y3 - y1),
                  den = ax2 * ay3 - ax3 * ay2
                );
              if (den == 0, next);
                my( b2 = x2^2 + y2^2 - x1^2 - y1^2,
                  b3 = x3^2 + y3^2 - x1^2 - y1^2,
                  x = b2 * ay3 - b3 * ay2,
                  y = ax2 * b3 - ax3 * b2,
                  gc = gcd(gcd(x, y), den)
                );
              if (den < 0, gc = -gc);
                x /= gc; y /= gc; den /= gc;
                my( dx = x - den * x1,
                  dy = y - den * y1,
                  s = dx^2 + dy^2
                );
              listput(C, [x, y, s, den])
  ))))));
  Set(C)
};
for (k = 0, 10, print1(#circles(k), ", "))  \\ Hugo Pfoertner, Sep 22 2022
(Python)
# after Hugo Pfoertner's PARI code
from math import gcd
from itertools import product
from sympy.utilities.iterables import combinations_with_replacement
def A355884(n):
    c, t = set(), 0
    for x1, x2, x3 in combinations_with_replacement(range(1, n+1), 3):
        for y1, y2, y3 in product(range(1, n+1), repeat=3):
            den = (x1-x2)*(y1-y3)-(x1-x3)*(y1-y2)<<2
            if den:
                a, b = x1**2-x3**2+y1**2-y3**2<<1, x1**2-x2**2+y1**2-y2**2<<1
                x = -(y1-y2)*a+(y1-y3)*b
                y = (x1-x2)*a-(x1-x3)*b
                gc = gcd(x, y, den)
                if den < 0: gc = -gc
                x //= gc
                y //= gc
                den //= gc
                if (z:=(x, y, (x-den*x1)**2+(y-den*y1)**2, den)) not in c:
                    t += 1
                    c.add(z)
    return t # Chai Wah Wu, Nov 30 2025

Crossrefs

Cf. A192493, A192494, A357301.

Sequence in context: A058581 A050263 A020869 * A055716 A233300 A281052

Adjacent sequences: A355881 A355882 A355883 * A355885 A355886 A355887

Keyword

nonn,hard

Author

Sharvil Kesarwani, Jul 20 2022

Extensions

a(23)-a(32) from Chai Wah Wu, Nov 30 2025

Status

approved