A061336 Smallest number of triangular numbers which sum to n.

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, 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, 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

Offset: 0

Author

Henry Bottomley, Apr 25 2001

Keywords

• nonn

Comments

a(n)=3 if n=5 or 8 mod 9, since triangular numbers are {0,1,3,6} mod 9.

From Bernard Schott, Jul 16 2022: (Start)

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:

EYPHKA! num = DELTA + DELTA + DELTA (where Y is in fact the Greek letter Upsilon and DELTA is the Greek letter of that name).

This proof was published in his book Disquisitiones Arithmeticae, Leipzig, 1801. (End)

Examples

			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.
		

References

• Elena Deza and Michel Marie Deza, Fermat's polygonal number theorem, Figurate numbers, World Scientific Publishing (2012), Chapter 5, pp. 313-377.
• C. F. Gauss, Disquisitiones Arithmeticae, Yale University Press, 1966, New Haven and London, p. 342, art. 293.

Links

• Giovanni Resta, Table of n, a(n) for n = 0..10000
• George E. Andrews, EYPHKA! num = Delta + Delta + Delta, J. Number Theory 23 (1986), 285-293.
• Eric Weisstein's World of Mathematics, Fermat's Polygonal Number Theorem.

Crossrefs

Cf. A000217, A007294, A057945, A061337, A051533, A020757.

Cf. A100878 (analog for A000326), A104246 (analog for A000292), A283365 (analog for A000332), A283370 (analog for A000389).

Programs

Mathematica

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 *)

PARI

\\ see A283370 for generic code, working but not optimized for this case of triangular numbers. - M. F. Hasler, Mar 06 2017

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

Formula

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.

a(n) <= 3 (proposed by Fermat and proved by Gauss). - Bernard Schott, Jul 16 2022