Math Puzzle: Largest number which cannot be written as the sum of distinct fourth powers

I've come across this question which I can't seem to solve. Write the largest number that cannot be written as the sum of distinct fourth powers. First I'm stuck with the interpretation: I was thinking it meant base-4, but you can certainly find a base-4 representative of any base-10 number, right? Any help appreciated.

• A fourth power is a number of the form $n^4$. So $1$, $16$, $81$, $256$, and $625$ are the first few such numbers. – Barry Cipra Mar 25 '15 at 20:36
• @BarryCipra: Not forgetting $0$! – Mark Dickinson Mar 25 '15 at 20:52
• Bah. That looks like a factorial. It wasn't supposed to. – Mark Dickinson Mar 25 '15 at 20:53
• @MarkDickinson, of course! – Barry Cipra Mar 25 '15 at 20:54

An excerpt from "C21 Sums of higher powers" in Richard Guy's Unsolved Problems in Number Theory (third edition, pg. 207):

Denote by $s_k$ the largest integer that is not the sum of distinct $k$th powers of positive integers. Sprague showed that $s_2=128$; Graham reported that $s_3=12758$ and Lin used his method to obtain $s_4=$ ....

Here's the rest of that sentence, if you can't stand the suspense:

5134240

• It's even reported on Wikipedia, on the page en.wikipedia.org/wiki/Million. (So it must be true!) – Mark Dickinson Mar 25 '15 at 21:14
• Thank you so much! I can't believe google didn't generate that wiki result. – mugged99 Mar 25 '15 at 21:23
• @mugged99, so maybe Google isn't omnisicient after all. (Of course it probably knew I was going to post this comment....) – Barry Cipra Mar 25 '15 at 21:28

Waring's problem gives $g(4)=19$, i.e., every positive integer can be written as the sum of $19$ fourth powers, and this is minimal. So there is no largest number, which cannot be written as the sum of fourth powers.

Edit: The question is about the sum of distinct fourth powers. Then there are some numbers which are not the sum of distinct fourth powers. The largest one is $5134240$, see this book, and Barry Cipra's answer.

• Looking at the title I guess the question was about distinct fourth powers. That complicates matters further. I think that the answer is known, but my copy of Roberts is in my office. Sprague proved in the 40s that 128 is the largest integer that cannot be written as a sum of distinct squares. His idea can most likely be expanded to distinct fourth powers as well, but the details will be hairy (well, a computer enumeration will surely help :-) – Jyrki Lahtonen Mar 25 '15 at 20:40

For what it's worth, here is a computer proof (unless my code is buggy) that every integer larger than 5134240 is a sum of distinct 4th powers.

X={0}
c=0
B=5134241
e=0
while e<=(c+1)**4 or 2*(c+1)**4<(c+2)**4:
print("Still trying")
while B+e not in X:
c=c+1
X=X.union({x+c**4 for x in X})
## B+e is now in. Now how big is e?
while B+e in X:
e=e+1
## B+e now not in.

print("Every number between",B,"and",B+e-1,"(inclusive) is a sum of distinct 4th powers each of which is at most",c,"and so we're done by induction.")


If I run this code in python3 then in under a minute it prints

Every number between 5134241 and 11773650 (inclusive) is a sum of
distinct 4th powers each of which is at most 38  and so we're done
by induction.


The set X contains things which are the sums of distinct 4th powers. Eventually we find a sequence of more than $39^4$ consecutive numbers starting at 5134241 which are the sums of distinct 4th powers each of which is at most $38^4$; now allowing $39^4$ gives us a run of $2*39^4\geq40^4$ numbers which are the sums of distinct 4th powers each of which is at most $39^4$, and so on.

I learnt this trick from user Akashnil at

http://www.artofproblemsolving.com/community/c6h219756p1218963

The problem is: Find the largest number x such that x cannot be written as a sum of fourth powers; that is $x ≠ a^4 + b^4 + c^4 + d^4 + ...$ for any choice of integers 0 < a < b < c < d ...

(As a side note: The question says "distinct fourth powers" and means "distinct fourth powers of integers". If it said "fourth powers of distinct integers" then we could use for example $(-2)^4$ and $2^4$, both equal to 16, which would likely change the answer).

It's easy to find lets say the largest $x ≤ 10^9$ with that property; a simple program will do that in a few minutes: Create an array with $10^9+1$ boolean values $a_0$ to $a_{1,000,000,000}$. Initially set $a_0$ = true, all others = false because 0 is the only sum of fourth powers less than $1^4$. Then for i = 1, 2, 3, ... as long as $i^4 ≤ 10^9$, let p = $i^4$. Then let j = $10^9$, $10^9-1$, $10^9-2$ ... down to p, and for each j set $a_j$ to true if $a_{j-p}$ is true. Then check for the largest x such that $a_x$ is false.

How to prove that this is the smallest number overall: Just an idea. Using the algorithm described above, find all the integers x which can be written as sum of distinct fourth powers up to $i^4$, for i = 1, 2, 3, ... Hopefully we will eventually find a large range [a..b] such that all a ≤ x ≤ b are sums of distinct fourth powers up to $i^4$, and $(b + 1 - a) ≥ (i + 1)^4$. Then all integers in the range $[a..b + (i + 1)^4]$ are sums of fourth powers up to $(i + 1)^4$, and each further fourth power makes the range just bigger. Then we just examine all x < a.