A004215 -id:A004215 - cp's OEIS frontend

A124966 Numbers which can be expressed as the ordered sum of 3 squares in 2 or more different ways.

9, 17, 18, 25, 26, 27, 29, 33, 34, 36, 38, 41, 45, 49, 50, 51, 53, 54, 57, 59, 61, 62, 65, 66, 68, 69, 72, 73, 74, 75, 77, 81, 82, 83, 85, 86, 89, 90, 94, 97, 98, 99, 100, 101, 102, 104, 105, 106, 107, 108, 109, 110, 113, 114, 116, 117, 118, 121, 122, 123, 125, 126, 129

Offset: 1

Artur Jasinski, Nov 14 2006

nonn

			a(1)=9 because 9 = 3^2 + 0^2 + 0^2 or 2^2 + 2^2 + 1^2.

Robert Price, Table of n, a(n) for n = 1..83131

Cf. A004215, A094942, A124967-A124971.

Select[Range[129], Length@PowersRepresentations[#, 3, 2] >= 2 &] (* Ray Chandler, Oct 31 2019 *)

Equals = A000027 - A094942 - A004215.

Corrected and extended by Ray Chandler, Nov 30 2006

A000419 Numbers that are the sum of 3 but no fewer nonzero squares.

Original entry on oeis.org

3, 6, 11, 12, 14, 19, 21, 22, 24, 27, 30, 33, 35, 38, 42, 43, 44, 46, 48, 51, 54, 56, 57, 59, 62, 66, 67, 69, 70, 75, 76, 77, 78, 83, 84, 86, 88, 91, 93, 94, 96, 99, 102, 105, 107, 108, 110, 114, 115, 118, 120, 123, 126, 129, 131, 132, 133, 134, 138, 139, 140, 141, 142

Offset: 1

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

A002828(a(n)) = 3; A025427(a(n)) > 0. - Reinhard Zumkeller, Feb 26 2015

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 311.

Ray Chandler, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Square Number.
Index entries for sequences related to sums of squares

Cf. A000378, A000408, A000415, A002828, A004215, A025427.

a000419 n = a000419_list !! (n-1)
a000419_list = filter ((== 3) . a002828) [1..]
-- Reinhard Zumkeller, Feb 26 2015

Select[Range[150],SquaresR[3,#]>0&&SquaresR[2,#]==0&] (* Harvey P. Dale, Nov 01 2011 *)

is(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]%2 && f[i, 1]%4==3, return( n/4^valuation(n,4)%8 !=7 ))); 0 \\ Charles R Greathouse IV, Feb 07 2017

def aupto(lim):
  squares = [k*k for k in range(1, int(lim**.5)+2) if k*k <= lim]
  sum2sqs = set(a+b for i, a in enumerate(squares) for b in squares[i:])
  sum3sqs = set(a+b for a in sum2sqs for b in squares)
  return sorted(set(range(lim+1)) & (sum3sqs - sum2sqs - set(squares)))
print(aupto(142)) # Michael S. Branicky, Mar 06 2021

Legendre: a nonnegative integer is a sum of three (or fewer) squares iff it is not of the form 4^k m with m == 7 (mod 8).

More terms from Arlin Anderson (starship1(AT)gmail.com)

A072401 1 iff n is of the form 4^m*(8k+7).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0

Offset: 0

Reinhard Zumkeller, Jun 16 2002

Characteristic function of A004215, indicating numbers not the sum of 3 integer squares.

a(n) + 1 is the smallest positive number such that (a(n) + 1) * n is the sum of three squares. - Peter Schorn, Jul 18 2023

Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197; preprint. See Example 20.
Eric Weisstein's World of Mathematics, Square Numbers.
Index entries for sequences related to sums of squares.
Index entries for characteristic functions.

Cf. A004215, A057427, A064873, A072400.

Cf. A071374.

A072400[n_] := Mod[If[Mod[n, 4] == 0, n/4^IntegerExponent[n, 4], n], 8];
a[n_] := 1 - Sign[7 - A072400[n]];
Table[a[n], {n, 0, 96}] (* Jean-François Alcover, Dec 13 2021 *)

a(n) = if(n, (n >> (2*valuation(n, 4))) % 8 == 7, 0); \\ Amiram Eldar, May 15 2025

def A072401(n): return ((m:=(~n&n-1).bit_length())&1^1)&int((n>>m)&7==7) # Chai Wah Wu, Aug 01 2023

a(n) = 1 - A057427(7 - A072400(n)).
a(A004215(k)) = 1 for k>0.
a(n) = A057427(A064873(n)).
For n<112: a(n) = A064873(n), but A064873(112) = 2, as also a(112 - 1) = 1.
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/6. - Amiram Eldar, May 15 2025

A055039 Numbers of the form 2^(2i+1)*(8j+7).

Original entry on oeis.org

14, 30, 46, 56, 62, 78, 94, 110, 120, 126, 142, 158, 174, 184, 190, 206, 222, 224, 238, 248, 254, 270, 286, 302, 312, 318, 334, 350, 366, 376, 382, 398, 414, 430, 440, 446, 462, 478, 480, 494, 504, 510, 526, 542, 558, 568, 574, 590, 606, 622

Offset: 1

N. J. A. Sloane, Jun 01 2000

The numbers not of the form x^2+y^2+2z^2.
Numbers of the form 6*x^2 + 8*x^2*(2*y -1). (Steve Waterman).
These are the numbers not occurring as norms in the face-centered cubic lattice (cf. A004015).
Numbers whose base 4 representation ends in 3,2 followed by some number of zeros. - Franklin T. Adams-Watters, Dec 04 2006
Numbers k such that the k-th coefficient of eta(x)^4/eta(x^4) is 0 where eta is the Dedekind eta function. - Benoit Cloitre, Mar 15 2025
The asymptotic density of this sequence is 1/12. - Amiram Eldar, Mar 29 2025

			In base 4: 32, 132, 232, 320, 332, 1032, 1132, 1232, 1320, 1332, 2032, ...

T. D. Noe, Table of n, a(n) for n=1..10000
L. E. Dickson, Integers represented by positive ternary quadratic forms, Bull. Amer. Math. Soc. 33 (1927), 63-70.
L. J. Mordell, A new Waring's problem with squares of linear forms, Quart. J. Math., 1 (1930), 276-288 (see p. 283).
Steve Waterman, Missing numbers formula.

Equals twice A004215. Not the same as A044075 - see A124169.
Complement of A000401.
Cf. A004015.

Select[Range[650], Mod[# / 4^IntegerExponent[#, 4], 16] == 14 &] (* Amiram Eldar, Mar 29 2025 *)

from itertools import count, islice
def A055039_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:(m:=(~n&n-1).bit_length())&1 and (n>>m)&7==7,count(max(startvalue,1)))
A055039_list = list(islice(A055039_gen(),30)) # Chai Wah Wu, Jul 09 2022

def A055039(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(((x>>i)-7>>3)+1 for i in range(1,x.bit_length(),2))
    return bisection(f,n,n) # Chai Wah Wu, Feb 24 2025

A047449 Numbers that are primitively represented by x^2 + y^2 + z^2.

Original entry on oeis.org

1, 2, 3, 5, 6, 9, 10, 11, 13, 14, 17, 18, 19, 21, 22, 25, 26, 27, 29, 30, 33, 34, 35, 37, 38, 41, 42, 43, 45, 46, 49, 50, 51, 53, 54, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 73, 74, 75, 77, 78, 81, 82, 83, 85, 86, 89, 90, 91, 93, 94, 97, 98, 99, 101, 102, 105, 106

Offset: 1

N. J. A. Sloane

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1)

Cf. A000378, A004215, A034043-A034047.

LinearRecurrence[{1,0,0,0,1,-1},{1,2,3,5,6,9},70] (* Harvey P. Dale, Mar 05 2015 *)

a(n)=(n-1)\5*8+[6,1,2,3,5][n%5+1] \\ Charles R Greathouse IV, Jun 11 2015

Numbers that are congruent to {1, 2, 3, 5, 6} mod 8.
Union of A047449 and A034045 is A000378. Intersection of A047449 and A034043 is A034046. Numbers that are in A000378 and not congruent to 0 mod 4. - Ray Chandler, Sep 05 2004
G.f.: x*(1 + x + x^2 + 2*x^3 + x^4 + 2*x^5) / ( (x^4 + x^3 + x^2 + x + 1)*(x-1)^2 ). - R. J. Mathar, Dec 07 2011
a(n) = a(n-1) + a(n-5) - a(n-6); a(1)=1, a(2)=2, a(3)=3, a(4)=5, a(5)=6, a(6)=9. - Harvey P. Dale, Mar 05 2015

A055046 Numbers of the form 4^i(8j+3).

Original entry on oeis.org

3, 11, 12, 19, 27, 35, 43, 44, 48, 51, 59, 67, 75, 76, 83, 91, 99, 107, 108, 115, 123, 131, 139, 140, 147, 155, 163, 171, 172, 176, 179, 187, 192, 195, 203, 204, 211, 219, 227, 235, 236, 243, 251, 259, 267, 268, 275, 283, 291, 299, 300, 304, 307, 315, 323, 331, 332

Offset: 1

N. J. A. Sloane, Jun 01 2000

Numbers not of the form x^2+y^2+5z^2.

Also values of n such that numbers of the form x^2+n*y^2 for some integers x, y cannot have prime factor of 2 raised to an odd power. - V. Raman, Dec 18 2013

Paolo Xausa, Table of n, a(n) for n = 1..10000
L. J. Mordell, A new Waring's problem with squares of linear forms, Quart. J. Math., 1 (1930), 276-288 (see p. 283).

Cf. A004215, A055043, A055045, A055047, A233998, A233999, A234000.

A055046Q[k_] := Mod[k/4^IntegerExponent[k, 4], 8] == 3;
Select[Range[500], A055046Q] (* Paolo Xausa, Mar 20 2025 *)

is(n)=n/=4^valuation(n,4); n%8==3 \\ Charles R Greathouse IV and V. Raman, Dec 19 2013

from itertools import count, islice
def A055046_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:not (m:=(~n&n-1).bit_length())&1 and (n>>m)&7==3,count(max(startvalue,1)))
A055046_list = list(islice(A055046_gen(),30)) # Chai Wah Wu, Jul 09 2022

def A055046(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(((x>>(i<<1))-3>>3)+1 for i in range(x.bit_length()>>1))
    return bisection(f,n,n) # Chai Wah Wu, Feb 14 2025

a(n) = 6n + O(log n). - Charles R Greathouse IV, Dec 19 2013

a(n) = A055043(n)/2. - Chai Wah Wu, Mar 19 2025

A113505 Numbers not the sum of at most three perfect powers (A001597).

Original entry on oeis.org

7, 15, 23, 87, 111, 119, 167, 335, 1391, 1455, 1607, 1679, 1991, 25887, 26375

Offset: 1

R. P. van der Hilst (R.P.vanderHilst(AT)students.uu.nl), Jan 12 2006

Cannot be written in the form a^x + b^y + c^z with a, b, c >= 0 and x, y, z > 1.
a(16), if it exists, is larger than 10^8. - Giovanni Resta, May 07 2017
From Brian Trial, Jun 07 2025: (Start)
Per Legendre's three-square theorem (A004215) only integers of the form 4^i(8j+7) are eligible.
Every integer > 5042631 (= 1424^2 + 734*2 + 19^5) and < 10^9 can be expressed as either a^2 + b^2 + c^2 or a^2 + b^2 + c^3, a,b,c >= 0 so a(16) >= 10^9. (End)

Eric Weisstein's World of Mathematics, Perfect Power
Eric Weisstein's World of Mathematics, Powerful Number.

A056828 is a subset, A001694, A274459.

lmt = 40000; s = Union@ Join[{0, 1}, Flatten@ Table[n^i, {n, 2, Sqrt@ lmt}, {i, 2, Log[n, lmt]}]]; t = Select[ Union[Plus @@@ Tuples[s, 3]], # < lmt + 1 &]; Complement[Range@ lmt, t] (* Robert G. Wilson v *)

Edited by Robert G. Wilson v, May 01 2006

A119869 Sizes of successive clusters in f.c.c. lattice centered at a lattice point.

Original entry on oeis.org

1, 13, 19, 43, 55, 79, 87, 135, 141, 177, 201, 225, 249, 321, 321, 369, 381, 429, 459, 531, 555, 603, 627, 675, 683, 767, 791, 887, 935, 959, 959, 1055, 1061, 1157, 1205, 1253, 1289, 1409, 1433, 1481, 1505, 1553, 1601, 1721, 1745, 1865, 1865, 1961, 1985, 2093, 2123

Offset: 0

Hugo Pfoertner, May 26 2006

N. J. A. Sloane and B. K. Teo, Theta series and magic numbers for close-packed spherical clusters, J. Chem. Phys. 83 (1985) 6520-6534.

N. J. A. Sloane, Table of n, a(n) for n = 0..9999
Paul Bourke, Waterman Polyhedra.
Paul Bourke, On-line generator
Martin Kraus, Live Graphics3d
Mirek Majewski, Dedicated commands in MuPAD
Wouter Meeussen, ConvexHull3D package & demo-file.
Mark Newbold, Waterman Polyhedra. CCPOLY Java Applet.
Steve Waterman, Waterman Polyhedron.
Steve Waterman, Missing numbers formula

Cf. A004015, A004215, A055039.

Cf. A055039 [missing polyhedra]. Properties of Waterman polyhedra: A119870 [vertices], A119871 [faces], A119872 [edges], A119873 [volume]. Waterman polyhedra with different centers: A119874, A119875, A119876, A119877, A119878.

maxd:=20001: read format: temp0:=trunc(evalf(sqrt(maxd)))+2: a:=0: for i from -temp0 to temp0 do a:=a+q^( (i+1/2)^2): od: th2:=series(a,q,maxd): a:=0: for i from -temp0 to temp0 do a:=a+q^(i^2): od: th3:=series(a,q,maxd): th4:=series(subs(q=-q,th3),q,maxd):
t1:=series((th3^3+th4^3)/2,q,maxd): t1:=series(subs(q=sqrt(q),t1),q,floor(maxd/2)): t2:=seriestolist(t1): t4:=0; for n from 1 to nops(t2) do t4:=t4+t2[n]; lprint(n-1, t4); od: # N. J. A. Sloane, Aug 09 2006

a[n_] := Sum[SquaresR[3, 2k], {k, 0, n}]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jul 12 2012, after formula *)
Accumulate[SquaresR[3,2*Range[0,70]]] (* Harvey P. Dale, Jun 01 2015 *)

Partial sums of A004015, which has an explicit generating function.

Edited by N. J. A. Sloane, Aug 09 2006

Additional links from Steve Waterman, Nov 26 2006

A006892 Representation as a sum of squares requires n squares with greedy algorithm.

Original entry on oeis.org

1, 2, 3, 7, 23, 167, 7223, 13053767, 42600227803223, 453694852221687377444001767, 51459754733114686962148583993443846186613037940783223

Offset: 1

Jeffrey Shallit

nonn

Of course Lagrange's theorem tells us that any positive integer can be written as a sum of at most four squares (cf. A004215).

Records in A053610. - Hugo van der Sanden, Jun 24 2015

			Here is why a(5) = 23: start with 23, subtract largest square <= 23, which is 16, getting 7.
Now subtract largest square <= 7, which is 4, getting 3.
Now subtract largest square <= 3, which is 1, getting 2.
Now subtract largest square <= 2, which is 1, getting 1.
Now subtract largest square <= 1, which is 1, getting 0.
Thus 23 = 16+4+1+1+1.
It took 5 steps to get to 0, and 23 is the smallest number which takes 5 steps. - _N. J. A. Sloane_, Jan 29 2014

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Rick L. Shepherd, Table of n, a(n) for n = 1..15
Art of Problem Solving, 2010 AMC 10A Problems/Problem 25 [From _Rick L. Shepherd_, Jan 28 2014]
E. Lemoine, Décomposition d'un nombre entier N en ses puissances nièmes maxima, C. R. Acad. Sci. Paris, Vol. 95, pp. 719-722, 1882 (then next pages).
E. Lemoine, Sur la décomposition d'un nombre en ses carrés maxima, Assoc. Française pour L'Avancement des Sciences (1896), 73-77.

Cf. A004215, A053610.

a(n) = if (n <= 3, n , ((a(n-1)+3)/2)^2 - 2) \\ Michel Marcus, May 25 2013

For n >= 4, a(n) = a(n-1) + ((a(n-1)+1)/2)^2. - Joe K. Crump (joecr(AT)carolina.rr.com), Apr 16 2000
a(n) = n for n <= 3; for n > 3, a(n) = ((a(n-1)+3)/2)^2 - 2. - Arkadiusz Wesolowski, Mar 30 2013
a(n+2) = 2 * A053630(n) - 3. - Thomas Ordowski, Jul 14 2014
a(n+3) = A053630(n)^2 - 2. - Thomas Ordowski, Jul 19 2014

Four more terms from Rick L. Shepherd, Jan 27 2014

A034043 Numbers that are imprimitively represented by x^2+y^2+z^2.

Original entry on oeis.org

0, 4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 64, 68, 72, 75, 76, 80, 81, 84, 88, 90, 96, 98, 99, 100, 104, 108, 116, 117, 120, 121, 125, 126, 128, 132, 136, 140, 144, 147, 148, 150, 152, 153, 160, 162, 164, 168, 169

Offset: 1

N. J. A. Sloane

nonn

Cf. A000378, A004215, A047449, A034044-A034047.

Union of A034043 and A034044 is A000378. Intersection of A047449 and A034043 is A034046. Numbers that are in A000378 and not squarefree. - Ray Chandler, Sep 05 2004

cp's OEIS Frontend

A124966 Numbers which can be expressed as the ordered sum of 3 squares in 2 or more different ways.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A000419 Numbers that are the sum of 3 but no fewer nonzero squares.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

Extensions

A072401 1 iff n is of the form 4^m*(8k+7).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A055039 Numbers of the form 2^(2i+1)*(8j+7).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Python

A047449 Numbers that are primitively represented by x^2 + y^2 + z^2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055046 Numbers of the form 4^i*(8*j+3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula

A113505 Numbers not the sum of at most three perfect powers (A001597).

Views

Author

Keywords

Comments

Links

A055046 Numbers of the form 4^i(8j+3).