# Smallest Number not Expressible as Sum of Fewer than 19 Fourth Powers

## Theorem

The smallest positive integer which cannot be expressed as the sum of fewer than $19$ fourth powers is $79$:

$79 = 15 \times 1^4 + 4 \times 2^4$

## Proof

We have $1^4 = 1, 2^4 = 16, 3^4 = 81 > 79$.

Hence for each $n < 79$, we can only use $1^4$ and $2^4$ in our sum.

Write $n = 2^4 a + 1^4 b$.

We can use the greedy algorithm to generate these expressions, since replacing $2^4$ with $16 \times 1^4$ increases the number of fourth powers required.

Suppose $n < 64$.

By Division Theorem, there is a unique way to write $n = 16 q + r$, with $q \in \Z$, $0 \le r < 16$.

 $\ds 16 q + r$ $=$ $\ds n$ $\ds \leadsto \ \$ $\ds 16 q + r$ $<$ $\ds 64$ $\ds \leadsto \ \$ $\ds 16 q$ $<$ $\ds 64$ $\ds \leadsto \ \$ $\ds q$ $<$ $\ds 4$

Thus $q + r \le 3 + 15 = 18$.

It follows that each positive integer less than $64$ can be expressed in not more than $18$ fourth powers.

Suppose $64 \le n \le 78$.

We cannot use more than $4$ $2^4$, since $5 \times 2^4 = 80 > n$.

Thus we write $n = 4 \times 2^4 + \paren {n - 64} \times 1^4$.

Since $n - 64 \le 78 - 64 = 14$, we can use not more than $18$ fourth powers to express $n$.

For $n = 79$, we still cannot use more than $4$ $2^4$, since $5 \times 2^4 = 80 > n$.

Thus $n = 4 \times 2^4 + 15 \times 1^4$ uses the least number of fourth powers.

Hence $79$ is the smallest positive integer which cannot be expressed as the sum of fewer than $19$ fourth powers.

$\blacksquare$