login
Smallest number of triangular numbers which sum to n.
17

%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