%I #28 Jul 15 2024 14:48:22
%S 0,1,2,1,2,3,1,2,3,2,1,2,2,2,3,1,2,3,2,3,2,1,2,3,2,2,3,2,1,2,2,2,3,3,
%T 2,3,1,2,2,2,3,3,2,2,3,1,2,3,2,2,3,2,3,3,3,1,2,2,2,3,2,2,3,3,2,2,1,2,
%U 3,2,2,3,2,2,3,3,2,3,1,2,3,2,3,2,2,3,3,2,2,3,2,1,2,2,2,3,3,2,3,2,2,2,2,3,3
%N Smallest number of triangular numbers which sum to n.
%C a(n)=3 if n=5 or 8 mod 9, since triangular numbers are {0,1,3,6} mod 9.
%C From _Bernard Schott_, Jul 16 2022: (Start)
%C In September 1636, Fermat, in a letter to Mersenne, made the statement that every number is a sum of at most three triangular numbers. This was proved by Gauss, who noted this event in his diary on July 10 1796 with the notation:
%C EYPHKA! num = DELTA + DELTA + DELTA (where Y is in fact the Greek letter Upsilon and DELTA is the Greek letter of that name).
%C This proof was published in his book Disquisitiones Arithmeticae, Leipzig, 1801. (End)
%D Elena Deza and Michel Marie Deza, Fermat's polygonal number theorem, Figurate numbers, World Scientific Publishing (2012), Chapter 5, pp. 313-377.
%D C. F. Gauss, Disquisitiones Arithmeticae, Yale University Press, 1966, New Haven and London, p. 342, art. 293.
%H Giovanni Resta, <a href="/A061336/b061336.txt">Table of n, a(n) for n = 0..10000</a>
%H George E. Andrews, <a href="http://dx.doi.org/10.1016/0022-314X(86)90074-0">EYPHKA! num = Delta + Delta + Delta</a>, J. Number Theory 23 (1986), 285-293.
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FermatsPolygonalNumberTheorem.html">Fermat's Polygonal Number Theorem</a>.
%F a(n) = 0 if n=0, otherwise 1 if n is in A000217, otherwise 2 if n is in A051533, otherwise 3 in which case n is in A020757.
%F a(n) <= 3 (proposed by Fermat and proved by Gauss). - _Bernard Schott_, Jul 16 2022
%e a(3)=1 since 3=3, a(4)=2 since 4=1+3, a(5)=3 since 5=1+1+3, with 1 and 3 being triangular.
%t t[n_]:=n*(n+1)/2; a[0]=0; a[n_]:=Block[ {k=1, tt= t/@ Range[Sqrt[2*n]]}, Off[IntegerPartitions::take]; While[{} == IntegerPartitions[n, {k}, tt, 1], k++]; k]; a/@ Range[0, 104] (* _Giovanni Resta_, Jun 09 2015 *)
%o (PARI) \\ see A283370 for generic code, working but not optimized for this case of triangular numbers. - _M. F. Hasler_, Mar 06 2017
%o (PARI) a(n)=my(m=n%9,f); if(m==5 || m==8, return(3)); f=factor(4*n+1); for(i=1,#f~, if(f[i,2]%2 && f[i,1]%4==3, return(3))); if(ispolygonal(n,3), n>0, 2) \\ _Charles R Greathouse IV_, Mar 17 2022
%Y Cf. A000217, A007294, A057945, A061337, A051533, A020757.
%Y Cf. A100878 (analog for A000326), A104246 (analog for A000292), A283365 (analog for A000332), A283370 (analog for A000389).
%K nonn
%O 0,3
%A _Henry Bottomley_, Apr 25 2001