A000050 Number of positive integers <= 2^n of form x^2 + y^2.
1, 2, 3, 5, 9, 16, 29, 54, 97, 180, 337, 633, 1197, 2280, 4357, 8363, 16096, 31064, 60108, 116555, 226419, 440616, 858696, 1675603, 3273643, 6402706, 12534812, 24561934, 48168461, 94534626, 185661958, 364869032, 717484560, 1411667114, 2778945873, 5473203125
Offset: 0
Keywords
Examples
There are 5 integers <= 2^3 of the form x^2 + y^2. The five (x,y) pairs (x <= y) are (0,1), (1,1), (0,2), (1,2), (2,2) and give the integers 1, 2, 4, 5, 8, respectively. So a(3) = 5. - _Seth A. Troisi_, Apr 27 2022
References
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Seth A. Troisi, Table of n, a(n) for n = 0..50 (terms 0..35 from N. J. A. Sloane)
- P. Moree and H. J. J. te Riele, The hexagonal versus the square lattice, arXiv:math/0204332 [math.NT], 2002.
- P. Moree and H. J. J. te Riele, The hexagonal versus the square lattice, Math. Comp. 73 (2004), no. 245, 451-473.
- D. Shanks and L. P. Schmid, Variations on a theorem of Landau. Part I, Math. Comp., 20 (1966), 551-569.
- Seth A. Troisi, C++ program
- Index entries for sequences related to populations of quadratic forms
Crossrefs
Cf. A001481.
Programs
-
Haskell
isqrt = a000196 issquare = a010052 a000050 n = foldl f 0 [1..2^n] where f i j = if a000050' j > 0 then i + 1 else i a000050' k = foldl f 0 (h k) where f i y = g y + i where g y = issquare (k - y^2) h k = [0..isqrt k] -- James Spahlinger, Oct 09 2012 -
Mathematica
(* This program is not suitable for a large number of terms *) a[0] = 1; a[n_] := a[n] = (For[cnt = 0; k = 2^(n-1)+1, k <= 2^n, k++, If[SquaresR[2, k] > 0, cnt++]]; cnt + a[n-1]); Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 26}] (* Jean-François Alcover, Mar 20 2014 *)