cp's OEIS Frontend

A000408 Numbers that are the sum of three nonzero squares.

%I A000408 #112 Jul 06 2024 01:32:51
%S A000408 3,6,9,11,12,14,17,18,19,21,22,24,26,27,29,30,33,34,35,36,38,41,42,43,
%T A000408 44,45,46,48,49,50,51,53,54,56,57,59,61,62,65,66,67,68,69,70,72,73,74,
%U A000408 75,76,77,78,81,82,83,84,86,88,89,90,91,93,94,96,97,98,99,101,102,104
%N A000408 Numbers that are the sum of three nonzero squares.
%C A000408 a(n) !== 7 (mod 8). - _Boris Putievskiy_, May 05 2013
%C A000408 A025427(a(n)) > 0. - _Reinhard Zumkeller_, Feb 26 2015
%C A000408 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
%D A000408 L. E. Dickson, History of the Theory of Numbers, vol. II:  Diophantine Analysis, Dover, 2005, p. 267.
%D A000408 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.)
%H A000408 Ray Chandler, <a href="/A000408/b000408.txt">Table of n, a(n) for n = 1..10000</a>
%H A000408 Alexander Berkovich and Will Jagy, <a href="http://arxiv.org/abs/1101.2951">On representation of an integer as the sum of three squares and the ternary quadratic forms with the discriminants p^2, 16p^2</a>, arXiv:1101.2951 [math.NT], 2011.
%H A000408 B. Farhi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Farhi/farhi7.html">On the Representation of the Natural Numbers as the Sum of Three Terms of the Sequence floor(n^2/a)</a>, J. Int. Seq. 16 (2013) #13.6.4.
%H A000408 Franz Halter-Koch, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa42/aa4212.pdf">Darstellung natürlicher Zahlen als Summe von Quadraten</a>, Acta Arithmetica 42 (1982), pp. 11-20.
%H A000408 S. Mezroui, A. Azizi, and M'hammed Ziane, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Mezroui/soufiane4.html">On a Conjecture of Farhi </a>, J. Int. Seq. 17 (2014) #14.1.8.
%H A000408 <a href="/index/Su#ssq">Index entries for sequences related to sums of squares</a>
%F A000408 a(n) = 6n/5 + O(log n). - _Charles R Greathouse IV_, Mar 14 2014; error term improved Jul 05 2024
%p A000408 N:= 1000: # to get all terms <= N
%p A000408 S:= series((JacobiTheta3(0,q)-1)^3,q,1001):
%p A000408 select(t -> coeff(S,q,t)>0, [$1..N]); # _Robert Israel_, Jan 14 2016
%t A000408 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 *)
%t A000408 pr[n_] := Select[ PowersRepresentations[n, 3, 2], FreeQ[#, 0] &]; Select[ Range[104], pr[#] != {} &] (* _Jean-François Alcover_, Apr 04 2013 *)
%t A000408 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_ *)
%o A000408 (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
%o A000408 (PARI) is(n)= my(a, b) ; a=1 ; while(a^2+1<n, b=1 ; while(b<=a && a^2+b^2<n, if(issquare(n-a^2-b^2), return(1) ) ; b++ ; ) ; a++ ; ) ; return(0) ;
%o A000408 for(n=3, 1e3, if(is(n), print1(n, ", "))); \\ _Altug Alkan_, Jan 18 2016
%o A000408 (Haskell)
%o A000408 a000408 n = a000408_list !! (n-1)
%o A000408 a000408_list = filter ((> 0) . a025427) [1..]
%o A000408 -- _Reinhard Zumkeller_, Feb 26 2015
%o A000408 (Python)
%o A000408 def aupto(lim):
%o A000408   squares = [k*k for k in range(1, int(lim**.5)+2) if k*k <= lim]
%o A000408   sum2sqs = set(a+b for i, a in enumerate(squares) for b in squares[i:])
%o A000408   sum3sqs = set(a+b for a in sum2sqs for b in squares)
%o A000408   return sorted(set(range(lim+1)) & sum3sqs)
%o A000408 print(aupto(104)) # _Michael S. Branicky_, Mar 06 2021
%Y A000408 Cf. A000378, A000404, A000414, A003072, A004214, A024795, A024796, A025321, A025427.
%K A000408 nonn
%O A000408 1,1
%A A000408 _N. J. A. Sloane_ and _J. H. Conway_