A341198 Number of points on or inside the circle of radius n, as rasterized by the midpoint circle algorithm.

1, 5, 21, 37, 61, 97, 129, 177, 221, 277, 349, 413, 489, 569, 657, 749, 845, 957, 1073, 1193, 1313, 1441, 1581, 1733, 1877, 2025, 2209, 2369, 2553, 2725, 2909, 3117, 3305, 3513, 3721, 3941, 4181, 4405, 4645, 4889, 5145, 5401, 5653, 5941, 6213, 6493, 6769, 7065

Offset: 0

Author

Pontus von Brömssen, Feb 06 2021

Keywords

• nonn

Comments

The number of points on the rasterized circle itself (of radius n) is given by 4*A022846(n) for n > 0.

Examples

			In the figure below, the points on the rasterized circle of radius n are labeled with the number n. (Points without a label do not lie on any such circle.)
                9 9 9 9 9
            9 9 8 8 8 8 8 9 9
        9 9 8 8 7 7 7 7 7 8 8 9 9
      9 . 8 7 7 6 6 6 6 6 7 7 8 . 9
      9 8 7 . 6 5 5 5 5 5 6 . 7 8 9
    9 8 7 . 6 5 . 4 4 4 . 5 6 . 7 8 9
    9 8 7 6 5 4 4 3 3 3 4 4 5 6 7 8 9
  9 8 7 6 5 . 4 3 2 2 2 3 4 . 5 6 7 8 9
  9 8 7 6 5 4 3 2 . 1 . 2 3 4 5 6 7 8 9
  9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9
  9 8 7 6 5 4 3 2 . 1 . 2 3 4 5 6 7 8 9
  9 8 7 6 5 . 4 3 2 2 2 3 4 . 5 6 7 8 9
    9 8 7 6 5 4 4 3 3 3 4 4 5 6 7 8 9
    9 8 7 . 6 5 . 4 4 4 . 5 6 . 7 8 9
      9 8 7 . 6 5 5 5 5 5 6 . 7 8 9
      9 . 8 7 7 6 6 6 6 6 7 7 8 . 9
        9 9 8 8 7 7 7 7 7 8 8 9 9
            9 9 8 8 8 8 8 9 9
                9 9 9 9 9
Counting the points on or inside a circle of given radius, one obtains a(0)=1, a(1)=5, a(2)=21, a(3)=37, a(4)=61, a(5)=97, ...
		

Links

• Eric Weisstein's World of Mathematics, Gauss's Circle Problem
• Wikipedia, Midpoint circle algorithm

Crossrefs

First differences: A341199.

Cf. A022846, A055979, A057655, A373193.

Programs

Python

def A341198(n):
  n2=n**2
  x=n
  y=A=0
  while y<=x:
    dx=x**2+(y+1)**2-n2-x>=0
    A+=x+(y!=0 and y!=x)*(x-2*y)+(dx and y==x-1)*(x-1)
    x-=dx
    y+=1
  return 4*A+1

Formula

a(n) == 1 (mod 4).

a(n) ~ Pi*n^2. More precisely, it is reasonable to expect that a(n) = Pi*n^2 + sqrt(8)*n + o(n), because there are Pi*n^2 + o(n) points in the disk x^2 + y^2 <= n^2 (Gauss's circle problem), all of which are inside the rasterized circle, and we can expect about half of the 4*sqrt(2)*n + O(1) points on the rasterized circle itself to be outside this disk (and there are no points between the disk and the rasterized circle).