A000534 Numbers that are not the sum of 4 nonzero squares.

0, 1, 2, 3, 5, 6, 8, 9, 11, 14, 17, 24, 29, 32, 41, 56, 96, 128, 224, 384, 512, 896, 1536, 2048, 3584, 6144, 8192, 14336, 24576, 32768, 57344, 98304, 131072, 229376, 393216, 524288, 917504, 1572864, 2097152, 3670016, 6291456, 8388608, 14680064

Offset: 1

Author

N. J. A. Sloane and J. H. Conway

Keywords

• nonn
• easy
• nice

Comments

For n > 15, a(n) = A006431(n-1). - Thomas Ordowski, Nov 18 2012

References

• J. H. Conway, The Sensual (Quadratic) Form, M.A.A., 1997, p. 140.
• L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 2, p. 302.
• E. Grosswald, Representations of Integers as Sums of Squares. Springer-Verlag, NY, 1985, Theorem 3, pp. 74-75.

Links

• T. D. Noe, Table of n, a(n) for n = 1..100
• Brennan Benfield and Oliver Lippard, Integers that are not the sum of positive powers, arXiv:2404.08193 [math.NT], 2024. See p. 2.
• Pierre de la Harpe, Lagrange et la variation des théorèmes, Images des Mathématiques, CNRS, 2014.
• Index entries for linear recurrences with constant coefficients, signature (0,0,4).
• Index entries for sequences related to sums of squares

Crossrefs

Cf. A123069, A000414 (complement).

Programs

Mathematica

q=22;lst={};Do[Do[Do[Do[z=a^2+b^2+c^2+d^2;If[z<=q^2+3,AppendTo[lst,z]],{d,q}],{c,q}],{b,q}],{a,q}];lst1=Union@lst lst={};Do[AppendTo[lst,n],{n,q^2+3}];lst2=lst Complement[lst2,lst1] (* Vladimir Joseph Stephan Orlovsky, Feb 07 2010 *)
Join[{0,1,2,3,5,6,8,9,11,14,17,24,29,32,41}, LinearRecurrence[{0, 0, 4}, {56, 96, 128}, 30]] (* Jean-François Alcover, Feb 09 2016 *)

PARI

for(n=1,224,if(sum(a=1,n,sum(b=1,a,sum(c=1,b,sum(d=1,c,if(a^2+b^2+c^2+d^2-n,0,1)))))==0,print1(n,",")))

PARI

{a(n)=if( n<2, 0, n<16, [1, 2, 3, 5, 6, 8, 9, 11, 14, 17, 24, 29, 32, 41][n-1], [4, 7, 12][n%3+1] * 2^(n\3*2-7))}; /* Michael Somos, Apr 23 2006 */

PARI

is(n)=my(k=if(n,n/4^valuation(n,4),2)); k==2 || k==6 || k==14 || setsearch([0, 1, 3, 5, 9, 11, 17, 29, 41], n) \\ Charles R Greathouse IV, Sep 03 2014

Python

from itertools import count, islice
def A000534_gen(startvalue=0): # generator of terms >= startvalue
    return filter(lambda n:n in {0, 1, 3, 5, 9, 11, 17, 29, 41} or n>>((~n&n-1).bit_length()&-2) in {2,6,14},count(max(startvalue,0)))
A000534_list = list(islice(A000534_gen(),30)) # Chai Wah Wu, Jul 09 2022

Formula

Consists of the numbers 0, 1, 3, 5, 9, 11, 17, 29, 41, 2*4^m, 6*4^m and 14*4^m (m >= 0). Compare A123069.

From 224 on, a(n) = 4*a(n-3).

Numbers n such that A025428(n) = 0.

G.f.: x^2*(36*x^16 + 32*x^15 + 60*x^14 + 55*x^13 + 36*x^12 + 27*x^11 + 20*x^10 + 19*x^9 + 18*x^8 + 13*x^7 + 11*x^6 + 4*x^5 + 2*x^4 - x^3 - 3*x^2 - 2*x - 1)/(4*x^3 - 1). - Chai Wah Wu, Jul 09 2022