A000047 Number of integers <= 2^n of form x^2 - 2y^2.

1, 2, 3, 5, 8, 15, 26, 48, 87, 161, 299, 563, 1066, 2030, 3885, 7464, 14384, 27779, 53782, 104359, 202838, 394860, 769777, 1502603, 2936519, 5744932, 11249805, 22048769, 43248623, 84894767, 166758141, 327770275, 644627310, 1268491353, 2497412741

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Examples

			There are 5 integers <= 2^3 of form x^2 - 2y^2. The five (x,y) pairs (1,0), (2,1), (2,0), (3,1), (4,2) give respectively: 1, 2, 4, 7, 8. So a(3) = 5. - _Bernard Schott_, Feb 10 2019
		

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 Ray Chandler, 36..37 from Pontus von Brömssen)
• D. Borwein, J. M. Borwein, P. B. Borwein, R. Girgensohn, Giuga's Conjecture on Primality, Am. Math. Monthly 103 (1) (1996), 40-50.
• D. Shanks and L. P. Schmid, Variations on a theorem of Landau. Part I, Math. Comp., 20 (1966), 551-569.
• Index entries for sequences related to populations of quadratic forms
• Seth A. Troisi, C++ and Python programs

Crossrefs

Cf. A035251.

Programs

Mathematica

cnt=0; n=0; Table[n++; While[{p,e}=Transpose[FactorInteger[n]]; If[Select[p^e, MemberQ[{3,5}, Mod[ #,8]] &] == {}, cnt++ ]; n<2^k, n++ ]; cnt, {k,0,20}] (* T. D. Noe, Jan 19 2009 *)

PARI

A000047(n)={ local(f,c=0); for(m=1,2^n, for(i=1,#f=factor(m)~, abs(f[1,i]%8-4)==1 || next; f[2,i]%2 & next(2));c++);c} \\ See comment in A035251: m=3 or 5 mod 8; M. F. Hasler, Jan 19 2009

Extensions

More terms from Giovanni Resta and Harry J. Smith, Jan 24 2009