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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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