|
%I #68 Jul 31 2023 12:01:03
%S 1,5,9,9,13,21,21,21,25,29,37,37,37,45,45,45,49,57,61,61,69,69,69,69,
%T 69,81,89,89,89,97,97,97,101,101,109,109,113,121,121,121,129,137,137,
%U 137,137,145,145,145,145,149,161,161,169,177,177,177
%N The circle problem: number of points (x,y) in square lattice with x^2 + y^2 <= n.
%D C. Alsina and R. B. Nelsen, Charming Proofs: A Journey Into Elegant Mathematics, Math. Assoc. Amer., 2010, p. 42.
%D J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag, p. 106.
%D F. Fricker, Einfuehrung in die Gitterpunktlehre, Birkhäuser, Boston, 1982.
%D P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 5.
%D E. Kraetzel, Lattice Points, Kluwer, Dordrecht, 1988.
%D C. D. Olds, A. Lax and G. P. Davidoff, The Geometry of Numbers, Math. Assoc. Amer., 2000, p. 51.
%D W. Sierpiński, Elementary Theory of Numbers, Elsevier, North-Holland, 1988.
%H T. D. Noe, <a href="/A057655/b057655.txt">Table of n, a(n) for n = 0..1000</a>
%H Pierre de la Harpe, <a href="https://arxiv.org/abs/2106.02499">On the prehistory of growth of groups</a>, arXiv:2106.02499 [math.GR], 2021.
%H F. Richman, <a href="http://math.fau.edu/Richman/gausdisk.htm">Counting Gaussian integers in a disk</a>
%H W. Sierpiński, <a href="http://matwbn.icm.edu.pl/kstresc.php?tom=42&wyd=10">Elementary Theory of Numbers</a>, Warszawa 1964.
%F a(n) = 1 + 4*{ [n/1] - [n/3] + [n/5] - [n/7] + ... }. - Gauss
%F a(n) = 1 + 4*Sum_{ k = 0 .. [sqrt(n)] } [ sqrt(n-k^2) ]. - Liouville (?)
%F a(n) - Pi*n = O(sqrt(n)) (Gauss). a(n) - Pi*n = O(n^c), c = 23/73 + epsilon ~ 0.3151 (Huxley). If a(n) - Pi*n = O(n^c) then c > 1/4 (Landau, Hardy). It is conjectured that a(n) - Pi*n = O(n^(1/4 + epsilon)) for all epsilon > 0.
%F a(n) = A122510(2,n). - _R. J. Mathar_, Apr 21 2010
%F a(n) = 1 + sum((floor(1/(k+1)) + 4 * floor(cos(Pi * sqrt(k))^2) - 4 * floor(cos(Pi * sqrt(k/2))^2) + 8 * sum((floor(cos(Pi * sqrt(i))^2) * floor(cos(Pi * sqrt(k-i))^2)), i = 1..floor(k/2))), k = 1..n). - _Wesley Ivan Hurt_, Jan 10 2013
%F G.f.: theta_3(0,x)^2/(1-x) where theta_3 is a Jacobi theta function. - _Robert Israel_, Sep 29 2014
%e a(0) = 1 (counting origin).
%e a(1) = 5 since 4 points lie on the circle of radius sqrt(1) + origin.
%e a(2) = 9 since 4 lattice points lie on the circle w/radius = sqrt(2) (along diagonals) + 4 points inside the circle + origin. - _Wesley Ivan Hurt_, Jan 10 2013
%p N:= 1000: # to get a(0) to a(N)
%p R:= Array(0..N):
%p for a from 0 to floor(sqrt(N)) do
%p for b from 0 to floor(sqrt(N-a^2)) do
%p r:= a^2 + b^2;
%p R[r]:= R[r] + (2 - charfcn[0](a))*(2 - charfcn[0](b));
%p od
%p od:
%p convert(map(round,Statistics:-CumulativeSum(R)),list); # _Robert Israel_, Sep 29 2014
%t f[n_] := 1 + 4Sum[ Floor@ Sqrt[n - k^2], {k, 0, Sqrt[n]}]; Table[ f[n], {n, 0, 60}] (* _Robert G. Wilson v_, Jun 16 2006 *)
%t Accumulate[ SquaresR[2, Range[0, 55]]] (* _Jean-François Alcover_, Feb 24 2012 *)
%t CoefficientList[Series[EllipticTheta[3,0,x]^2/(1-x), {x, 0, 100}], x] (* _Vaclav Kotesovec_, Sep 29 2014 after _Robert Israel_ *)
%o (PARI) a(n)=sum(x=-n,n,sum(y=-n,n,if((sign(x^2+y^2-n)+1)*sign(x^2+y^2-n),0,1)))
%o (PARI) a(n)=1+4*sum(k=0,sqrtint(n), sqrtint(n-k^2) ); /* _Benoit Cloitre_, Oct 08 2012 */
%o (Haskell)
%o a057655 n = length [(x,y) | x <- [-n..n], y <- [-n..n], x^2 + y^2 <= n]
%o -- _Reinhard Zumkeller_, Jan 23 2012
%o (Python)
%o from math import isqrt
%o def A057655(n): return 1+(sum(isqrt(n-k**2) for k in range(isqrt(n)+1))<<2) # _Chai Wah Wu_, Jul 31 2023
%Y Partial sums of A004018. Cf. A057656, A057961, A057962. For another version see A000328.
%Y A014198(n) + 1.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_, Oct 15 2000
|
