login
A341198
Number of points on or inside the circle of radius n, as rasterized by the midpoint circle algorithm.
3
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
Eric Weisstein's World of Mathematics, Gauss's Circle Problem
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.
Sequence in context: A170837 A170876 A373193 * A038844 A303521 A365767
KEYWORD
nonn
AUTHOR
STATUS
approved