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

From ProofWiki
Jump to navigation Jump to search

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$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Smallest_Number_not_Expressible_as_Sum_of_Fewer_than_19_Fourth_Powers&oldid=463647"