\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\usepackage{multirow}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{algorithm}[theorem]{Algorithm}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Largest Integer Not\\
\vskip .1in
the Sum of Distinct 8th Powers
}
\vskip 1cm
\large
Michael J.\ Wiener\\
20 Hennepin St.\\
Nepean, ON K2J 3Z4\\
Canada\\
\href{mailto:michael.james.wiener@gmail.com}{\tt michael.james.wiener@gmail.com}
\end{center}

\vskip .2 in

\begin{abstract}
The largest integer that is not the sum of one or more distinct
squares is 128 and is called the threshold of completeness for the set of squares.
A natural extension is to consider positive cubes and higher powers.
Previous research solved this problem for powers up to 7.
Our contribution is the threshold of completeness for 8th powers as well as
lower bounds for powers from 9 to 16.
We also describe the mathematical methods we used to speed up computations.
Using 200,000 computer cores, our methods could find the threshold of completeness for 9th
powers in about a month, and for 10th powers in about a year.
\end{abstract}

\section{Introduction}\label{introduction}

There is no way to write 128 as the sum of one or more distinct squares,
and it is the largest such number~\cite{Spr48}.
The fact that the summed squares are distinct is important; $128 = 8^2+8^2$ does not count.
We say that 128 is not {\it summable} with the set $\{1^2, 2^2, \ldots\}$, 
and is the largest such number.
We can prove this by first showing that 128 is not summable with squares
and then showing that each integer from 129 to 249 is summable with the finite set
$\{1^2, 2^2, \ldots, 10^2\}$.
We can then add $11^2$ to each of the solutions for the integers from 129 to 249 to
cover the range 250 to 370.
We then add $12^2$ to the solutions for the integers from 129 to 370 to extend the
covered range.
Continuing with $13^2, 14^2, \ldots$, the covered range extends indefinitely with
overlaps but without 
leaving any gaps.
We call 128 the {\it threshold of completeness\/} for squares.

In this work, we focus on the threshold of completeness for sets of positive $n$th powers.
However, we can generalize the idea of thresholds of completeness to other sets, such as the
triangular numbers, $(x(x+1)/2)_{x \in \mathbb{N}} = \{1, 3, 6, 10, \ldots\}$, or to any other polynomial.
Fuller and Nichols studied thresholds of completeness for a wide range of generalizations
of this problem including sets that do not include all powers, and requiring that
the minimum number of powers summed be some constant other than 1~\cite{FN15}.
They use the term {\it anti-Waring number} for the smallest number such that it and 
every subsequent integer is summable.
Thus the anti-Waring number is one more than the threshold of completeness
(when both numbers exist).

The threshold of completeness does not exist for all sets because 
there might be no point beyond which
all integers are summable.
For example, the set of even numbers cannot give any odd sums, 
and any finite set only gives a finite number of sums.
However, Sprague proved that the threshold of completeness for positive 
$n$th powers exists for all positive integers $n$~\cite{Spr48proof},
and Roth and Szekeres generalized this proof by showing which polynomials $p(x)$
are such that $(p(x))_{x \in \mathbb{N}}$ has a threshold of completeness~\cite{RS54}.
Later, Graham gave an alternative proof of Roth and Szekeres' result
in an ``elementary manner''~\cite{Gra64}.

Kim made an interesting contribution proving the following 
upper bound for the threshold of completeness of positive $n$th powers:
$$(b-1)2^{n-1}\bigl(r+\tfrac{2}{3}(b-1)(2^{2n}-1)+2(b-2)\bigr)^n-2a+ab,$$ 
where $a=n!2^{n^2}, b=2^{n^3}a^{n-1}, r=2^{n^2-n}a$~\cite{Kim17}.

For odd exponents, not being careful about stating that only positive powers are permitted
can lead to the misunderstanding that we can include negative powers, such as $(-2)^3$.
Permitting both addition and subtraction of powers is not an interesting generalization
of the threshold of completeness problem.
We can see this with the following method that uses Prouhet's solution to the Tarry-Escott
problem~\cite{Wri59}.
Consider the $2^n$ consecutive powers 
$u^n, (u-1)^n, \ldots, (u-2^n+1)^n$ 
added and subtracted with the signs of the powers in a Prouhet-Thue-Morse sequence 
({\small $+--+-++--++-+--+\ldots$})~\cite{Pro1851,Thu06,Thu12,Mor21},
\seqnum{A010060} in the 
{\it On-Line Encyclopedia of Integer Sequences} \cite{OEIS}.
Each power is a polynomial in $u$ whose highest degree term is $\pm u^n$.
When we take the powers in $2^{n-1}$ adjacent pairs, 
the pairs are finite differences with a spacing of $\pm 1$,
the $u^n$ terms cancel,
and we are left with polynomials in $u$ whose highest degree term is $\pm nu^{n-1}$.
When we take these polynomials in $2^{n-2}$ pairs, 
each pair is a second order finite difference
with a spacing of $\pm 2$ and is a polynomial whose highest degree term is $\pm 2n(n-1)u^{n-2}$.
Each step of pairing up the polynomials produces higher order finite differences
(using spacings equal to plus or minus a power of 2)
that reduce the polynomial degree by 1, and all 
resulting polynomials have the same highest degree term
except for the sign.
The final sum
is the constant $c=n!2^{n(n-1)/2}$, independent of $u$.
This means that by varying $u$, we get an infinite supply of sums equal to $c$,
each using $2^n$ consecutive powers (from non-overlapping ranges).
Now consider any power of the form $(vc+1)^n$ for arbitrary $v$.
Such powers are congruent to 1 (mod $c$),
and we can subtract enough sums equal to $c$ to get a sum of 1.
This means we now have an infinite supply of sums equal to 1.
With these we can form any sum that is positive, negative, or zero.

According to the {\it On-Line Encyclopedia of Integer Sequences} (\seqnum{A001661}), 
thresholds of completeness are known
for sets of positive $n$th powers for exponents $n = 1, 2, \ldots, 7$, 
with the $n=7$ case solved by Johnson in 2010~\cite{OEIS}.
Our contribution is the threshold of completeness for 8th powers and 
lower bounds for some higher exponents (see Table~\ref{ToC}).
We also describe the mathematical methods we developed to compute thresholds
of completeness in enough detail that others can reproduce and extend our results.
\setlength{\tabcolsep}{6pt}
\begin{table}
\normalsize
\begin{center}
\begin{tabular}{|c|r|c|} 
\hline
 & & \\[-10pt]
$n$ & \multicolumn{1}{c|}{Threshold of Completeness for $n$th powers} & Reference \\
\hline \hline
 & & \\[-9pt]
1 & 0  & \\
2 & 128  & \cite{Spr48} \\
3 & 12,758  & \cite{Gra64,DP74} \\
4 & 5,134,240  & \cite{Lin70} \\
5 & 67,898,771  & \cite{Pat92} \\
6 & 11,146,309,947 & \cite{FN15} \\
7 & 766,834,015,734 & \cite{OEIS} \\
8 & 4,968,618,780,985,762 & this work \\
9 & $\ge$ 155,581,444,629,727,232 & \multirow{2}{*}{\vspace{24pt}\vdots} \\
10 & $\ge$ 13,130,572,287,326,740,862 & \\
11 & $\ge$ 1,641,961,088,738,387,417,337 & \\
12 & $\ge$ 555,664,230,155,437,340,241,901 & \\
13 & $\ge$ 132,999,999,685,872,578,648,583,148 &  \\
14 & $\ge$ 13,799,996,074,582,156,266,244,947,666 &  \\
15 & $\ge$ 2,099,999,963,240,136,765,496,329,587,024 &  \\
16 & $\ge$ 999,999,988,996,135,865,287,858,019,238,512,392 & \\
\hline
\end{tabular}
\end{center} 
\caption{Thresholds of completeness.}
\label{ToC}
\end{table}

\section{Finding thresholds of completeness by finite search}\label{confirm}

When we say that a threshold of completeness has a particular value, in part we are asserting that 
all larger values are summable (see Definition~\ref{threshdef}).
Fortunately, we can prove this with a finite search.
\begin{definition}
Let $S(x^n) = \{1^n, 2^n, \ldots\}$, and let $S_k(x^n) = \{1^n, 2^n, \ldots, k^n\}$.
\label{setdef}
\end{definition}
\begin{definition}
The threshold of completeness for $n$th powers, $T(S(x^n))$, is the largest integer that
is not the sum of one or more distinct elements of the set $S(x^n)$.
\label{threshdef}
\end{definition}
According to Porubsk{\'y}~\cite{Por09}, Theorem~\ref{maintheorem} below began 
with Richert proving that every
integer greater than 6 is the sum of distinct primes~\cite{Ric49}, and Sierpi\'nski extending 
it to more general purposes~\cite{Sie88}.
The version below is adapted for finding thresholds of completeness.
\begin{theorem}
Given $n, k \in \mathbb{Z}^+$ and $t \in \mathbb{Z}$ such that 
\begin{itemize}
\item[(1)] $t+1$ to $t+(k+1)^n$ (inclusive) 
are summable with
the finite set $S_k(x^n)$, and
\item[(2)] $(k+2)^n \le 2(k+1)^n$,
\end{itemize}
then the threshold of completeness $T(S(x^n)) \le t$.
\label{maintheorem}
\end{theorem}
\begin{proof}
Let $a \ge 0$.
Rewrite condition (2) as $(k+2)/(k+1) \le 2^{1/n}$.
Then
$$ \frac{k+a+2}{k+a+1} = \frac{k+2}{k+1} - \frac{a}{(k+a+1)(k+1)}
\le \frac{k+2}{k+1} \le 2^{1/n}.$$
So, if condition (2) holds for $k$, it also holds if we replace $k$ with any integer
larger than $k$.
Next we use induction.
Consider the statement that all integers from $t+1$ to $t+(b+1)^n$ (inclusive) are summable with
the finite set $S_b(x^n) = \{1^n, 2^n, \ldots, b^n\}$.
Assume the statement is true for some $b \ge k$.
We can then add $(b+1)^n$ to each solution from $t+1$ to $t+(b+1)^n$ so that all
integers from
$t+1$ to $t+2(b+1)^n$ are summable using powers no larger than $(b+1)^n$.
Because $(b+2)^n \le 2(b+1)^n$, we now have that all integers from $t+1$ to $t+(b+2)^n$ 
are summable using the set $S_{b+1}(x^n)$.
This proves that if the statement is true for $b$, then it is true for $b+1$.
By condition (2), the statement is true for $b=k$.
This completes the proof by induction that the statement is true for all $b \ge k$.
So all integers from $t+1$ to $t+(b+1)^n$ are summable from $S(x^n)$ for $b$
growing without bound.
Thus, all integers greater than $t$ are summable, and
the threshold of completeness $T(S(x^n)) \le t$, as required.
\end{proof}
Theorem~\ref{maintheorem} does not directly give us the threshold of completeness, but once we 
have $t$ and $k$ that satisfy its conditions, the problem is reduced to a finite search through
integers less than or equal to $t$ for the largest integer that is not summable.
We could add a third condition to this theorem that $t$ be non-summable so that it is equal to
the threshold of completeness.
However, we found that adding this condition is inefficient for exponents 4 and 6
because it requires a larger value for $k$ (see the discussion of Table~\ref{lowexp}).

\section{Exponents up to 6}\label{warmup}

We describe a simple and fast sieve-like method of finding the threshold of completeness
for small exponents to introduce concepts 
that will be useful for larger exponents.
We begin with a memory consisting of
an array of bits $b_0, b_1, \ldots, b_\mu$ for some upper limit $\mu$.
If $\mu \ge t+(k+1)^n$, where $n$, $t$, and $k$ are as defined in Theorem~\ref{maintheorem},
then the algorithm described below will succeed in finding $T(S(x^n))$.
To start, set $b_0=1$, and the remaining bits to 0.
In this state, we are indicating that using no elements of $S(x^n)$ at all, the only sum we can form
is 0.
Although Definition~\ref{threshdef} requires a valid sum to include at least one power,
it is convenient to consider 0 to be the sum of the null set of powers for this computation.
Let us consider the case of squares using $\mu=255$.
The starting state of the memory is $b_{255} = \cdots = b_1 = 0$, and $b_0=1$.
Next we make use of Algorithm~\ref{addpower} for adding a power $y$ 
to every existing sum in the memory.
\begin{definition}
We use $\land$ as the bitwise AND operation, and $\lor$ as the bitwise OR operation.
Let
$x, y, z$ be nonnegative integers with binary representations 
$x=\sum_{i=0}^\infty x_i2^i$, 
$y=\sum_{i=0}^\infty y_i2^i$, $z=\sum_{i=0}^\infty z_i2^i$, and all 
$x_i, y_i, z_i \in \{0,1\}$.
We say that $z$ is the bitwise AND of $x$ and $y$ and write $z = x \land y$ 
if for all $i \in \mathbb{Z}_0^+$, $z_i = x_i~\textrm{AND}~y_i$.
Similarly, we say that $z$ is the bitwise OR of $x$ and $y$ and write $z = x \lor y$ 
if for all $i \in \mathbb{Z}_0^+$, $z_i = x_i~\textrm{OR}~y_i$.
\label{bitwisedef}
\end{definition}
\begin{algorithm} {\it Add New Power to Memory.} \label{addpower}
Take a power $y$ and memory limit $\mu$,
and add to the memory $y$ more than every sum already represented in the memory.
Given the memory bits $b_0, b_1, \ldots, b_\mu$, we go through the 
$b_i$ from $i=\mu$ down to $y$, and 
perform $b_i \gets b_i$ OR $b_{i-y}$.
If we think of the memory as a single large integer $W=\sum_{i=0}^\mu b_i2^i$, 
this operation is
simply $W \gets W \lor (2^yW \bmod{2^{\mu+1}})$  (see Definition~\ref{bitwisedef}).
\end{algorithm}
For the first three times we use Algorithm~\ref{addpower} below, we show only $b_{14}, \ldots, b_0$ 
because the higher order bits are all zeros after these steps.
Now we use Algorithm~\ref{addpower} to add the power $y=1^2$ to the memory.
The result is
$$ b_{14}~\textrm{to}~b_0: 000000000000011, $$
which means that the possible sums are 0 and 1.
Next we add in $2^2$ to get
$$ b_{14}~\textrm{to}~b_0: 000000000110011, $$
corresponding to sums 0, 1, 4, 5.
After the step with $3^2$, we get
$$ b_{14}~\textrm{to}~b_0: 110011000110011. $$
After the $4^2,5^2,\ldots,10^2$ steps, we have
\begin{displaymath}
\begin{array}{rl}
b_{63}~\textrm{to}~b_0: & 1110111111111110011001111111110001100110001100110110011000110011 \\
b_{127}~\textrm{to}~b_{64}: & 1111111111111110111011111111111011101111111111111110111011110111 \\
b_{191}~\textrm{to}~b_{128}: & 1111111111111111111111111111111111111111111111111111111111111110 \\
b_{255}~\textrm{to}~b_{192}: & 1111111111111111111111111111111111111111111111111111111111111111 . \\
\end{array}
\end{displaymath}
Now $b_{128}=0$ and all the higher order bits are 1.
The conditions of Theorem~\ref{maintheorem} are met for $n=2$, $t=128$, and $k=10$.
All that remains is to find the largest integer less than or equal to 128 that is not summable.
We proceed with the $11^2$ step with Algorithm~\ref{addpower} because $11^2 \le 128$, 
and see that it does not change $b_{128}$.
Thus $T(S(x^2))=128$.

Table~\ref{lowexp} shows results for powers up to 6 using this method on a laptop.
We see that $T(S(x^n)) < t$ for exponents 4 and 6.
If we add the requirement that $t=T(S(x^n))$ to Theorem~\ref{maintheorem},
execution times increase for the exponent 4 and 6 cases, because we
have to increase $k$ to 38 and 46, respectively.
(All execution times in this paper are measured using a single thread on a 
12th Generation Intel(R) Core(TM) i9-12900HK running at 2.50 GHz.
For memory sizes, we use kB = 1024 bytes, MB = 1024 kB, GB = 1024 MB, and TB = 1024 GB.)

Unfortunately, using this simple and fast method would require 152 GB for 7th powers
and 776 TB for 8th powers,
which is well beyond the memory capacity of a typical laptop.
It would be possible to use the laptop's solid state drive for 7th powers, 
and a modern supercomputer could handle 8th powers,
but we chose to find ways to trade extra execution
time for reduced memory requirements.
\setlength{\tabcolsep}{6pt}
\begin{table}
\normalsize
\begin{center}
\begin{tabular}{|c|r|r|c|c|c|} 
\hline
 & & & & & \\[-10pt]
$n$ & \multicolumn{1}{c|}{$T(S(x^n))$} & \multicolumn{1}{c|}{$t$} & $k$ & Memory Size & Run Time \\
\hline \hline
 & & & & & \\[-9pt]
1 & 0  & 0  & 1 & 2 bits & $<1~\mu$s \\
2 & 128  & 128  & 10 & 250 bits (32 bytes) & $1.3~\mu$s \\
3 & 12,758  & 12,758  & 20 & 22,020 bits (3 kB) & $27~\mu$s \\
4 & 5,134,240  & 6,211,329  & 37 & 8,296,466 bits (1.0 MB) & 2.4 ms \\
5 & 67,898,771  & 67,898,771  & 33 & 113,334,196 bits (14 MB) & 28 ms \\
6 & 11,146,309,947 & 12,840,617,485 & 42 & 19,161,980,535 bits (2.3 GB) & 7.7 s \\
\hline
\end{tabular}
\end{center} 
\caption{Results for small exponents.}
\label{lowexp}
\end{table}

\section{Reducing memory requirements}\label{lessmem}

Here we describe a way to reduce the size of the memory required to find the
threshold of completeness for exponents $n=7$ and higher.
We begin with an inefficient method and improve it in a sequence of steps,
finishing with a complete algorithm.

\subsection{Index searching}\label{indexsearch}

To continue, we need to introduce the concept of an {\it index}.
\begin{definition}
An {\em index} is a nonnegative integer representing a finite set of positive $n$th powers,
where the exponent $n$ is explicitly stated or implied by context.
Let $s_i=1$ when power $(i+1)^n$ is in the set, and $s_i=0$ otherwise.
Then the set's index is $I = \sum_{i=0}^\infty s_i2^i$.
The sum of the elements in the set of powers represented by index $I$ is 
$\sum_{i=0}^\infty s_i (i+1)^n$.
Any summable number has at least one corresponding set of powers that contribute to that sum.
A given sum may have more than one index.
For example $25=5^2=4^2+3^2$.
The set $\{5^2\}$ has index $2^{5-1}=16$, and the set $\{3^2,4^2\}$ 
has index $2^{3-1}+2^{4-1}=12$, but the sum of powers corresponding to both indexes is 25.
\label{index}
\end{definition}
Let $b_0, \ldots, b_\mu$ be the available bits of memory for some upper limit $\mu$.
In Section~\ref{warmup}, we iterated Algorithm~\ref{addpower} to set $b_i=1$ 
when $i$ is a summable number.
An alternative way to fill the memory begins with setting all memory bits $b_0, \ldots, b_\mu$ to zero.
Then for each index $I = 0, \ldots, 2^k-1$, where 
$k = \lfloor \mu^{1/n} \rfloor$, compute the sum $v$ of the $n$th powers in the
set represented by $I$, and
if $v \le \mu$, set $b_v = 1$.
This method is far less efficient than the method from Section~\ref{warmup} 
and does not reduce memory requirements, but we will improve it below.

\subsection{Separating sums by congruence class}\label{congclasssums}

In Section~\ref{indexsearch}, at the end of computation, a memory bit 
$b_v$, $0 \le v \le \mu$, was equal to 0 if $v$
is not summable, and 1 if $v$ is summable.
We got this result with a single large computation.
To reduce memory requirements (or to make use of the $\mu+1$ available bits of memory
for determining the summability of integers larger than $\mu$), 
we separate sums into congruence classes mod $2^{gn}$ for
some $g \in \mathbb{Z}^+$.
Let $L = (\mu+1)2^{gn}-1$.
With this new approach, we repeat the following subcomputation for each $m=0,1,\ldots,2^{gn}-1$.
Set all memory bits $b_i$ to zero.
For each index $I = 0, \ldots, 2^k-1$, where 
$k = \lfloor L^{1/n} \rfloor$, compute the sum $v$ of the $n$th powers in the
set represented by $I$ (see Definition~\ref{index}), and
if $v \le L$ and $v \equiv m \pmod{2^{gn}}$, set $b_{(v-m)2^{-gn}} = 1$.
At the end of each subcomputation, a memory bit $b_i$ is equal to 0 if $i2^{gn}+m$
is not summable, and 1 if it is summable.

For a given memory limit $\mu$, the methods of Section~\ref{indexsearch} could only determine
the summability of numbers up to $\mu$, but this new approach can determine summability
of numbers up to limit $L=(\mu+1)2^{gn}-1$.
This algorithm is even slower than the one in Section~\ref{indexsearch}, 
but at least the memory requirements are reduced for a given limit $L$.
The advantage of separating sums by congruence class will become clearer in Section~\ref{evenodd}.

\subsection{Separating even and odd powers}\label{evenodd}

To discuss this optimization, it is useful to introduce the concept of a {\it subindex}.
\begin{definition}
A {\em subindex} is a nonnegative integer representing a finite set of positive 
odd $n$th powers,
where the exponent $n$ is explicitly stated or implied by context.
Let $s_i=1$ when power $(2i+1)^n$ is in the set, and $s_i=0$ otherwise.
Then the set's subindex is $I = \sum_{i=0}^\infty s_i2^i$.
\label{oddindex}
\end{definition}
\begin{definition}
Let $\sigma_n(I)$ be the sum 
of the elements in the set of odd powers represented by subindex $I$: 
$\sigma_n(I) = \sum_{i=0}^\infty s_i (2i+1)^n$, where $I = \sum_{i=0}^\infty s_i2^i$,
and $s_i \in \{0,1\}$ for all $i \in \mathbb{Z}_0^+$.
\label{sigma}
\end{definition}
This optimization starts with the
simple but powerful observation that all even powers are divisible by $2^n$ so that
only odd powers determine a sum's congruence class mod $2^n$.
If we are only looking for sums congruent to $m$ (mod $2^n$), then we need consider only subsets
of the odd powers whose sum is congruent to $m$ (mod $2^n$).
Then we can add any combination of even powers we like without changing
the congruence class of the sum.
So, where the algorithm in Section~\ref{congclasssums} with $g=1$ searched through indexes 
$0, \ldots, 2^k-1$ to cover all subset sums of $S_k(x^n)$, we now cover all the
subset sums of just the odd powers less than or equal to $k^n$ by searching
through the subindexes $I = 0, \ldots, 2^{\lceil k/2 \rceil}-1$.
It is only after finding all subindexes $I$ such that $\sigma_n(I) \equiv m \pmod{2^n}$
and setting memory bit $b_{(\sigma_n(I)-m)2^{-gn}} = 1$
that were turn our attention to the even powers.
Because the sums represented by the memory bits are spaced $2^n$ apart, when we use
Algorithm~\ref{addpower} with $y=p^n$, this has the effect of adding even power $(2p)^n$ to
all the sums in the memory.
So, we run Algorithm~\ref{addpower} for each $y = 1^n, \ldots, \lfloor k/2 \rfloor^n$
to cover all the even powers less than or equal to $k^n$.

So far, we have used the idea in Section~\ref{congclasssums} with $g=1$, but we can go further.
Suppose that we seek sums of powers congruent to $m \pmod{2^{2n}}$
instead of just $m \pmod{2^n}$.
Now, in a first stage, we enumerate all subindexes $I = 0,\ldots,2^{\lceil k/2 \rceil}-1$
and for each $I$, compute its sum of odd powers $s = \sigma_n(I)$,
and if $s \equiv m$ (mod $2^n$), then carry $\lfloor s/2^n \rfloor$ 
and $\lfloor m/2^n \rfloor$ to a nearly identical 
second stage that uses $\lfloor k/2 \rfloor$ in place of $k$.
The first stage took care of the least significant $n$ bits of $m$, and in the second stage 
we can think of all sums as divided by $2^n$.
Again, we go through the subindexes, this time looking for sums of powers
congruent to $\lfloor m/2^n \rfloor$ (mod $2^n$).
A difference between the first and second stage 
is that we add the offset $\lfloor s/2^n \rfloor$ to each sum in the second stage.
In a final step where we think of all sums as divided by $2^{2m}$, we use 
Algorithm~\ref{addpower} to add powers $1^n, 2^n, \ldots, \lfloor k/4 \rfloor^n$ to the memory.
If we step back and do not think of sums as divided by either $2^n$ or $2^{2n}$, the first
stage found sums of odd powers, the second stage contributed sums of powers $x^n$, where
$x \equiv 2$ (mod 4), and the final step contributed sums of powers $x^n$, where
$x \equiv 0$ (mod 4).
See Algorithms~\ref{algodd}~and~\ref{algcheck} for a more 
precise description of this process.
There is no reason why we have to stop there.
We can increase $g$ further to reduce memory requirements at the cost of more 
execution time.

\subsection{Efficiently avoiding sums of powers that are too large}\label{toolarge}

In Section~\ref{evenodd}, enumerating
all the sums of odd powers in $S_k(x^n)$  
involved counting through the subindexes $I = 0,\ldots,2^{\lceil k/2 \rceil}-1$.
We are only interested in sums $\sigma_n(I) \le L = (\mu+1)2^{gn}-1$,
where $\mu+1$ is the number of memory bits available.
However, some of the sums may be larger than $L$.
In fact, it is common for many subindexes in a row to produce sums $\sigma_n(I)$
that are larger than $L$.
This slows down the algorithm considerably.
Given a subindex $I$ where $\sigma_n(I) > L$,
we would like an efficient way to find the next larger subindex $I'$
such that $\sigma_n(I') \le L$.
Theorem~\ref{oddindexstep} is useful here.
\begin{theorem}
\leavevmode
\begin{itemize}

\item[(1)]  Consider a subindex $I$ that has at least two 1s in its binary representation.
Let $2^u$ be the weight of the least significant 1 in the binary representation of $I$,
and let $2^v$ be the weight of the second least significant 1 in the binary representation of $I$.
Then no subindex $I' \in (I, I - 2^u + 2^v)$ is such that $\sigma_n(I') \le \sigma_n(I)$.

\item[(2)] Consider a subindex $I$ that has at most one 1 in its binary representation.
Then no subindex $I' > I$ is such that $\sigma_n(I') \le \sigma_n(I)$.
\end{itemize}
\label{oddindexstep}
\end{theorem}
\begin{proof}
\leavevmode
\begin{itemize}
\item[(1)] Let $j = I - 2^v - 2^u$, where $v > u$.
Then all 1s in the binary representation of 
$j$ have weight larger than $2^v$,
and $(I, I - 2^u + 2^v) = (j + 2^v + 2^u, j + 2^v + 2^v)$.
If $I' \in (I, I - 2^u + 2^v)$, then $I' = j + 2^v + b$, where $b \in (2^u, 2^v)$.
Because $I=j+2^v+2^u$, the binary representations of $I$ and $I'$ differ only in bits of weight less than $2^v$.
For $I$, the only contribution of bits of weight less that $2^v$ to the sum $\sigma_n(I)$ is $(2u + 1)^n$.
For $I'$, the contribution of bits of weight less that $2^v$ to $\sigma_n(I')$ is all the bits in $b$.
But the binary representation of $b$ must either have a 1 of weight 
$2^u$ along with at least one other 1, or $b$
must have a 1 with weight larger than $2^u$.
In either case, $\sigma_n(b) > (2u + 1)^n$, and thus $\sigma_n(I') > \sigma_n(I)$
for all $I' \in (I, I - 2^u + 2^v)$.

\item [(2)] If the binary representation of $I$ has fewer than two 1s, then either $I=0$, 
in which case $\sigma_n(I)=0$ 
and the statement is trivially true,
or $I = 2^u$ for some $u$.
The binary representation of any subindex $I' > I$ must either have a 1 of weight $2^u$ 
along with at least one other 1, or it
must have a 1 with weight larger than $2^u$.
In either case, $\sigma_n(I') > \sigma_n(I)$.
\end{itemize}
\end{proof}
Suppose that the least significant 1 in the binary representation of subindex $I$ has weight $2^u$, 
and the second least significant 
1 has weight $2^v$ (we will deal with the possibility that $I$ does not have two 1s below).
By Theorem~\ref{oddindexstep}, if $I' \in (I, I - 2^u + 2^v)$, then $\sigma_n(I') > \sigma_n(I)$.
An interesting trick from Warren's useful book {\it Hacker's Delight}~\cite[p.\ 11]{Hack} 
for isolating the least significant 1 in the binary representation of $I$ is to 
calculate $I \land (2^W-I)$, where $W$ is any positive integer such that $2^W > I$, and 
$\land$ refers to a bitwise AND operation (see Definition~\ref{bitwisedef}).
Because computers naturally work modulo $2^{32}$ or $2^{64}$ for unsigned integers,
performing $I \land (2^W-I)$ is the same as $I \land -I$ for any $I$ that fits in the computer's
word size.
So we will just write this computation as $I \land -I$.
Because $I \land -I = 2^u$, and $(I-2^u) \land -(I-2^u) = 2^v$,
we can compute $I - 2^u + 2^v$ as follows:
$$ I \gets I - (I \land -I)~~~\textrm{followed by}~~~I \gets I + (I \land -I). $$
If the result is $I=0$ because the binary representation of $I$ started with fewer than two 1s, 
this means there are no remaining 
subindexes $I'>I$ such that $\sigma_n(I') \le \sigma_n(I)$.
So, when we go through the subindexes $I$ from 0 to $2^{\lceil k/2 \rceil}-1$ as
described in Section~\ref{evenodd}, and we encounter an $I$ such that
$\sigma_n(I) > L = (\mu+1)2^{gn}-1$, we use the two {\it Hacker's Delight} steps
above to skip over subindexes $I'$ where $\sigma_n(I') > L$.

\subsection{Pre-computing sums sorted by congruence class}\label{precompute}

In Section~\ref{evenodd}, when enumerating 
all the sums of subsets of odd powers in $S_k(x^n)$ by counting through the subindexes from 0
to $2^{\lceil k/2 \rceil}-1$, we seek sums congruent to $m$ (mod $2^n$).
A more efficient version of this process begins with precomputing lists of some
of the sums of subsets of odd powers.
For some constant $p$, we precompute the sums $s_J=\sigma_n(J)$ for subindexes 
$J = 0,\ldots,2^p - 1$, making a separate list based on 
each sum's congruence class mod $2^n$, and we sort 
the sums $s_J$ within each list from smallest to largest.
With each sum, we also store its corresponding subindex $J$.
These precomputed lists allow us to speed up the computation 
as shown in Algorithm~\ref{algodd}.

\subsection{Reducing the number of odd powers}\label{kprime}

Here we describe an optimization that involves ignoring some of the odd powers.
This is useful for exponent $n=8$.
We begin with an observation about even exponents.

If we add up an odd number of odd powers we get an odd sum.
So, if $\sigma_n(I)$ is odd then subindex $I$ must have odd Hamming weight.
(We use ``Hamming weight'' to mean the number of 1 bits in the binary representation 
of a nonnegative integer.)
Similarly, if $\sigma_n(I)$ is even then subindex $I$ must have even Hamming weight.
We can extend this idea further with Lemma~\ref{mod2u} and Theorem~\ref{hamwt}.
\begin{lemma}
Suppose $a \in \mathbb{Z}$ and $u \in \mathbb{Z}^+$.  Then
$(2a+1)^{2^u} \equiv 1 \pmod{2^{u+2}}$.
\label{mod2u}
\end{lemma}
\begin{proof}
We proceed by induction.
Consider $u=1$.
$$(2a+1)^2 = 4a^2+4a+1 = 8\tbinom{a+1}{2} + 1 \equiv 1\pmod{8}.$$
Thus this lemma is true for $u=1$.
Now assume it is true for $u=v$, for some $v>0$.
So $(2a+1)^{2^v} = 2^{v+2}b+1$, for some integer $b$.
Then 
$$(2a+1)^{2^{v+1}} = (2^{v+2}b+1)^2 = 2^{2v+4}b^2 + 2^{v+3}b+1 \equiv 1\pmod{2^{v+3}}.$$
Thus, if this lemma is true for $u=v$, it is also true for $u=v+1$.
This completes the proof by induction.
\end{proof}
\begin{theorem}
Consider an exponent $n$ that is divisible by $2^u$, $u>0$.
If a subindex $I$ has Hamming weight $h$, then $\sigma_n(I) \equiv h \pmod{2^{u+2}}$.
\label{hamwt}
\end{theorem}
\begin{proof}
A consequence of Lemma~\ref{mod2u} is that all odd powers for exponent $n$ are 
congruent to 1 (mod $2^{u+2}$).
When subindex $I$ has Hamming weight $h$, $\sigma_n(I)$ is the sum of
$h$ odd powers.
Thus $\sigma_n(I) \equiv h \pmod{2^{u+2}}$.
\end{proof}
For exponent $n=8$, let $I$ be a subindex with Hamming weight $h$ and let $q=\sigma_8(I)$.
Then by Theorem~\ref{hamwt}, $h \equiv q$ (mod 32).
So, when we are enumerating subindexes $I$ looking for
those such that $\sigma_8(I) \equiv m \pmod{2^{8g}}$ for some $g \ge 1$, 
we need only consider subindexes with Hamming weight congruent to $m$ (mod 32).
However, the number of subindexes with Hamming weight 
congruent to $m$ (mod 32) varies considerably with $m$.
Consider the case of $k=80$ so that there are only 40 odd powers.
For $m=4$, a subindex must have Hamming weight 4 or 36.
There are only ${40 \choose 4} + {40 \choose 36} =$~182,780 such subindexes available.
In contrast, for $m=20$, there are ${40 \choose 20} =$~137,846,528,820 subindexes available.
This increase by a factor of over 750,000
makes a huge difference in how long it takes to enumerate all the subindexes.
Additionally, the extra computation is mostly wasted because in Algorithm~\ref{algodd} below, 
we are just setting the same memory bits to 1 over and over again.
To avoid this waste, we eliminated some of the larger odd powers from our search.
For $k=80$, we would normally consider the odd powers
$1^8, 3^8, \ldots, 79^8$.
Instead, we defined $k'$ to be an upper limit on the number of 
odd powers used.
So, when computing subset sums of $S_k(x^8)$, we did not include the powers
$(2k'+1)^8, (2k'+3)^8, \ldots, (2\lceil k/2 \rceil-1)^8$ in any of the subsets.
We determined a suitable $k'$ for each congruence class $m$ (mod 32) experimentally.
If at any point $k'$ was not large enough to satisfy the conditions of Theorem~\ref{maintheorem},
we simply increased $k'$ (without letting $2k'-1$ exceed $k$) and tried again.
See Section~\ref{exponent8} for more details on this optimization.

Another possible use for this observation about the Hamming weight of subindexes
would be to directly search through just those subindexes with the correct Hamming weight
instead of just trying every subindex.
This idea works well for exponent $n=16$ as we will see in Section~\ref{exponent16}, but for exponent $n=8$,
it was more efficient to use pre-computed sums of odd powers as described in Section~\ref{precompute}.

\subsection{Efficient method for checking one congruence class}\label{efficient}

The goal for a given exponent $n$ is to find integers $t$ and $k$ that will
satisfy the requirements of Theorem~\ref{maintheorem}.
We do not know in advance which values of $t$ and $k$ will work; finding them
is an iterative process.
We make guesses and perform computations to reveal whether we need
to change these guesses.
Combining the efficiency improvements in the subsections above gives the following algorithms
that we can use in this iterative process.
Algorithm~\ref{algodd} performs the stages of computing sums of odd powers.
One use for this algorithm is to check the range from $t+1$ to $t+(k+1)^n$ for numbers
not summable with $S_k(x^n)$.
If a number is not summable, then we have a new larger candidate for $t$.
Another use is to find numbers smaller than $t$ that are not summable with $S(x^n)$.
In this case, we use $\lfloor t^{1/n} \rfloor$ in place of $k$ so that we are considering all
powers not larger than $t$.
Algorithm~\ref{algcheck} uses Algorithm~\ref{algodd} to determine whether we need a larger
value for $t$ 
to satisfy Theorem~\ref{maintheorem}
and to determine if there exists a larger candidate $c$ for the threshold of completeness.
\begin{algorithm} {\it Calculate Sums of Odd Powers for One Congruence Class.} \label{algodd}
The inputs are a congruence class $m$ mod $2^{gn}$, 
an exponent $n$, 
the number of remaining stages $g$ of adding sums of odd powers,
an offset $f$ to be added to each sum,
the number $k$ which sets $k^n$ to be the largest power used in sums of powers,
the number $k'$ which sets $(2k'-1)^n$ to be the largest odd power used in the sums,
and the upper limit $L$ on the size of sums sought.
The output is a memory consisting of bits $b_0,\ldots,b_\mu$, where
$\mu = \lfloor (L - m)/2^{gn} \rfloor$.
At the end of the algorithm, $b_a=1$ if $a2^{gn}+m$ is 
summable using odd powers $1^n,3^n,\ldots,(2k'-1)^n$
and all even powers less than or equal to $k^n$ 
except for those of the form $x^n$ where $x \equiv 0 \pmod{2^g}$.
Bit $b_a=0$ otherwise.
For each $d=1,2,\ldots, p$, we use a precomputed table of pairs $(s_j,j)$,
where $j$ is a $d$-bit subindex, and $s_j=\sigma_n(j)$ is a sum of odd powers in $S_{2d}(x^n)$.
Each table is separated into distinct lists
by each sum's congruence class mod $2^n$.
Each list is sorted from smallest to largest sum.
\begin{tabbing}
\hspace*{0.25in}\=\hspace*{0.25in}\=\hspace*{0.25in}\=\hspace*{0.25in}\=\hspace*{0.25in}\=\kill
\> \textbf{for} $a = 0,1,\ldots,\mu$ \textbf{do} $b_a \gets 0$ \textbf{end for} \\
\> maxq $\gets L-f$ \\
\> $i \gets 0$ \\
\> $q \gets 0$ \\
\> \textbf{do} \\
\> \> use precomputed table of sums of odd powers with subindexes $\min(p,k')$ bits long \\
\> \> use precomputed list of sums of odd powers congruent to $m-q-f \pmod{2^n}$ \\
\> \> \textbf{if} $g > 1$ \textbf{then} \\
\> \> \> \textbf{for} each precomputed pair $(s_j,j)$ such that $s_j \le \textrm{maxq}-q$ \textbf{do} \\
\> \> \> \> recursively call Algorithm~\ref{algodd} with inputs \\
\> \> \> \> \> ($\lfloor m/2^n \rfloor$, $n$, $g-1$, $\lfloor (q+f+s_j)/2^n \rfloor$, $\lfloor k/2 \rfloor$, 
$\lceil \lfloor k/2 \rfloor / 2 \rceil$, $\lfloor L/2^n \rfloor$) \\
\> \> \> \textbf{end for} \\
\> \> \textbf{else} \\
\> \> \> \textbf{for} each precomputed pair $(s_j,j)$ such that $s_j \le \textrm{maxq}-q$ \textbf{do} \\
\> \> \> \> $b_{\lfloor (q+f+s_j)/2^n \rfloor} \gets 1$ \\
\> \> \> \textbf{end for} \\
\> \> \textbf{end if} \\
\> \> $i \gets i + 2^p$ \\
\> \> $q \gets \sigma_n(i)$ \\
\> \> \textbf{while} $q > \textrm{maxq}$ and $i \ne 0$ and $i < 2^{k'}$ \textbf{do} \\
\> \> \> $i \gets i - (i \land (-i))$ \\
\> \> \> $i \gets i + (i \land (-i))$ \\
\> \> \> $q \gets \sigma_n(i)$ \\
\> \> \textbf{end while} \\
\> \textbf{while} $i \ne 0$ and $i < 2^{k'}$\\
\end{tabbing}
\end{algorithm}
\begin{algorithm} {\it Check One Congruence Class.} \label{algcheck}
The inputs are a congruence class $m$ mod $2^{gn}$, 
an exponent $n$, 
the current largest candidate $c$ for the threshold of completeness,
the current value for $t$ being used to satisfy Theorem~\ref{maintheorem},
the number of stages $g$ of adding sums of odd powers,
limits $k$ and $k'$ ($k' \le \lceil k/2 \rceil$) on the size of powers used in the sums,
and the upper limit $L$ on the size of sums sought.
For odd powers, we do not use
any powers larger than $(2k'-1)^n$.
For even powers, we do not use
any powers larger than $k^n$.
We use a memory consisting of bits $b_i$, $i=0,1,\ldots, \mu$, where
$\mu = \lfloor (L - m)/2^{gn} \rfloor$.
To satisfy the requirements of Theorem~\ref{maintheorem}, we must have $L \ge t+(k+1)^n$.
The output is a boolean value along with possible updates to the values of $c$, $t$, $k$, and $L$.
The output is (true) if the conditions of Theorem~\ref{maintheorem} are met for 
congruence class $m$ (mod $2^{gn}$), or if we are able to update $c$ or $t$
to meet these conditions.
Otherwise, the output is (false) and either $k$ has been increased or $L$
has been increased (in which case we must run this algorithm again with these new inputs).
When the output is (false), it is necessary to start the process of checking all congruence classes
$m$ (mod $2^{gn}$) over again.
When the memory size must increase, the suggested size may be larger than necessary, because
$k$ may have grown too large.
In practice, when the memory size had to increase, we often chose the new size and the 
starting value of $k$ manually.
\begin{tabbing}
\hspace*{0.25in}\=\hspace*{0.25in}\=\hspace*{0.25in}\=\hspace*{0.25in}\=\hspace*{0.25in}\=\kill
\> $z \gets L$ \\
\> \textbf{do} \\
\> \> call Algorithm~\ref{algodd} with inputs ($m$, $n$, $g$, $0$, $k$, $k'$, $z$) \\
\> \> \textbf{for} $j = 1,2,\ldots,\lfloor k/2^g \rfloor$ \textbf{do} \\
\> \> \> call Algorithm~\ref{addpower} with power $j^n$ \\
\> \> \textbf{end for} \\
\> \> find the largest $a \in [0,\mu]$ such that $b_a = 0$ \\
\> \> \textbf{if} there is no such $a$ \textbf{then} \textbf{return} (true) \textbf{end if} \\
\> \> $z \gets m+a2^{gn} - 1$ \\
\> \> \textbf{if} $z < c$ \textbf{then} \textbf{return} (true) \textbf{end if} \\
\> \> $k' \gets k' + 1$ \\
\> \textbf{while} $k' \le \lceil k/2 \rceil$ \\
\> $v \gets 0$ \\
\> \textbf{while} $(v < z)$ and ($\exists$ minimum $a \in (\lfloor (t-m)/2^{gn} \rfloor,\mu]$ such that $b_a=0$) \textbf{do} \\
\> \> $v \gets m+a2^{gn}$ \\
\> \> \textbf{if} $(v-t)>(k+1)^n$ \textbf{then} $z \gets v-1$ \textbf{else} $t \gets v$ \textbf{end if} \\
\> \textbf{end while} \\
\> call Algorithm~\ref{algodd} with inputs ($m$, $n$, $g$, $0$, 
$\lfloor t^{1/n} \rfloor$, $\lceil \lfloor t^{1/n} \rfloor/2 \rceil$, $t$) \\
\> \textbf{for} $j = 1,2,\ldots,\lfloor t^{1/n}/2^g \rfloor$ \textbf{do} \\
\> \> call Algorithm~\ref{addpower} with power $j^n$ \\
\> \textbf{end for} \\
\> find the largest $a \in [0,\mu]$ such that $b_a = 0$ \\
\> $v \gets m+a2^{gn}$ \\
\> \textbf{if} $v>c$ \textbf{then} \\
\> \> $c \gets v$ \\
\> \> \textbf{if} $t<c$ \textbf{then} $t \gets c$ \textbf{end if} \\
\> \> \textbf{if} $(L-c) < (k+1)^n$ \textbf{then} $L \gets c+(k+1)^n$; \textbf{return} (false) \textbf{end if} \\
\> \textbf{end if} \\
\> \textbf{if} $(L-t) < (k+1)^n$ \textbf{then} $k \gets k + 1$; $t \gets c$; \textbf{return} (false) \textbf{end if} \\
\> \textbf{if} $(z-t) < (k+1)^n$ \textbf{then} \textbf{return} (false) \textbf{end if} \\
\> \textbf{return} (true) \\
\end{tabbing}
\end{algorithm}

\subsection{Other observations}\label{other}

Another observation for $n=8$ is that all powers are congruent to 0, 1, or 16 modulo 17.
For each exponent, we can come up with many other similar facts for different moduli.
There may be some way to combine several such constraints on powers
to speed up the search for the threshold of completeness, but we do not see
a way to use these ideas to further improve on the optimizations described above.

\section{Exponent 7}\label{exponent7}

We used Algorithm~\ref{algcheck} to find $T(S(x^7))$.
We began by calling this algorithm with $m=0$, $n=7$, $c=0$, $t=0$, $g=1$, $k=40$, $k'=20$,
and $L=10^{12}$.
Because the exponent is odd, there is nothing to be gained by reducing the number of odd powers 
as explained in Section~\ref{kprime}, so we always used $k'=\lceil k/2 \rceil$.
For the first 24 calls, the algorithm returned (false) and increased one or more 
of $t$, $k$, and $L$, so we
kept starting over at $m=0$.
After that, the algorithm would return (true) for several congruence classes mod $2^7$ 
before failing at some point
and forcing us to start over again.
Eventually, Algorithm~\ref{algcheck} succeeded for all $m=0, 1, \ldots, 2^7-1$ 
using $t=$~865,130,689,840 and $k=45$
to give $c = T(S(x^7)) = $~766,834,015,734.
The whole process took 19 minutes.
If we reduce $L$ to the bare minimum required, the time required to confirm this result is 7.7 minutes
using 1.2 GB of memory.

\section{Exponent 8}\label{exponent8}

The work to this point has been a warm-up for the main contribution, which is the threshold of completeness
for exponent $n=8$.
We found this threshold in four steps.
First we did an initial exploration to find roughly the right sizes of inputs to Algorithm~\ref{algcheck}.
Next we searched for larger values of $c$, $t$, and $k$.
Then we found suitable values for $k'$ to minimize computation time.
Finally, we did the full computation to get $T(S(x^8))$.

Before the initial exploration, it was clear that using only $g=1$ stage of adding odd powers
would require too much memory.
In Section~\ref{kprime}, we saw that a subindex must have Hamming weight $h \equiv m \pmod{32}$.
To create a sum of odd powers congruent to 31 (mod 32), the set of odd powers 
contributing to this sum must 
contain at least 31 odd powers, and the subindex for this set
must have a Hamming weight
of at least 31.
So, $k'$ must be at least 31, and $k$ must be at least 61.
Theorem~\ref{maintheorem} requires $L \ge t+(k+1)^8$, and thus
$L \ge 62^8$.
The number of memory bits required is $\lceil L/2^{gn} \rceil$.
With $g=1$, this requires a 100 GB memory, which is beyond the resources we had available.
Using $g=2$ reduces this to 400 MB, and leaves room for expansion
as $t$ and $k$ increase.

In the initial exploration, we focused on the congruence class $m$ (mod $2^{16}$) 
likely to give few subindexes.
This has two advantages.
The first is that is takes less computation time to go through these subindexes.
The second is that it makes intuitive sense that in such a case we get our best chance 
of finding a large candidate for the threshold of completeness $c$, and a large value for $t$
to use for Threorem~\ref{maintheorem}.
There is no guarantee that this intuition is correct, but the only cost if we are wrong is greater execution time;
it will not lead to an incorrect final result.
Given $k'$ and $m$, the number of subindexes with Hamming
weight congruent to $m$ (mod 32) is 
$$ Q_{32}(k', m) = \sum_{\substack{i \equiv m \hspace{-5pt} 
\pmod{32} \\ 0 \le i \le k'}} {k' \choose i}.$$
This is a minimum when $m \equiv \lfloor k' /2 \rfloor - 16$ (mod 32).
When $k'$ is odd, we could have used $m \equiv \lceil k'/2 \rceil - 16 \pmod{32}$, because it
gives the same sum (the terms are identical but in reverse order).
However, we prefer the first minimum because it has more high Hamming weight subindexes $I$
whose sums of odd powers $\sigma_n(I)$ tend to be larger.
When we add in even powers, larger sums of odd powers have a greater 
tendency to produce irrelevant total sums that
exceed $L$.
We began our initial exploration with $m=0$, $n=8$, $c=0$, $t=0$, $g=2$, $k=64$, $k'=32$,
and $L=10^{14}$.
As Algorithm~\ref{algcheck} changed $c$, $t$, $k$, and $L$, we changed $k'$ to equal 
$\lceil k/2 \rceil$ and $m$ to 
equal $\lfloor k'/2 \rfloor-16$.
After 5.5 hours, call number 172 returned (true) for inputs $m=4$, $n=8$, 
$c=t=$~4,739,704,992,497,666, $g=2$, $k=79$, $k'=40$, and $L=$~6,417,426,592,497,666.

In the next step, we explored the most promising congruence classes $m$ (mod $2^{16}$) to
give a value of $c$ closest to the actual threshold of completeness,
and values of $t$ and $k$ closest to those needed for Theorem~\ref{maintheorem}.
There are $2^{11}$ such congruence classes in each mod 32 congruence class.
We judged congruence classes 4 and 3 (mod 32) to be the most promising based on the 
number of subindexes available for $k=79$ and $k'=40$.
First, we checked $m=4, 36, \ldots, 2^{16}-28$, but Algorithm~\ref{algcheck} returned (true) in every case.
Then we checked $m=3, 35, \ldots, 2^{16}-29$ to reveal that we needed to use $k=80$,
$t=$~5,784,315,489,954,275, and $L=$~7,637,335,678,806,116.
Although we did not know it at the time, these turned out to be the final values needed for use with
Theorem~\ref{maintheorem}.

The next step was to find the right $k'$ values for minimizing the execution time of the final step.
Let $k'_m$ be the smallest $k'$ such that Algorithm~\ref{algcheck} returns (true) for
congruence class $m$ (mod $2^{16}$).
We found $k'_0, k'_1, \ldots, k'_{31}$:
\begin{displaymath}
\begin{array}{l}
{\textrm{\small 36,37,39,40,38,32,26,22,21,21,20,21,21,21,22,22,23,24,25,25,26,27,28,29,29,30,31,32,33,33,34,35}}. \\
\end{array}
\end{displaymath}
We used these values in the final step (below) to speed up the computation.
For a given $m < 2^{16}$, let $a = m \bmod{32}$.
We assumed that a reasonable starting guess for 
$k'_m$ is $k'_a$.
In some cases, $k'_a$ was not large enough, and Algorithm~\ref{algcheck} had to increase it.
Let $k^*_a$ be the smallest value of $k'$ such that Algorithm~\ref{algcheck} returns (true) for
every congruence class $m=a, a+32, \ldots, a+2^{16}-32$ (mod $2^{16}$).
Here is the final list of $k^*_0, k^*_1, \ldots, k^*_{31}$:
\begin{displaymath}
\begin{array}{l}
{\textrm{\small 36,37,40,40,39,32,27,23,22,21,21,21,21,22,22,23,23,24,25,26,26,27,28,29,30,30,31,32,33,33,34,35}} . \\
\end{array}
\end{displaymath}
If we calculate $Q_{32}(k^*_a, a)$ for $a=0,1,\ldots,31$, the range is from 40,920 to 3,839,160.
However, if we had just used $k'=40$ (which is the number of odd powers in $S_k(x^8)$ for
$k=80$), the maximum $Q_{32}(40, m)$ occurs for $m \equiv 20 \pmod{32}$, and is
$Q_{32}(40, 20)=$~137,846,528,820.
In contrast, $k' = 26$ is sufficient for $m \equiv 20 \pmod{32}$, 
and because $Q_{32}(26, 20) =$~230,230,
the more efficient version is more than 5 orders of magnitude faster.
Thus the optimization involving $k'$ to use the minimum number of 
odd powers necessary is critical.

In the final step, we went through every congruence class 
$m=0, 1, \ldots, 2^{16}-1$ (mod $2^{16}$)
to check whether the conditions of Theorem~\ref{maintheorem} are satisfied, and to see if there
are any larger candidates for the threshold of completeness.
In every case, Algorithm~\ref{algcheck} returned (true), indicating that the conditions are met,
and while checking the $m = 2466$ case, we found the largest candidate $c = T(S(x^8))$ = 4,968,618,780,985,762.
This required 22.6 days of computation time.
Fortunately, we required only 13.6 GB of memory and were able to run two instances concurrently
on a 32 GB laptop.
We were also fortunate that the final candidate $c$ is smaller than the value of $t$
we found early on, so it was not necessary to
restart the search through all congruence classes when we found a larger candidate $c$.

\section{Exponents 9 to 12}\label{exponent9}

Starting with exponent $n=9$, finding thresholds of completeness requires far more computing power 
than we had available.
We had to content ourselves with random searching of promising congruence classes 
mod $2^{gn}$ to find 
the largest non-summable numbers possible within our computation constraints.

For exponent $n=9$, we did an initial exploration to get to 
$k=73$, and $t \approx 1.5 \times 10^{17}$.
We found that using $g=2$
required about 110 GB, so we had to
go to $g=3$ to reduce this to about 220 MB.
Thus each run with Algorithm~\ref{algcheck} covered numbers in one congruence
class mod $2^{27}$.
Initially, each congruence class took about 3 hours to complete.
Fortunately, a new idea reduced this time considerably.
For exponents $n \ge 9$, the time required to perform 
Algorithm~\ref{algodd} dominates the
time required for Algorithm~\ref{addpower}.
So, the new idea is to periodically pause Algorithm~\ref{algodd}, 
make a temporary copy of the memory
bits $b_0,\ldots,b_\mu$,
and perform Algorithm~\ref{addpower} on this temporary copy 
to see if we have already proven that all numbers in
congruence class $m$ mod $2^{27}$ in the range 
from $t+1$ to $t+(k+1)^9$ are summable so that we can quit early.
This reduced the average time to check a congruence class mod $2^{27}$
from 3 hours to 51 minutes.
However, the total run time for all congruence classes is still about 13 millennia.
So, we were content to choose several thousand congruence classes 
at random and report the largest candidate for 
threshold of completeness we could find (see Table~\ref{ToC}).
A side effect of this improvement is that for $n \ge 9$ we do not need the $n=8$ trick
of using only a subset of the set of powers $S_k(x^n)$ (see Section~\ref{kprime});
if a congruence class is slow because it produces many sums of powers,
it will likely be possible to quit early using this new improvement.
We used this improvement for all exponents 9 and larger.

We used an additional idea for the even exponents that we will
illustrate using the $n=12$ case.
For $n=12$ and $g=3$, Algorithm~\ref{algcheck} seeks subindexes $I$ with 
$\sigma_{12}(I) \equiv m \pmod{2^{36}}$.
By Theorem~\ref{hamwt}, because exponent 12 is divisible by 4, 
the Hamming weight of such a subindex $I$ 
must be congruent to $\sigma_{12}(I)$ mod 16.
So, the Hamming weight of $I$ must be congruent to $m$ mod 16.
The number of subindexes $I < 2^k$ satisfying this Hamming weight requirement is
$$ Q_{16}(\lceil k/2 \rceil, m) = \sum_{\substack{i \equiv m \hspace{-5pt} 
\pmod{16} \\ 0 \le i \le \lceil k/2 \rceil}} {\lceil k/2 \rceil \choose i}.$$
This is a minimum when $m \equiv \lfloor (k+1) /4 \rfloor - 8$ (mod 16).
We judged these values of $m$ to be the most promising for finding
large candidates for $c$ and $t$ with Algorithm~\ref{algcheck}.
In case this reasoning is incorrect, we tried some values of $m$ 
from other congruence classes mod 16, but
found that they did not give better results.

For exponents 9 to 12, we were able to check enough congruence classes $m$
that we appeared to find parameters $k$ and $t$
in the correct range for Theorem~\ref{maintheorem}.
Table~\ref{exp9_12} shows the best parameters we found for each of these
exponents as well as the estimated number of cores required to check all 
congruence classes and find
the threshold of completeness within one year.
The corresponding largest candidates we found for the threshold of completeness
are in Table~\ref{ToC}.
When we check other congruence classes $m$, we fail to improve on these parameters
in the vast majority of cases.
However, because we have checked such a small fraction of available congruence classes,
the likelihood that we have found the actual threshold of completeness is very low.
\setlength{\tabcolsep}{6pt}
\begin{table}
\normalsize
\begin{center}
\begin{tabular}{|c|c|c|r|c|} 
\hline
 & & & & \\[-10pt]
 & & & & Core-Years \\
$n$ & $k$ & $g$ & \multicolumn{1}{c|}{$t$} & to Complete \\
\hline \hline
 & & & & \\[-9pt]
9 & 74 & 3 & 160,170,705,729,301,541 & $1.3 \times 10^4$ \\
10 & 74 & 3 & 14,784,582,277,082,304,038 & $1.9 \times 10^5$ \\
11 & 79 & 4 & 1,692,580,057,933,058,867,601 & $5.1 \times 10^9$ \\
12 & 89 & 4 & 640,711,717,768,919,776,264,350 & $1.2 \times 10^{12}$ \\
\hline
\end{tabular}
\end{center} 
\caption{Best results so far for exponents 9 to 12.}
\label{exp9_12}
\end{table}

\section{Exponents 13 to 15}\label{exponent13}

For exponents 13 to 15, every run of Algorithm~\ref{algcheck} produced a new
larger candidate $c$ for the threshold of completeness.
This means that we are very likely not in the correct range of parameter
values $k$ and $t$ to satisfy the conditions of Theorem~\ref{maintheorem}.
The values of $k$ we used for these exponents were 96, 96, and 98, respectively.
For each exponent, the last run took weeks to complete,
and the next run with larger parameter values would likely take
even longer.
Further, the lower bounds on threshold of completeness values in Table~\ref{ToC} for these
exponents contain suspicious strings of 9s.
This is because we happened to choose round numbers for the limit $L$,
and Algorithm~\ref{algcheck} found a non-summable value not much below $L$.
The actual thresholds of completeness could easily be orders of magnitude larger
than our best efforts so far for these exponents.

\section{Exponent 16}\label{exponent16}

Using Theorem~\ref{hamwt}, we know that if we are examining congruence class $m$
mod $2^{16g}$ for exponent 16,
the Hamming weight of subindexes must be congruent to $m$ (mod 64).
We modified Algorithm~\ref{algodd} to search through only those subindexes
with the correct Hamming weight rather than use the pre-computed sorted table of
sums of odd powers (see Section~\ref{precompute}).
This sped up the calculations significantly allowing us to complete the last run that
produced the $n=16$ entry in Table~\ref{ToC} in a few weeks despite the fact that
we needed to use $k=164$, which is significantly larger than the values we needed for
smaller exponents.
However, there is no reason to believe that we are particularly close to the
actual threshold of completeness.

\section{Conclusion}\label{conclusion}

The thresholds of completeness for sets of positive $n$th powers were
known for exponents up to 7.
Our main contribution is to show that the threshold of completeness for $n=8$ is
$T(S(x^8))$ = 4,968,618,780,985,762.
We also found lower bounds for exponents 9 to 16.
Using 200,000 computer cores, our methods could find $T(S(x^9))$ in about a month and 
$T(S(x^{10}))$ in about a year.
But the computing power required for higher exponents is impractical
without significant improvements to our methods.

\begin{thebibliography}{99}

\bibitem{DP74} R.\ E.\ Dressler and T.\ Parker, 12,758, {\it Math.\ Comp.} 
\textbf{52} (1974), 313--314.

\bibitem{FN15} C.\ Fuller and R.\ H.\ Nichols, Generalized anti-Waring numbers, 
{\it J.\ Integer Sequences} \textbf{18} (2015), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Fuller/fuller2.html}{Article 15.10.5}.

\bibitem{Gra64} R.\ L.\ Graham, Complete sequences of polynomial values, {\it Duke Math.\ J.} 
\textbf{31} (1964), 275--285.

\bibitem{Kim17} D.\ Kim, On the largest integer that is not a sum of distinct positive {\it n}th powers, 
{\it J.\ Integer Sequences} \textbf{20} (2017), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL20/Kim/kim6.html}{Article 17.7.5}.

\bibitem{Lin70} S.\ Lin, Computer experiments on sequences which form integral bases, 
in J.\ Leech, ed., {\it Computational Problems in Abstract Algebra}, Pergamon Press, 1970, 
pp.\ 365--370.

\bibitem{Mor21} M.\ Morse, Recurrent geodesics on a surface of negative curvature, 
{\it Trans.\ Amer.\ Math.\ Soc.} \textbf{22} (1921), 84--100.

\bibitem{Pat92} C.\ Patterson, {\it The Derivation of a High Speed Sieve Device}, 
Ph.D.\ thesis, University of Calgary, 1992.

\bibitem{Por09} {\v S}.\ Porubsk{\'y}, Richert's theorem, preprint, 2009, 
\url{https://www.cs.cas.cz/portal/AlgoMath/NumberTheory/AdditiveNumberTheory/RichertTheorem.htm}.

\bibitem{Pro1851} E.\ Prouhet, M{\'e}moire sur quelques relations entre les puissances des nombres, 
{\it C.\ R.\ Math.\ Acad.\ Sci.\ Paris} \textbf{33} (1851), 225.

\bibitem{Ric49} H.\ Richert, {\"U}ber Zerf{\"a}llungen in ungleiche Primzahlen, 
{\it Math.\ Z.} \textbf{52} (1949), 342--343.

\bibitem{RS54} K.\ F.\ Roth and G.\ Szekeres, Some asymptotic formulae in the theory of partitions, 
{\it Q.\ J.\ Math.} \textbf{5} (1954), 241--259.

\bibitem{Sie88} W.\ Sierpi\'nski, {\it Elementary Theory of Numbers}, 2nd ed., translated from Polish, 
A.\ Schinzel, ed.,
North-Holland and PWN-Polish Scientific Publishers, Vol.\ 31, 1988.

\bibitem{OEIS} N.\ J.\ A.\ Sloane et al.,
The On-Line Encyclopedia of Integer Sequences, 2023.
Available at \url{https://oeis.org}.

\bibitem{Spr48} R.\ Sprague, {\"U}ber Zerlegungen in ungleiche Quadratzahlen, 
{\it Math.\ Z.} \textbf{51} (1948), 289--290.

\bibitem{Spr48proof} R.\ Sprague, {\"U}ber Zerlegungen in {\it n}-te Potenzen 
mit lauter verschiedenen Grundzahlen, 
{\it Math.\ Z.} \textbf{51} (1948), 466--468.

\bibitem{Thu06} A.\ Thue, {\"U}ber unendliche Zeichenreihen, 
{\it Norske vid.\ Selsk.\ Skr.\ Mat.\ Nat.\ Kl.}
\textbf{7} (1906), 1--22.
Reprinted in T.\ Nagell, ed., {\it Selected Mathematical Papers of Axel Thue}, 
Universitetsforlaget, Oslo, 1977, pp.\ 139--158.

\bibitem{Thu12} A.\ Thue, {\"U}ber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, 
{\it Norske vid.\ Selsk.\ Skr.\ Mat.\ Nat.\ Kl.} \textbf{1} (1912), 1--67.
Reprinted in 
T.\ Nagell, ed., {\it Selected Mathematical Papers of Axel Thue}, Universitetsforlaget, 
Oslo, 1977, pp.\ 413--478.

\bibitem{Hack} H.\ Warren, Jr., {\it Hacker's Delight}, Pearson Education Inc., Addison-Wesley, 2003.

\bibitem{Wri59} E.\ M.\ Wright, Prouhet's 1851 solution of the Tarry-Escott problem of 1910, 
{\it Amer.\ Math.\ Monthly} \textbf{66} (1959), 199--201.
\end{thebibliography}

\bigskip
\hrule\bigskip
\noindent 2010 \textit{Mathematics Subject Classification}:
Primary 11P05.

\noindent \textit{Keywords:}
threshold of completeness, anti-Waring number, sum of powers.

\bigskip
\hrule
\bigskip

\noindent
(Concerned with sequences
\seqnum{A001661} and
\seqnum{A010060}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  January 21 2023; 
revised versions received  February 4 2023; May 16 2023; June 1 2023.
Published in {\it Journal of Integer Sequences}, June 6 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


