A000408 Numbers that are the sum of three nonzero squares.

3, 6, 9, 11, 12, 14, 17, 18, 19, 21, 22, 24, 26, 27, 29, 30, 33, 34, 35, 36, 38, 41, 42, 43, 44, 45, 46, 48, 49, 50, 51, 53, 54, 56, 57, 59, 61, 62, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 81, 82, 83, 84, 86, 88, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 104

Offset: 1

Author

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

Keywords

• nonn

Comments

a(n) !== 7 (mod 8). - Boris Putievskiy, May 05 2013

A025427(a(n)) > 0. - Reinhard Zumkeller, Feb 26 2015

According to Halter-Koch (below), a number n is a sum of 3 squares, but not a sum of 3 nonzero squares (i.e., is in A000378 but not A000408), if and only if it is of the form 4^j*s, where j >= 0 and s in {1,2,5,10,13,25,37,58,85,130,?}, where ? denotes at most one unknown number that, if it exists, is > 5*10^10. - Jeffrey Shallit, Jan 15 2017

References

• L. E. Dickson, History of the Theory of Numbers, vol. II: Diophantine Analysis, Dover, 2005, p. 267.
• Savin Réalis, Answer to question 25 ("Toute puissance entière de 3 est une somme de trois carrés premiers avec 3"), Mathesis 1 (1881), pp. 87-88. (See also p. 73 where the question is posed.)

Links

• Ray Chandler, Table of n, a(n) for n = 1..10000
• Alexander Berkovich and Will Jagy, On representation of an integer as the sum of three squares and the ternary quadratic forms with the discriminants p^2, 16p^2, arXiv:1101.2951 [math.NT], 2011.
• B. Farhi, On the Representation of the Natural Numbers as the Sum of Three Terms of the Sequence floor(n^2/a), J. Int. Seq. 16 (2013) #13.6.4.
• Franz Halter-Koch, Darstellung natürlicher Zahlen als Summe von Quadraten, Acta Arithmetica 42 (1982), pp. 11-20.
• S. Mezroui, A. Azizi, and M'hammed Ziane, On a Conjecture of Farhi , J. Int. Seq. 17 (2014) #14.1.8.
• Index entries for sequences related to sums of squares

Crossrefs

Cf. A000378, A000404, A000414, A003072, A004214, A024795, A024796, A025321, A025427.

Programs

Haskell

a000408 n = a000408_list !! (n-1)
a000408_list = filter ((> 0) . a025427) [1..]
-- Reinhard Zumkeller, Feb 26 2015

Maple

N:= 1000: # to get all terms <= N
S:= series((JacobiTheta3(0,q)-1)^3,q,1001):
select(t -> coeff(S,q,t)>0, [$1..N]); # Robert Israel, Jan 14 2016

Mathematica

f[n_] := Flatten[Position[Take[Rest[CoefficientList[Sum[x^(i^2), {i, n}]^3, x]], n^2], ?Positive]];f[11] (* _Ray Chandler, Dec 06 2006 *)
pr[n_] := Select[ PowersRepresentations[n, 3, 2], FreeQ[#, 0] &]; Select[ Range[104], pr[#] != {} &] (* Jean-François Alcover, Apr 04 2013 *)
max = 1000; s = (EllipticTheta[3, 0, q] - 1)^3 + O[q]^(max+1); Select[ Range[max], SeriesCoefficient[s, {q, 0, #}] > 0 &] (* Jean-François Alcover, Feb 01 2016, after Robert Israel *)

PARI

is(n)=for(x=sqrtint((n-1)\3)+1,sqrtint(n-2), for(y=1,sqrtint(n-x^2-1), if(issquare(n-x^2-y^2), return(1)))); 0 \\ Charles R Greathouse IV, Apr 04 2013

PARI

is(n)= my(a, b) ; a=1 ; while(a^2+1Altug Alkan, Jan 18 2016

Python

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)
print(aupto(104)) # Michael S. Branicky, Mar 06 2021

Formula

a(n) = 6n/5 + O(log n). - Charles R Greathouse IV, Mar 14 2014; error term improved Jul 05 2024