|
%I M0715 N0265 #40 Dec 19 2022 10:17:28
%S 1,2,3,5,9,16,29,54,97,180,337,633,1197,2280,4357,8363,16096,31064,
%T 60108,116555,226419,440616,858696,1675603,3273643,6402706,12534812,
%U 24561934,48168461,94534626,185661958,364869032,717484560,1411667114,2778945873,5473203125
%N Number of positive integers <= 2^n of form x^2 + y^2.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Seth A. Troisi, <a href="/A000050/b000050.txt">Table of n, a(n) for n = 0..50</a> (terms 0..35 from N. J. A. Sloane)
%H P. Moree and H. J. J. te Riele, <a href="https://arxiv.org/abs/math/0204332">The hexagonal versus the square lattice</a>, arXiv:math/0204332 [math.NT], 2002.
%H P. Moree and H. J. J. te Riele, <a href="http://dx.doi.org/10.1090/S0025-5718-03-01556-4">The hexagonal versus the square lattice</a>, Math. Comp. 73 (2004), no. 245, 451-473.
%H D. Shanks and L. P. Schmid, <a href="http://dx.doi.org/10.1090/S0025-5718-1966-0210678-1">Variations on a theorem of Landau. Part I</a>, Math. Comp., 20 (1966), 551-569.
%H Seth A. Troisi, <a href="https://github.com/sethtroisi/OEIS/tree/main/A000050">C++ program</a>
%H <a href="/index/Qua#quadpop">Index entries for sequences related to populations of quadratic forms</a>
%e 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
%t (* 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 *)
%o (Haskell)
%o isqrt = a000196
%o issquare = a010052
%o a000050 n = foldl f 0 [1..2^n]
%o where f i j = if a000050' j > 0 then i + 1 else i
%o a000050' k = foldl f 0 (h k)
%o where f i y = g y + i
%o where g y = issquare (k - y^2)
%o h k = [0..isqrt k]
%o -- _James Spahlinger_, Oct 09 2012
%Y Cf. A001481.
%K nonn
%O 0,2
%A _N. J. A. Sloane_
|
