|
%I #21 Jun 09 2021 02:38:52
%S 1,5,21,37,61,97,129,177,221,277,349,413,489,569,657,749,845,957,1073,
%T 1193,1313,1441,1581,1733,1877,2025,2209,2369,2553,2725,2909,3117,
%U 3305,3513,3721,3941,4181,4405,4645,4889,5145,5401,5653,5941,6213,6493,6769,7065
%N Number of points on or inside the circle of radius n, as rasterized by the midpoint circle algorithm.
%C The number of points on the rasterized circle itself (of radius n) is given by 4*A022846(n) for n > 0.
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GausssCircleProblem.html">Gauss's Circle Problem</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Midpoint_circle_algorithm">Midpoint circle algorithm</a>
%F a(n) == 1 (mod 4).
%F 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).
%e 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.)
%e 9 9 9 9 9
%e 9 9 8 8 8 8 8 9 9
%e 9 9 8 8 7 7 7 7 7 8 8 9 9
%e 9 . 8 7 7 6 6 6 6 6 7 7 8 . 9
%e 9 8 7 . 6 5 5 5 5 5 6 . 7 8 9
%e 9 8 7 . 6 5 . 4 4 4 . 5 6 . 7 8 9
%e 9 8 7 6 5 4 4 3 3 3 4 4 5 6 7 8 9
%e 9 8 7 6 5 . 4 3 2 2 2 3 4 . 5 6 7 8 9
%e 9 8 7 6 5 4 3 2 . 1 . 2 3 4 5 6 7 8 9
%e 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9
%e 9 8 7 6 5 4 3 2 . 1 . 2 3 4 5 6 7 8 9
%e 9 8 7 6 5 . 4 3 2 2 2 3 4 . 5 6 7 8 9
%e 9 8 7 6 5 4 4 3 3 3 4 4 5 6 7 8 9
%e 9 8 7 . 6 5 . 4 4 4 . 5 6 . 7 8 9
%e 9 8 7 . 6 5 5 5 5 5 6 . 7 8 9
%e 9 . 8 7 7 6 6 6 6 6 7 7 8 . 9
%e 9 9 8 8 7 7 7 7 7 8 8 9 9
%e 9 9 8 8 8 8 8 9 9
%e 9 9 9 9 9
%e 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, ...
%o (Python)
%o def A341198(n):
%o n2=n**2
%o x=n
%o y=A=0
%o while y<=x:
%o dx=x**2+(y+1)**2-n2-x>=0
%o A+=x+(y!=0 and y!=x)*(x-2*y)+(dx and y==x-1)*(x-1)
%o x-=dx
%o y+=1
%o return 4*A+1
%Y First differences: A341199.
%Y Cf. A022846, A055979, A057655.
%K nonn
%O 0,2
%A _Pontus von Brömssen_, Feb 06 2021
| 