|
|
A000050
|
|
Number of positive integers <= 2^n of form x^2 + y^2.
(Formerly M0715 N0265)
|
|
7
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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
|
|
|
EXAMPLE
|
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
|
|
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 *)
|
|
PROG
|
(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]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|