On the Largest Integer that is not a Sum of Distinct Positive nth Powers

Doyon Kim Department of Mathematics and Statistics Auburn University Auburn, AL 36849 USA

                      dzk0028@auburn.edu

Abstract

It is known that for an arbitrary positive integer n the sequence S(x^{n}) = (1^{n}, 2^{n}, …) is complete, meaning that every sufficiently large integer is a sum of distinct nth powers of positive integers. We prove that every integer

m ≥ (b − 1)2^{n−1}(r + \frac{2}{3}(b − 1)(2^{2n} − 1) + 2(b − 2))^{n} − 2a + ab,

where a = n!2^{n^{2}}, b = 2^{n^{3}}a^{n−1}, r = 2^{n^{2}−n}a, is a sum of distinct positive nth powers.

1 Introduction

Let S = (s_{1}, s_{2}, …) be a sequence of integers. The sequence S is said to be complete if every sufficiently large integer can be represented as a sum of distinct elements of S. For a complete sequence S, the largest integer that is not representable as a sum of distinct elements of S is called the threshold of completeness of S. We let θ_{S} denote the threshold of completeness of S.

The threshold of completeness is often very difficult to find even for a simple sequence. For an arbitrary positive integer n, let S(x^{n}) denote the sequence of nth powers of positive integers, i.e., S(x^{n}) = (1^{n}, 2^{n}, …). The completeness of the sequence was proved in 1948, by Sprague [6]. In 1954, Roth and Szekeres [5] further generalized the result by proving that if f(x) is a polynomial that maps integers into integers, then S(f) = (f(1), f(2), …) is complete if and only if f(x) has a positive leading coefficient and for any prime p there exists an integer m such that p does not divide f(m). In 1964, Graham [2] re-proved the theorem of Roth and Szekeres using alternative elementary techniques.

However, little is known about the threshold of completeness of S(x^{n}). The value θ_{S(x^{n})} is known only for n ≤ 6. The values are as follows: θ_{S(x)} = 0, θ_{S(x^{2})} = 128 [7], θ_{S(x^{3})} = 12758 [2], θ_{S(x^{4})} = 5134240 [3], θ_{S(x^{5})} = 67898771 [4], θ_{S(x^{6})} = 11146309947 [1]. Sprague, Roth and Szekeres, and Graham proved that S(x^{n}) is complete, but they were not interested in the size of θ_{S(x^{n})}. The values θ_{S(x^{n})} for 3 ≤ n ≤ 6 were found by methods that require lengthy calculations assisted by computer, and they do not give any idea on the size of θ_{S(x^{n})} for general n.

In this paper, we establish an upper bound of θ_{S(x^{n})} as a function of n. Using the elementary techniques Graham used in his proof, it is possible to obtain an explicit upper bound of the threshold of completeness of S(x^{n}) = (1^{n}, 2^{n}, 3^{n}, …). Since the case n = 1 is trivial, we let n be a positive integer greater than 1. We prove the following theorem:

Theorem 1. Let a = n!2^{n^{2}}, b = 2^{n^{3}}a^{n−1} and r = 2^{n^{2}−n}a. Then

θ_{S(x^{n})} < (b − 1)2^{n−1}(r + \frac{2}{3}(b − 1)(2^{2n} − 1) + 2(b − 2))^{n} − 2a + ab.

The theorem yields the result

θ_{S(x^{n})} = O((n!)^{n^{2}−1} · 2^{2n^{4}+n^{3}+n^{2}+(2− \frac{ln 3}{ln 2} )n}).

The upper bound of θ_{S(x^{n})} given by the formula is much greater than 4^{n^{4}}, while the actual values of θ_{S(x^{n})} for 2 ≤ n ≤ 6 are less than 4^{n^{2}}. So the upper bound obtained in this paper is most likely far from being tight.

2 Preliminary results

Let S = (s_{1}, s_{2}, …) be a sequence of integers.

Definition 2. The set P (S) is a set of all sums of the form ∑_{k=1}^{∞} ϵ_{k}s_{k} where ϵ_{k} is 0 or 1, all but a finite number of ϵ_{k} are 0 and at least one of ϵ_{k} is 1.

Definition 3. The sequence S is complete if P (S) contains every sufficiently large integer.

Definition 4. If S is complete, the threshold of completeness θ_{S} is the largest integer that is not in P (S).

Definition 5. The set A(S) is a set of all sums of the form ∑_{k=1}^{∞} δ_{k}s_{k} where δ_{k} is −1, 0 or 1 and all but a finite number of δ_{k} are 0.

Definition 6. Let k be a positive integer. The sequence S is a Σ(k)-sequence if s_{1} ≤ k, and

s_{n} ≤ k + ∑_{j=1}^{n−1} s_{j}, n ≥ 2.

For example, if S = (2, 4, 8, 16, …) then S is a Σ(2)-sequence since 2^{n} = 2 + ∑_{j=1}^{n−1} 2^{j} for all n ≥ 2.

Definition 7. Let c and k be positive integers. The sequence S is (c, k)-representable if P (S) contains k consecutive integers c + j, 1 ≤ j ≤ k.

For example, if S = (1, 3, 6, 10, …) is a sequence of triangle numbers then S is (8, 3)- representable since {9, 10, 11} ⊂ P (S).

Definition 8. For a positive integer m, we define ℤ_{m}(S) to be the sequence (α_{1}, α_{2}, …), where 0 ≤ α_{i} < m and s_{i} ≡ α_{i} (mod m) for all i.

The two following lemmas, slightly modified from Lemma 1 and Lemma 2 in Graham’s paper [2], are used to obtain the upper bound.

Lemma 9. For a positive integer k, let S = (s_{1}, s_{2}, …) be a strictly increasing Σ(k)-sequence of positive integers and let T = (t_{1}, t_{2}, …) be (c, k)-representable. Then U = (s_{1}, t_{1}, s_{2}, t_{2}, …) is complete and θ_{U} ≤ c.

Proof. It suffices to prove that every positive integer greater than c belongs to P (U). The proof proceeds by induction. Note that all the integers c + t, 1 ≤ t ≤ k belong to P (T), and all the integers c + s_{1} + t, 1 ≤ t ≤ k belong to P (U). If 1 ≤ t ≤ k then

c + t ∈ P (T) ⊂ P (U),

and if k + 1 ≤ t ≤ k + s_{1}, then 1 ≤ k − s_{1} + 1 ≤ t − s_{1} ≤ k and we have

c + t = c + (t − s_{1}) + s_{1} ∈ P (U).

Therefore all the integers

c + t, 1 ≤ t ≤ k + s_{1}

belong to P (U). Now, let n ≥ 2 and suppose that all the integers

c + t, 1 ≤ t ≤ k + ∑_{j=1}^{n−1} s_{j}

belong to P (U), and that for every such t there is a P (U) representation of c + t such that none of s_{m}, m ≥ n is in the sum. Since all the integers c+t+s_{n}, 1 ≤ t ≤ k +∑_{j=1}^{n−1} s_{j} belong to P (U) and c + 1 + s_{n} ≤ c + 1 + k + ∑_{j=1}^{n−1} s_{j}, all the integers

c + t, 1 ≤ t ≤ k + ∑_{j=1}^{n} s_{j}

belong to P (U). Since S is a strictly increasing sequence of positive integers, this completes the induction step and the proof of lemma.

Lemma 10. Let S = (s_{1}, s_{2}, …) be a strictly increasing sequence of positive integers. If s_{k} ≤ 2s_{k−1} for all k ≥ 2, then S is a Σ(s_{1})-sequence.

Proof. For k ≥ 2, we have

s_{k} ≤ 2s_{k−1} = s_{k−1} + s_{k−1}

≤ s_{k−1} + 2s_{k−2} = s_{k−1} + s_{k−2} + s_{k−2} ≤ s_{k−1} + s_{k−2} + 2s_{k−3} ≤ ⋯

≤ s_{1} + ∑_{j=1}^{k−1} s_{j}.

Therefore, S is a Σ(s_{1})-sequence.

Lemma 9 shows that if a sequence S can be partitioned into one Σ(k)-sequence and one (c, k)-representable sequence then S is complete with θ_{S} ≤ c. What we aim to do is to partition S(x^{n}) into two such sequences for some c and k.

Let f(x) = x^{n} and let S(f) = (f(1), f(2), …). Let a = n!2^{n^{2}} and r = 2^{n^{2}−n}a. Partition the elements of the sequence S(f) into four sets B_{1}, B_{2}, B_{3} and B_{4} defined by

B_{1} = {f(αa + β) : 0 ≤ α ≤ 2^{n^{2}−n} − 1, 1 ≤ β ≤ 2^{n}},
B_{2} = {f(αa + β) : 0 ≤ α ≤ 2^{n^{2}−n} − 1, 2^{n} + 1 ≤ β ≤ a, αa + β < 2^{n^{2}−n}a},
B_{3} = {f(2^{n^{2}−n}a), f(2^{n^{2}−n}a + 2), f(2^{n^{2}−n}a + 4), …},
B_{4} = {f(2^{n^{2}−n}a + 1), f(2^{n^{2}−n}a + 3), f(2^{n^{2}−n}a + 5), …},

so that

B_{1} ∪ B_{2} = {f(1), f(2), …, f(r − 1)}

and

B_{3} ∪ B_{4} = {f(r), f(r + 1), f(r + 2), …}.

Let S, T, U and W be the strictly increasing sequences defined by

S = (s_{1}, s_{2}, …, s_{2^{n^{2}}}), s_{j} ∈ B_{1},
T = (t_{1}, t_{2}, …), t_{j} ∈ B_{3},
U = (u_{1}, u_{2}, …), u_{j} ∈ B_{1} ∪ B_{3},
W = (w_{1}, w_{2}, …), w_{j} ∈ B_{2} ∪ B_{4}.

Then the sequences U and W partition the sequence S(f). First, using Lemma 10, we show that W is a Σ(a)-sequence.

Lemma 11. For a = n!2^{n^{2}} and r = 2^{n^{2}−n}a,

\frac{f(r + 1)}{f(r − 1)} < \frac{f(a + 2^{n} + 1)}{f(a)} < \frac{f(2^{n} + 2)}{f(2^{n} + 1)} ≤ 2.

Proof. Re-write the inequalities as

(1 + \frac{2}{r − 1})^{n} < (1 + \frac{2^{n} + 1}{a})^{n} < (1 + \frac{1}{2^{n} + 1})^{n} ≤ 2.

It is clear that

\frac{r − 1}{2} > \frac{a}{2^{n} + 1} > 2^{n} + 1,

which proves the first two inequalities. The proof of the third inequality

(1 + \frac{1}{2^{n} + 1})^{n} ≤ 2 ⟺ 1 ≤ (2^{\frac{1}{n}} − 1)(2^{n} + 1)

is also straightforward. Corollary 12. The sequence W is a Σ(a)-sequence. Proof. Note that w_{1} = (2^{n} + 1)^{n}. For every k ≥ 2, \frac{w_{k}}{w_{k−1}} satisfies one of the following equalities:

\frac{w_{k}}{w_{k−1}} = \frac{f(α + 1)}{f(α)}, for α ≥ 2^{n} + 1;  (1)
\frac{w_{k}}{w_{k−1}} = \frac{f(βa + 2^{n} + 1)}{f(βa)}, for β ≥ 1;  (2)
\frac{w_{k}}{w_{k−1}} = \frac{f(γ + 2)}{f(γ)}, for γ ≥ r − 1.  (3)

Also, for every α ≥ 2^{n} + 1, β ≥ 1 and γ ≥ r − 1 we have

\frac{f(α + 1)}{f(α)} ≤ \frac{f(2^{n} + 2)}{f(2^{n} + 1)},
\frac{f(βa + 2^{n} + 1)}{f(βa)} ≤ \frac{f(a + 2^{n} + 1)}{f(a)},
\frac{f(γ + 2)}{f(γ)} ≤ \frac{f(r + 1)}{f(r − 1)}.

Thus, by Lemma 11, \frac{w_{k}}{w_{k−1}} ≤ 2 for k ≥ 2, and therefore by Lemma 10, W is a Σ((2^{n} + 1)^{n})- sequence. To complete the proof, it remains to prove that (2^{n} + 1)^{n} < a for all n > 1. The inequality is true for n = 2 and n = 3, and for n > 3 we have

(2^{n} + 1)^{n} < (2^{n} + 2^{n})^{n} = 2^{n}2^{n^{2}} < n!2^{n^{2}} = a.

Therefore, W is a Σ(a)-sequence.

Now, we prove that U is (d, a)-representable for some positive integer d. By Lemma 9, the value d is the upper bound of θ_{S(x^{n})}. Note that the sequences S and T partition U. Lemma 13 shows that P (S) contains a complete residue system modulo a, and Lemma 14 and 15 together show that P (T) contains arbitrarily long arithmetic progression of integers with common difference a. The properties of S and T are used in Lemma 16 to prove that P (U) contains a consecutive integers.

Lemma 13. The set P (S) contains a complete residue system modulo a.

Proof. It suffices to prove that {1, 2, …, a} ⊂ P (ℤ_{a}(S)). Let S_{1}, S_{2}, …, S_{2^{n}} be the sequences defined by

S_{j} = (j^{n}, j^{n}, …, j^{n}), 1 ≤ j ≤ 2^{n}

where |S_{j}| = 2^{n^{2}−n} for all j. Since for each 0 ≤ α ≤ 2^{n^{2}−n} − 1, 1 ≤ β ≤ 2^{n} we have

f(αa + β) ≡ β^{n} (mod a),

and S is the sequence of such f(αa + β) in increasing order, the sequences S_{1}, S_{2}, …, S_{2^{n}} partition the sequence ℤ_{a}(S). Note that

P (S_{1}) = {1, 2, …, 2^{n^{2}−n}}, P (S_{2}) = {2^{n}, 2 · 2^{n}, 3 · 2^{n}, …, 2^{n^{2}−n} · 2^{n}}.

Since for every integer 1 ≤ m ≤ 2^{n^{2}−n}(1 + 2^{n}) there exist 0 ≤ α ≤ 2^{n^{2}−n}, 1 ≤ β ≤ 2^{n} such that

m = α2^{n} + β,

we have

P (S_{1} ∪ S_{2}) = {1, 2, 3, …, 2^{n^{2}−n}(1 + 2^{n})}.

Likewise, for every j ≥ 3, the inequality

j^{n} < 2^{n}(j − 1)^{n} < 2^{n^{2}−n}(1 + 2^{n} + ⋯ + (j − 1)^{n})

holds, and therefore for every 1 ≤ m ≤ 2^{n^{2}−n}(1 + 2^{n} + ⋯ + j^{n}) there exists 0 ≤ α ≤ 2^{n^{2}−n}, 1 ≤ β ≤ 2^{n^{2}−n}(1 + 2^{n} + ⋯ (j − 1)^{n}) such that m = αj^{n} + β. Therefore

P (ℤ_{a}(S)) = P (S_{1} ∪ S_{2} ∪ ⋯ ∪ S_{2^{n}}) = {1, 2, 3, …, 2^{n^{2}−n}(1 + 2^{n} + 3^{n} + ⋯ + 2^{n^{2}})}.

It remains to prove that

a = n!2^{n^{2}} ≤ 2^{n^{2}−n}(1 + 2^{n} + 3^{n} + ⋯ + 2^{n^{2}}).

Since

(\frac{1 + 2^{n} + ⋯ + 2^{n^{2}}}{2^{n}} )^{\frac{1}{n}} ≥ \frac{1 + 2 + ⋯ + 2^{n}}{2^{n}} ,

we have

2^{n^{2}−n}(1 + 2^{n} + ⋯ + 2^{n^{2}}) ≥ (1 + 2 + ⋯ + 2^{n})^{n} = (\frac{2^{n}(2^{n} + 1)}{2})^{n} .

Since 2^{n} + 1 > 2j for every positive integer j ≤ n, we have

\frac{2^{n^{2}−n}(1 + 2^{n} + ⋯ + 2^{n^{2}})}{n!2^{n^{2}}} ≥ (\frac{2^{n}(2^{n} + 1)}{2})^{n} · \frac{1}{n!2^{n^{2}}}

= \frac{(2^{n} + 1)^{n}}{n!2^{n}}

= ∏_{j=1}^{n} \frac{2^{n} + 1}{2j}

> 1.

Therefore, a = n!2^{n^{2}} < 2^{n^{2}−n}(1 + 2^{n} + ⋯ + 2^{n^{2}}) and it completes the proof.

Lemma 14. For every positive integer m,

a ∈ A((f(m), f(m + 2), f(m + 4), …, f(m + \frac{2}{3}(2^{2n} − 1))).

Proof. Define Δ_{k} : ℚ[x] → ℚ[x] by:

Δ_{1}(g(x)) = g(4x + 2) − g(4x),
Δ_{k}(g(x)) = Δ_{1}(Δ_{k−1}(g(x))), 2 ≤ k ≤ n,

so that for 1 ≤ k ≤ n, Δ_{k}(f(x)) is a polynomial of degree n − k. For example,

Δ_{2}(f(x)) = Δ_{1}(f(4x + 2) − f(4x))
= (f(16x + 10) + f(16x)) − (f(16x + 8) + f(16x + 2))

and

Δ_{3}((f(x)) = Δ_{1}(Δ_{2}(f(x)))
= (f(64x + 42) + f(64x + 32) + f(64x + 8) + f(64x + 2))
− (f(64x + 40) + f(64x + 34) + f(64x + 10) + f(64x)).

It is easy to check that there are 2^{k−1} positive terms and 2^{k−1} negative terms in Δ_{k}(f(x)), and all of the terms are distinct. Therefore, for each 1 ≤ k ≤ n, there exist 2^{k} distinct integers α_{k}(1) > α_{k}(2) > ⋯ > α_{k}(2^{k−1}), β_{k}(1) > β_{k}(2) > ⋯ > β_{k}(2^{k−1}) with α_{k}(1) > β_{k}(1) such that

Δ_{k}(f(x)) = ∑_{i=1}^{2^{k−1}} f(2^{2k}x + α_{k}(i)) − ∑_{i=1}^{2^{k−1}} f(2^{2k}x + β_{k}(i)).

Since α_{1}(1) = 2 and α_{k}(1) = 4α_{k−1}(1) + 2 for k ≥ 2, we have

α_{k}(1) = \frac{2}{3}(2^{2k} − 1).

Also, we have {α_{k}(2^{k−1}), β_{k}(2^{k−1})} = {0, 2}. Therefore

Δ_{k}(f(x)) ∈ A((f(2^{2k}x), f(2^{2k}x + 2), …, f(2^{2k}x + \frac{2}{3}(2^{2k} − 1)))).

On the other hand, since

Δ_{1}(f(x)) = f(4x + 2) − f(4x)
= (4x + 2)^{n} − (4x)^{n}
= n2^{2n−1}x^{n−1} + terms of lower degree,

we have

Δ_{n}(f(x)) = n(n − 1)(n − 2) ⋯ 1 · 2^{2n−1}2^{2n−3}2^{2n−5} ⋯ 2^{1}
= n!2^{n^{2}}
= a.

Therefore,

a ∈ A((f(2^{2n}x), f(2^{2n}x + 2), …, f(2^{2n}x + \frac{2}{3}(2^{2n} − 1)))).

Since the Δ_{n}(f(x)) is a polynomial of degree 0, the value a = Δ_{n}(f(x)) is independent of x. Therefore, we can replace 2^{2n}x with an arbitrary positive integer m and we have

a ∈ A((f(m), f(m + 2), f(m + 4), …, f(m + \frac{2}{3}(2^{2n} − 1)))).

Lemma 15. For every positive integer t, there exists a positive integer c such that all the integers

c + ja, 1 ≤ j ≤ t

belong to P (T) and

c < (t − 1)2^{n−1}(r + \frac{2}{3}(t − 1)(2^{2n} − 1) + 2(t − 2))^{n} − a.

Proof. Let α = \frac{2}{3}(2^{2n} − 1), and let T_{1}, T_{2}, …, T_{t−1} be the sequences defined by

T_{1} = (f(r), f(r + 2), f(r + 4), …, f(r + α)),
T_{2} = (f(r + α + 2), f(r + α + 4), …, f(r + 2α + 2)),
T_{3} = (f(r + 2α + 4), f(r + 2α + 6), …, f(r + 3α + 4)), …
T_{t−1} = (f(r + (t − 2)α + 2(t − 2)), …, f(r + (t − 1)α + 2(t − 2))).

By Lemma 14, a ∈ A(T_{j}) for every 1 ≤ j ≤ t − 1, and there exists

A_{j}, B_{j} ∈ P (T_{j})

such that A_{j} − B_{j} = a, both A_{j} and B_{j} consist of 2^{n−1} terms, and all 2^{n} terms of A_{j} and B_{j} are distinct. Let

C_{1} = B_{1} + B_{2} + B_{3} + ⋯ + B_{t−1},
C_{2} = A_{1} + B_{2} + B_{3} + ⋯ + B_{t−1},
C_{3} = A_{1} + A_{2} + B_{3} + ⋯ + B_{t−1}, …
C_{j} = ∑_{i=1}^{j−1} A_{i} + ∑_{i=j}^{t−1} B_{i}, …
C_{t} = A_{1} + A_{2} + A_{3} + ⋯ + A_{t−1}.

Then each C_{j} belongs to P (T), and (C_{1}, C_{2}, …, C_{t}) is an arithmetic progression of t integers with common difference a. Thus, they are exactly the integers c + ja, 1 ≤ j ≤ t with c = C_{1} − a = B_{1} + B_{2} + ⋯ + B_{t−1} − a. Since each B_{j}, 1 ≤ j ≤ t − 1 is a sum of 2^{n−1} terms in T, and all of the terms are less than or equal to

f(r + (t − 1)α + 2(t − 2)) = (r + \frac{2}{3}(t − 1)(2^{2n} − 1) + 2(t − 2))^{n},

we have

c = C_{1} − a < (t − 1)2^{n−1}(r + \frac{2}{3}(t − 1)(2^{2n} − 1) + 2(t − 2))^{n} − a.

Finally, we show that P (U) contains a consecutive integers k_{1} + t_{1}, k_{2} + t_{2}, …, k_{a} + t_{a}, where {k_{1}, k_{2}, …, k_{a}} is a complete residue system of a in P (S) and t_{1}, t_{2}, …, t_{a} are taken from the arithmetic progression in P (T).

Lemma 16. Let b = 2^{n^{3}}a^{n−1}. The sequence U is (d, a)-representable for a positive integer d such that

d < (b − 1)2^{n−1}(r + \frac{2}{3}(b − 1)(2^{2n} − 1) + 2(b − 2))^{n} − 2a + ab.

Proof. By Lemma 15, P (T) contains an arithmetic progression of b integers,

c + ja, 1 ≤ j ≤ b

with

c < (b − 1)2^{n−1}(r + \frac{2}{3}(b − 1)(2^{2n} − 1) + 2(b − 2))^{n} − a.

By Lemma 13, there exist positive integers 1 = k_{1} < k_{2} < ⋯ < k_{a} in P (S) such that {k_{1}, k_{2}, …, k_{a}} is a complete residue system modulo a. For 1 ≤ j ≤ a, let

n_{j} = ⌊\frac{k_{a} − k_{j}}{a} ⌋ + 1.

Then for each 1 ≤ j ≤ a,

\frac{k_{a} − k_{j}}{a} < n_{j} ≤ \frac{k_{a} − k_{j}}{a} + 1 ⟺ k_{a} < n_{j}a + k_{j} ≤ k_{a} + a.

Also, if i ≠ j then n_{i}a + k_{i} ≢ n_{j}a + k_{j} (mod a). Therefore

{c + n_{1}a + k_{1}, c + n_{2}a + k_{2}, …, c + n_{a}a + k_{a}}

is the set of a consecutive integers

{c + k_{a} + 1, c + k_{a} + 2, …, c + k_{a} + a}.

It remains to prove that each c + n_{j}a + k_{j} is in P (U). Let Σ(S) denote the sum of every element of S. Since |S| = 2^{n^{2}}, and

s_{j} ≤ f((2^{n^{2}−n} − 1)a + 2^{n}) = (r − a + 2^{n})^{n} < r^{n} − (a − 2^{n})^{n} < r^{n} − n!

for each s_{j} ∈ S, we have

Σ(S) < 2^{n^{2}}(r^{n} − n!) = 2^{n^{2}}r^{n} − a.

Therefore, for each 1 ≤ j ≤ a we have

1 ≤ n_{j} < \frac{k_{a}}{a} + 1 ≤ \frac{1}{a}Σ(S) + 1 < \frac{1}{a}2^{n^{2}}r^{n} = 2^{n^{3}}a^{n−1} = b

and thus all of c + n_{j}a belong to P (T). Since all of k_{j} belong to P (S), all of c + n_{j}a + k_{j} belong to P (U). Therefore, U is (c + k_{a}, a)-representable. Let

d = c + k_{a}.

Since k_{a} < Σ(S) < 2^{n^{2}}r^{n} − a = ab − a,

d = c + k_{a} < (b − 1)2^{n−1}(r + \frac{2}{3}(b − 1)(2^{2n} − 1) + 2(b − 2))^{n} − 2a + ab.

Now we have everything we need to prove the theorem.

3 Proof of the theorem

Recall that U and W are disjoint subsequences of S(f). By Corollary 12, W is a Σ(a)- sequence and by Lemma 16, U is (d, a)-representable with

d < (b − 1)2^{n−1}(r + \frac{2}{3}(b − 1)(2^{2n} − 1) + 2(b − 2))^{n} − 2a + ab.

Therefore by Lemma 9, S(x^{n}) = S(f) is complete and

θ_{S(x^{n})} ≤ d < (b − 1)2^{n−1}(r + \frac{2}{3}(b − 1)(2^{2n} − 1) + 2(b − 2))^{n} − 2a + ab.

4 Acknowledgments

The author would like to thank Dr. Luke Oeding of Auburn University for his advice. His suggestions were valuable and helped the author to obtain a better upper bound. Also, the author would like to thank Dr. Peter Johnson of Auburn University and the anonymous referees for their helpful comments.

References

[1] C. Fuller and R. H. Nichols, Generalized Anti-Waring numbers, J. Integer Seq. 18 (2015), Article 15.10.5.

[2] R. L. Graham, Complete sequences of polynomial values, Duke Math. J. 31 (1964), 275–285.

[3] S. Lin, Computer experiments on sequences which form integral bases, in J. Leech, ed., Computational Problems in Abstract Algebra, Pergamon Press, 1970, pp. 365–370.

[4] C. Patterson, The Derivation of a High Speed Sieve Device, Ph.D. thesis, University of Calgary, 1992.

[5] K. F. Roth and G. Szekeres, Some asymptotic formulae in the theory of partitions, Q. J. Math. 5 (1954), 241–259.

[6] R. Sprague, Über Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen, Math. Z. 51 (1948), 466–468.

[7] R. Sprague, Über Zerlegungen in ungleiche Quadratzahlen, Math. Z. 51 (1948), 289–290.

2010 Mathematics Subject Classification: Primary 11P05; Secondary 05A17. Keywords: complete sequence, threshold of completeness, sum of powers.

(Concerned with sequence \underline{A001661}.)

Received October 29 2016; revised versions received November 2 2016; July 1 2017. Published in Journal of Integer Sequences, July 2 2017.

Return to Journal of Integer Sequences home page.