A057655 The circle problem: number of points (x,y) in square lattice with x^2 + y^2 <= n.
1, 5, 9, 9, 13, 21, 21, 21, 25, 29, 37, 37, 37, 45, 45, 45, 49, 57, 61, 61, 69, 69, 69, 69, 69, 81, 89, 89, 89, 97, 97, 97, 101, 101, 109, 109, 113, 121, 121, 121, 129, 137, 137, 137, 137, 145, 145, 145, 145, 149, 161, 161, 169, 177, 177, 177
Offset: 0
Examples
a(0) = 1 (counting origin). a(1) = 5 since 4 points lie on the circle of radius sqrt(1) + origin. 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
References
- C. Alsina and R. B. Nelsen, Charming Proofs: A Journey Into Elegant Mathematics, Math. Assoc. Amer., 2010, p. 42.
- J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag, p. 106.
- F. Fricker, Einfuehrung in die Gitterpunktlehre, Birkhäuser, Boston, 1982.
- P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 5.
- E. Kraetzel, Lattice Points, Kluwer, Dordrecht, 1988.
- C. D. Olds, A. Lax and G. P. Davidoff, The Geometry of Numbers, Math. Assoc. Amer., 2000, p. 51.
- W. Sierpiński, Elementary Theory of Numbers, Elsevier, North-Holland, 1988.
- James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 245-246.
Links
- T. D. Noe, Table of n, a(n) for n = 0..1000
- Pierre de la Harpe, On the prehistory of growth of groups, arXiv:2106.02499 [math.GR], 2021.
- F. Richman, Counting Gaussian integers in a disk
- W. Sierpiński, Elementary Theory of Numbers, Warszawa 1964.
Crossrefs
Programs
-
Haskell
a057655 n = length [(x,y) | x <- [-n..n], y <- [-n..n], x^2 + y^2 <= n] -- Reinhard Zumkeller, Jan 23 2012
-
Maple
N:= 1000: # to get a(0) to a(N) R:= Array(0..N): for a from 0 to floor(sqrt(N)) do for b from 0 to floor(sqrt(N-a^2)) do r:= a^2 + b^2; R[r]:= R[r] + (2 - charfcn[0](a))*(2 - charfcn[0](b)); od od: convert(map(round,Statistics:-CumulativeSum(R)),list); # Robert Israel, Sep 29 2014 -
Mathematica
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 *) Accumulate[ SquaresR[2, Range[0, 55]]] (* Jean-François Alcover, Feb 24 2012 *) CoefficientList[Series[EllipticTheta[3,0,x]^2/(1-x), {x, 0, 100}], x] (* Vaclav Kotesovec, Sep 29 2014 after Robert Israel *) -
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)))
-
PARI
a(n)=1+4*sum(k=0,sqrtint(n), sqrtint(n-k^2) ); /* Benoit Cloitre, Oct 08 2012 */
-
Python
from math import isqrt def A057655(n): return 1+(sum(isqrt(n-k**2) for k in range(isqrt(n)+1))<<2) # Chai Wah Wu, Jul 31 2023
Formula
a(n) = 1 + 4*{ [n/1] - [n/3] + [n/5] - [n/7] + ... }. - Gauss
a(n) = 1 + 4*Sum_{ k = 0 .. [sqrt(n)] } [ sqrt(n-k^2) ]. - Liouville (?)
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.
a(n) = A014198(n) + 1.
a(n) = A122510(2,n). - R. J. Mathar, Apr 21 2010
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
G.f.: theta_3(0,x)^2/(1-x) where theta_3 is a Jacobi theta function. - Robert Israel, Sep 29 2014
a(n^2) = A000328(n). - R. J. Mathar, Aug 03 2025