A331753 Let m(k) be the index of the largest triangular number <= k; then a(n) is the smallest number k that can be written as the sum of three triangular numbers if the largest is the (m(k)-n)-th triangular number, but no larger.

20, 50, 176, 110, 578, 614, 1163, 1070, 5135, 9503, 14648, 7928, 6035, 18653, 22130, 119204, 18128, 68258, 57335, 304799, 84725, 1024532, 215928, 692858, 688850, 637853, 736835, 1406105, 1801547, 1987469, 3673403, 654155, 8576861, 808718, 810146, 21515948

Offset: 1

Author

Jon E. Schoenfield, Feb 02 2020

Keywords

• nonn

Comments

Fermat asserted, and Gauss proved, that every number is the sum of three triangular numbers (cf. A002636).

For exactly half of the integers k in 1..11898, decomposing k into triangular numbers by the greedy algorithm (i.e., letting T1 be the largest triangular number <= k, then letting T2 be the largest triangular number <= k-T1, etc.) yields a decomposition of k into three or fewer positive triangular numbers, but for any K > 11898, the greedy algorithm decomposes more than half of the integers k in 1..K into four or more positive triangular numbers.

Even an approach that assigns only T1 "greedily" but allows T2 to be any triangular number will usually not yield a set of three triangular numbers whose sum is k: for more than half of the integers k in 1..K for any K > 40304762, no such sum exists in which the largest of the three triangular numbers is the largest triangular number <= k. The smallest such k is a(1)=20 (see Example section).

For some values of k, there exists no set of three triangular numbers summing to k unless the largest of the three is neither T(m(k)) nor T(m(k)-1); the smallest of these is a(2)=50, for which a solution to T(m(k)-2) + T2 + T3 = k does exist (see Example section).

Examples

			The largest triangular number <= 20 is T(5) = 5*6/2 = 15, and 20 cannot be expressed as the sum of 3 triangular numbers T1 + T2 + T3 if T1=15, but at T1 = T(5-1) = T(4) = 4*5/2 = 10, 20 can be expressed as T(4) + T(4) + T(0) = 10 + 10 + 0, and 20 is the smallest number with this property, so a(1)=20.
The largest triangular number <= 50 is T(9) = 9*10/2 = 45, and 50 can be expressed as T1 + T2 + T3 neither with T1 = T(9) = 45 nor with T1 = T(9-1) = T(8) = 36; however, at T1 = T(9-2) = T(7) = 28, 50 can be expressed as T(7) + T(6) + T(1) = 28 + 21 + 1, and 50 is the smallest number with this property, so a(2)=50.
		

Crossrefs

Cf. A000217 (triangular numbers), A002636 (number of ways of writing n as an unordered sum of at most 3 nonzero triangular numbers), A006893 (smallest number whose greedy decomposition uses n triangular numbers).