Triangular numbers as sums of triangular numbers

The nth triangular number, T(n), is a positive integer of the form n(n+1)/2 where n is a positive integer. The triangular numbers are so called because they can be arranged in triangular patterns (see MathWorld entry).

Gauss (it says here) proved Fermat’s conjecture that any positive integer can be written as the sum of at most three triangular numbers. I haven’t seen the proof, but given that apparently Gauss found it challenging, I’d imagine it’s fairly sophisticated.

What a non-sophisticate like me can do is prove a similar-sounding theorem: any triangular number (with a couple of exceptions) can be written as the sum of exactly three triangular numbers. This is more limited in that it applies only to (all but a few) triangular numbers, but more stringent in that it requires exactly three triangular numbers in the sum.

Consider some markers arranged in a triangle of side m>=3 (for example, m=7:)

  1: * * * * * * *
  2: * * * * * *
  3: * * * * *
  4: * * * *
  5: * * *
  6: * *
  7: *

We can choose the rightmost marker in row i, where 1<i<m, to be the lower right corner of a rectangle whose upper left corner is the upper left corner of the triangle (for example, i=3:)

  1: x x x x x * *
  2: x x x x x *
  3: x x x x x
  4: o o o o
  5: o o o
  6: o o
  7: o

Then we have partitioned the triangle into a rectangle with sides i and m+1-i (blue x), a triangle with side mi (green o), and a triangle with side i-1 (red *). This shows graphically that

T(m) = i(m+1-i) + T(mi) + T(i-1)    [m>=3, 1<i<m].  (1)

We could also choose the marker adjacent to the rightmost marker in row i, where this time 1<=i<m, to be our rectangle’s lower right corner (for example, again, i=3:)

  1: x x x x * * *
  2: x x x x * *
  3: x x x x *
  4: o o o o
  5: o o o
  6: o o
  7: o

Then we have partitioned the triangle into a rectangle with sides i and mi (blue x), a triangle with side mi (green o), and a triangle with side i (red *). So

T(m) = i(mi) + T(mi) + T(i)    [m>=3, 1<=i<m].  (2)

So right away we can show any triangular number T(m) (m>=3) can be written as a sum of four triangular numbers: If m is odd (m>=3) and we take the rightmost marker in row (m+1)/2 our rectangle is a square; likewise if m is even (m>=4) and we take the next-to-rightmost marker in row m/2. But a square of side k can be partitioned into two triangles of sides k and k-1.

But we want to do better. Can we find an i for a given m such that either i(m+1-i) or i(mi) is triangular? That is, find an i such that the given quantity is of the form n(n+1)/2?

Start with i(mi) = n(n+1)/2. Two possibilities are:

  1. 2i = n and (mi) = n+1.
  2. 2i = n+1 and (mi) = n.

(Two other possibilities, i = n and 2(mi) = n+1, and i = n+1 and 2(mi) = n, are equivalent to these, with i->mi and mi->i.)

Solving for i, mi, and n,

  1. i = (m-1)/3, mi = (2m+1)/3, n = 2(m-1)/3.
  2. i = (m+1)/3, mi = (2m-1)/3, n = (2m-1)/3.

For the other possibility, where the rectangle is i(m+1-i), we get similarly:

  1. i = m/3, mi = 2m/3, n = 2m/3
  2. i = (m+2)/3, mi = 2(m-1)/3, n = (2m+1)/3

To obtain integer results we can use:

  • Case 1 when m is of the form 3k+1; then i = k, mi = 2k+1, n = 2k
  • Case 2 when m is of the form 3k-1; then i = k, mi = 2k-1, n = 2k-1
  • Case 3 when m is of the form 3k; then i = k; m+1-i = 2k-1; n = 2k
  • Case 4 when m is of the form 3k+1; then i = k+1; m+1-i = 2k+1; n = 2k+1

Now putting these together with formulas (1) and (2) we have:

T(3k+1) = T(2k+1) + T(2k) + T(k) for k > 0 => 3k+1 = 4, 7, 10… (This comes from either case 1 or case 4.)
T(3k-1) = T(2k-1) + T(2k-1) + T(k) for k > 0 => 3k-1 = 2, 5, 8…
T(3k) = T(2k) + T(2k) + T(k-1) for k > 1 => 3k = 6, 9, 12…

This gives one partition of any triangular number T(m) into exactly three triangular numbers for any m except 1 and 3.

Some triangular numbers can also be partitioned into three equal triangular numbers — that is, they can be written as three times another triangular number. T(2) = 3 rather trivially equals 3*T(1) = 3 * 1; less trivially, T(9) = 45 equals 3*T(5) = 3 * 15. An infinite number of triangular numbers partition this way, and the formula to find their indices is a(n) = 4a(n-1)-a(n-2)+1. See On-Line Encyclopedia of Integer Sequences entry A061278.

For most m there are several possible threefold partitions into triangular numbers, which in general I don’t know any formula for; I believe you just have to search the solution space. The largest m I know of for which T(m) has only one partition is T(10) = 55 = T(3)+T(6)+T(7).

The smallest m for which T(m) has no threefold partitions using T(1) or T(2) is T(8) = 36 = T(3)+T(5)+T(5). The smallest m for which T(m) has no partitions using T(1), T(2), or T(3) is the very Biblical T(36) = 666 = T(5)+T(6)+T(35) = T(5)+T(24)+T(26) = T(6)+T(20)+T(29) = T(11)+T(24)+T(24) = T(12)+T(17)+T(29) = T(12)+T(20)+T(27) = T(14)+T(20)+T(26).

How about twofold partitions? These are sometimes but not always possible: possible for indices 3, 6, 8, 10, 11, 13, 15, 16, 18… See EIS entry A012132.

Partitions into two equal triangular numbers, i.e. twice another triangular number: T(3) = 6 = T(2)+T(2); T(20) = 210 = T(14)+T(14); T(119) = 7140 = T(84)+T(84); etc. See EIS entry A053141.

Four-fold or higher-fold partitions seem to be always possible, beyond the first few indices of course. No (nonzero) triangular number is four times another triangular number. Proof: if T(m) = 4T(n), then m(m+1)/2 is divisible by 4, m(m+1) is divisible by 8, and this can be true only if m or m+1 is divisible by 8, that is, m = 8j or m = 8j-1 and T(m) = 4j(8j±1) = 32j2±4j. Now consider T(4j) = (4j)(4j+1)/2 = 2j(4j+1). Four times this is 8j(4j+1) = 32j2+8j, too big by either 4j or 12j. On the other hand, T(4j-1) = 2j(4j-1), and four times this is 8j(4j-1) = 32j2-8j, too small by either 4j or 12j. So no triangular number is a quarter of 4j(8j±1), i.e., no (nonzero) triangular number is a quarter of another triangular number.

For higher equal partitions, T(5) = 15 = 5*T(2); T(14) = 105 = 5*T(6); T(3) = 6 = 6*T(1); T(8) = 36 = 6*T(3); T(6) = 21 = 7*T(2); T(14) = 105 = 7*T(5); and T(15) = 120 = 8*T(5).

Table of threefold partitions for T(m) < 1000:

T(1) = 1 none
T(2) = 3 = T(1)+T(1)+T(1)
T(3) = 6 none
T(4) = 10 = T(1)+T(2)+T(3)
T(5) = 15 = T(2)+T(3)+T(3)
T(6) = 21 = T(1)+T(4)+T(4)
= T(2)+T(2)+T(5)
T(7) = 28 = T(1)+T(3)+T(6)
= T(2)+T(4)+T(5)
T(8) = 36 = T(3)+T(5)+T(5)
T(9) = 45 = T(2)+T(3)+T(8)
= T(2)+T(6)+T(6)
= T(5)+T(5)+T(5)
T(10) = 55 = T(3)+T(6)+T(7)
T(11) = 66 = T(1)+T(4)+T(10)
= T(3)+T(5)+T(9)
= T(4)+T(7)+T(7)
= T(5)+T(5)+T(8)
T(12) = 78 = T(3)+T(3)+T(11)
= T(3)+T(8)+T(8)
= T(6)+T(6)+T(8)
T(13) = 91 = T(1)+T(9)+T(9)
= T(2)+T(4)+T(12)
= T(4)+T(5)+T(11)
= T(4)+T(8)+T(9)
= T(5)+T(6)+T(10)
T(14) = 105 = T(2)+T(8)+T(11)
= T(3)+T(6)+T(12)
= T(5)+T(9)+T(9)
T(15) = 120 = T(1)+T(7)+T(13)
= T(3)+T(8)+T(12)
= T(4)+T(10)+T(10)
= T(6)+T(6)+T(12)
T(16) = 136 = T(1)+T(5)+T(15)
= T(2)+T(7)+T(14)
= T(2)+T(10)+T(12)
= T(3)+T(4)+T(15)
= T(4)+T(6)+T(14)
= T(5)+T(10)+T(11)
= T(8)+T(9)+T(10)
T(17) = 153 = T(2)+T(9)+T(14)
= T(6)+T(11)+T(11)
T(18) = 171 = T(2)+T(5)+T(17)
= T(3)+T(9)+T(15)
= T(5)+T(8)+T(15)
= T(5)+T(12)+T(12)
= T(6)+T(9)+T(14)
T(19) = 190 = T(1)+T(8)+T(17)
= T(5)+T(10)+T(15)
= T(6)+T(12)+T(13)
T(20) = 210 = T(2)+T(8)+T(18)
= T(4)+T(4)+T(19)
= T(6)+T(8)+T(17)
= T(7)+T(13)+T(13)
= T(9)+T(9)+T(15)
= T(11)+T(11)+T(12)
T(21) = 231 = T(3)+T(5)+T(20)
= T(3)+T(14)+T(15)
= T(5)+T(9)+T(18)
= T(6)+T(14)+T(14)
= T(9)+T(11)+T(15)
T(22) = 253 = T(1)+T(6)+T(21)
= T(5)+T(7)+T(20)
= T(7)+T(14)+T(15)
= T(9)+T(10)+T(17)
= T(10)+T(12)+T(15)
T(23) = 276 = T(2)+T(15)+T(17)
= T(6)+T(9)+T(20)
= T(8)+T(15)+T(15)
= T(9)+T(12)+T(17)
= T(11)+T(14)+T(14)
= T(12)+T(12)+T(15)
T(24) = 300 = T(2)+T(6)+T(23)
= T(2)+T(11)+T(21)
= T(7)+T(16)+T(16)
= T(9)+T(9)+T(20)
= T(10)+T(10)+T(19)
T(25) = 325 = T(1)+T(17)+T(18)
= T(2)+T(13)+T(21)
= T(3)+T(11)+T(22)
= T(4)+T(5)+T(24)
= T(4)+T(14)+T(20)
= T(5)+T(15)+T(19)
= T(6)+T(7)+T(23)
= T(7)+T(11)+T(21)
= T(8)+T(8)+T(22)
= T(8)+T(16)+T(17)
T(26) = 351 = T(3)+T(9)+T(24)
= T(5)+T(8)+T(24)
= T(5)+T(14)+T(21)
= T(6)+T(15)+T(20)
= T(8)+T(14)+T(20)
= T(9)+T(17)+T(17)
= T(12)+T(15)+T(17)
T(27) = 378 = T(3)+T(6)+T(26)
= T(5)+T(17)+T(20)
= T(8)+T(11)+T(23)
= T(8)+T(18)+T(18)
= T(14)+T(15)+T(17)
T(28) = 406 = T(1)+T(14)+T(24)
= T(2)+T(12)+T(25)
= T(3)+T(19)+T(20)
= T(4)+T(9)+T(26)
= T(4)+T(15)+T(23)
= T(5)+T(11)+T(25)
= T(5)+T(13)+T(24)
= T(7)+T(12)+T(24)
= T(8)+T(9)+T(25)
= T(9)+T(18)+T(19)
= T(10)+T(15)+T(21)
= T(13)+T(14)+T(20)
T(29) = 435 = T(1)+T(7)+T(28)
= T(3)+T(12)+T(26)
= T(3)+T(17)+T(23)
= T(5)+T(15)+T(24)
= T(5)+T(20)+T(20)
= T(6)+T(8)+T(27)
= T(10)+T(10)+T(25)
= T(10)+T(19)+T(19)
= T(13)+T(13)+T(22)
= T(14)+T(15)+T(20)
T(30) = 465 = T(2)+T(21)+T(21)
= T(5)+T(5)+T(29)
= T(6)+T(11)+T(27)
= T(8)+T(12)+T(26)
= T(8)+T(17)+T(23)
= T(9)+T(15)+T(24)
= T(9)+T(20)+T(20)
T(31) = 496 = T(2)+T(7)+T(30)
= T(3)+T(10)+T(29)
= T(3)+T(19)+T(24)
= T(4)+T(6)+T(30)
= T(4)+T(20)+T(23)
= T(9)+T(9)+T(28)
= T(10)+T(20)+T(21)
= T(11)+T(14)+T(25)
= T(13)+T(14)+T(24)
= T(17)+T(17)+T(19)
T(32) = 528 = T(3)+T(18)+T(26)
= T(5)+T(12)+T(29)
= T(6)+T(21)+T(23)
= T(9)+T(14)+T(27)
= T(11)+T(21)+T(21)
T(33) = 561 = T(3)+T(15)+T(29)
= T(4)+T(10)+T(31)
= T(6)+T(14)+T(29)
= T(10)+T(22)+T(22)
= T(12)+T(14)+T(27)
= T(14)+T(14)+T(26)
= T(15)+T(20)+T(21)
T(34) = 595 = T(1)+T(11)+T(32)
= T(3)+T(7)+T(33)
= T(4)+T(15)+T(30)
= T(6)+T(12)+T(31)
= T(8)+T(17)+T(28)
= T(10)+T(14)+T(29)
= T(11)+T(22)+T(23)
= T(13)+T(17)+T(26)
= T(14)+T(19)+T(24)
= T(18)+T(18)+T(22)
T(35) = 630 = T(2)+T(11)+T(33)
= T(2)+T(23)+T(26)
= T(6)+T(21)+T(27)
= T(8)+T(11)+T(32)
= T(9)+T(15)+T(30)
= T(12)+T(23)+T(23)
= T(15)+T(20)+T(24)
= T(20)+T(20)+T(20)
T(36) = 666 = T(5)+T(6)+T(35)
= T(5)+T(24)+T(26)
= T(6)+T(20)+T(29)
= T(11)+T(24)+T(24)
= T(12)+T(17)+T(29)
= T(12)+T(20)+T(27)
= T(14)+T(20)+T(26)
T(37) = 703 = T(1)+T(8)+T(36)
= T(1)+T(26)+T(26)
= T(2)+T(14)+T(34)
= T(3)+T(16)+T(33)
= T(5)+T(22)+T(29)
= T(6)+T(23)+T(28)
= T(7)+T(9)+T(35)
= T(7)+T(20)+T(30)
= T(8)+T(18)+T(31)
= T(10)+T(15)+T(32)
= T(11)+T(21)+T(28)
= T(12)+T(19)+T(29)
= T(12)+T(24)+T(25)
T(38) = 741 = T(2)+T(20)+T(32)
= T(3)+T(14)+T(35)
= T(3)+T(24)+T(29)
= T(4)+T(7)+T(37)
= T(4)+T(16)+T(34)
= T(4)+T(25)+T(28)
= T(9)+T(11)+T(35)
= T(9)+T(21)+T(30)
= T(10)+T(13)+T(34)
= T(10)+T(19)+T(31)
= T(11)+T(20)+T(30)
= T(13)+T(25)+T(25)
= T(14)+T(18)+T(30)
= T(17)+T(17)+T(29)
= T(17)+T(20)+T(27)
= T(20)+T(21)+T(24)
T(39) = 780 = T(2)+T(8)+T(38)
= T(5)+T(24)+T(30)
= T(6)+T(21)+T(32)
= T(8)+T(12)+T(36)
= T(9)+T(14)+T(35)
= T(9)+T(24)+T(29)
= T(11)+T(17)+T(33)
= T(12)+T(26)+T(26)
= T(14)+T(20)+T(30)
= T(17)+T(23)+T(26)
= T(18)+T(21)+T(27)
T(40) = 820 = T(1)+T(12)+T(38)
= T(1)+T(17)+T(36)
= T(3)+T(22)+T(33)
= T(5)+T(20)+T(34)
= T(7)+T(21)+T(33)
= T(8)+T(27)+T(28)
= T(10)+T(24)+T(30)
= T(13)+T(26)+T(27)
= T(14)+T(15)+T(34)
= T(17)+T(18)+T(31)
T(41) = 861 = T(2)+T(12)+T(39)
= T(5)+T(11)+T(39)
= T(5)+T(14)+T(38)
= T(6)+T(20)+T(35)
= T(8)+T(9)+T(39)
= T(9)+T(26)+T(30)
= T(12)+T(17)+T(35)
= T(14)+T(27)+T(27)
= T(15)+T(23)+T(30)
= T(20)+T(24)+T(26)
T(42) = 903 = T(1)+T(28)+T(31)
= T(2)+T(15)+T(39)
= T(2)+T(29)+T(30)
= T(3)+T(8)+T(41)
= T(3)+T(21)+T(36)
= T(4)+T(19)+T(37)
= T(6)+T(6)+T(41)
= T(7)+T(10)+T(40)
= T(9)+T(12)+T(39)
= T(10)+T(22)+T(34)
= T(11)+T(18)+T(36)
= T(11)+T(23)+T(33)
= T(13)+T(28)+T(28)
= T(15)+T(17)+T(35)
= T(18)+T(18)+T(33)
= T(22)+T(25)+T(25)
= T(23)+T(23)+T(26)
T(43) = 946 = T(3)+T(15)+T(40)
= T(5)+T(7)+T(42)
= T(5)+T(19)+T(38)
= T(5)+T(29)+T(31)
= T(6)+T(14)+T(40)
= T(14)+T(28)+T(29)
= T(15)+T(21)+T(34)
= T(19)+T(27)+T(27)
T(44) = 990 = T(6)+T(11)+T(42)
= T(12)+T(18)+T(38)
= T(12)+T(26)+T(33)
= T(14)+T(14)+T(39)
= T(15)+T(29)+T(29)
= T(17)+T(18)+T(36)
= T(17)+T(23)+T(33)
= T(21)+T(21)+T(32)