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,2

Comments

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

Links

Table of n, a(n) for n=0..47.

Eric Weisstein's World of Mathematics, Gauss's Circle Problem

Wikipedia, Midpoint circle algorithm

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).

Example

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, ...

Prog

(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

Crossrefs

First differences: A341199.

Cf. A022846, A055979, A057655.

Sequence in context: A170837 A170876 A373193 * A038844 A303521 A365767

Adjacent sequences: A341195 A341196 A341197 * A341199 A341200 A341201

Keyword

nonn

Author

Pontus von Brömssen, Feb 06 2021

Status

approved