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,2

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.

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.

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) = 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

Example

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

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 *)

Prog

(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 */
(Haskell)
a057655 n = length [(x, y) | x <- [-n..n], y <- [-n..n], x^2 + y^2 <= n]
-- Reinhard Zumkeller, Jan 23 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

Crossrefs

Partial sums of A004018. Cf. A057656, A057961, A057962. For another version see A000328.

A014198(n) + 1.

Sequence in context: A073168 A315121 A127500 * A175374 A141124 A209534

Adjacent sequences: A057652 A057653 A057654 * A057656 A057657 A057658

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Oct 15 2000

Status

approved