login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A057655 The circle problem: number of points (x,y) in square lattice with x^2 + y^2 <= n. 16
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 (list; graph; refs; listen; history; text; internal format)
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, Birkhaeuser, 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

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

CROSSREFS

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

A014198(n) + 1.

Sequence in context: A175363 A073168 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 09:32 EST 2018. Contains 299509 sequences. (Running on oeis4.)