Pollock's conjecture

The $n$-th triangular number is the sum of the first $n$ positive integers. The $n$-th tetrahedral number is the sum of the first $n$ triangular numbers, and it equals $\frac{n(n+1)(n+2)}{6}$. For example, the 5th tetrahedral number is $1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)=\frac{5\cdot 6\cdot 7}{6}=35$.

• First 5 triangular numbers: $1, 3, 6, 10, 15$
• First 5 tetrahedral numbers: $1, 4, 10, 20, 35$

In 1850, Sir Frederick Pollock, 1st Baronet — not a professional mathematician, but a British lawyer and politician — conjectured that every positive integer can be represented as the sum of at most five tetrahedral numbers. A tetrahedral number may appear in the sum more than once, and each occurrence is counted separately. The conjecture has remained open for more than a century and a half.

Write a program that, for each given integer, computes the least number of tetrahedral numbers whose sum equals that integer. In addition, compute the least number of terms when only odd tetrahedral numbers may be used.

For example, 40 can be written as the sum of 2 tetrahedral numbers, $20+20$ (where $20=\frac{4\cdot 5\cdot 6}{6}$), even though 40 itself is not a tetrahedral number. Using only odd tetrahedral numbers, 40 needs at least 6 terms, $35+1+1+1+1+1$. So for the input 40 the program reports 2 and 6.

The input consists of several lines, each containing a single positive integer less than $10^6$. The end of the input is indicated by a line containing a single $0$.

For each input integer, print one line with two integers separated by a single space. The first integer is the least number of tetrahedral numbers whose sum is the given integer. The second integer is the least number of odd tetrahedral numbers whose sum is the given integer. No extra characters should appear in the output.