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