Generalized Anti-Waring Numbers

Chris Fuller and Robert H. Nichols, Jr. Labry School of Science, Technology, and Business Cumberland University 1 Cumberland Square Lebanon, TN 37087 USA

                    cfuller@cumberland.edu
                    rnichols@cumberland.edu

Abstract

The anti-Waring problem considers the smallest positive integer such that it and every subsequent integer can be expressed as the sum of the k^{th} powers of r or more distinct natural numbers. We give a generalization that allows elements from any nondecreasing sequence, rather than only the natural numbers. This generalization is an extension of the anti-Waring problem, as well as the idea of complete sequences. We present new anti-Waring and generalized anti-Waring numbers, as well as a result to verify computationally when a generalized anti-Waring number has been found.

1 Introduction

For positive integers k and r, the anti-Waring number N(k, r) is defined to be the smallest positive integer such that N(k, r) and every subsequent positive integer can be expressed as the sum of the k^{th} powers of r or more distinct positive integers. Several authors [3, 5, 7, 11] recently reported results on anti-Waring numbers.

Early results considered only r = 1. As early as 1948, Sprague found that N(2, 1) = 129 [15] and proved that N(k, 1) exists for all k ≥ 2 [16]. In 1964, Graham [6] reported that N(3, 1) = 12759 (Graham [6] references another Graham paper “On the Threshold of completeness for certain sequences of polynomial values” said to appear circa 1964). Dressler and Parker [4] also computed N(3, 1) in 1974. Lin [10] used Graham’s method to find that N(4, 1) = 5134241 with a computer in 1970. In 1992, Patterson [12, pp. 18–23] found that N(5, 1) = 67898772. In this paper, we independently verify each of these numbers and show that N(6, 1) = 11146309948.

More recently, Looper and Saritzky [11] proved that N(k, r) exists for all positive integers k and r. Deering and Jamieson [3] found specific values of N(2, r) for 1 ≤ r ≤ 10 and N(3, r) for 1 ≤ r ≤ 5. Shortly afterwards, Fuller et al. [5] computed values of N(2, r) for 1 ≤ r ≤ 50 and N(3, r) for 1 ≤ r ≤ 30. We also verify these numbers and present N(k, r) for more values of k and r. One can verify a suspected value of N(k, r) using different sets of conditions [3, 5].

In an effort to generalize the anti-Waring results we consider a nondecreasing sequence of positive integers A = (a_{i})_{i∈ℕ}. Here and throughout we use ℕ = {1, 2, 3, … }. For positive integers k, n, and r we define the generalized anti-Waring number N(k, n, r, A) to be the smallest positive integer, if it exists, such that it and every subsequent positive integer can be expressed as the sum of the k^{th} powers of the a_{i} with i ≥ n ranging over r or more distinct values. If the sequence A has all distinct elements, we may use set notation for the last argument of the generalized anti-Waring number. The generalized anti-Waring number N(k, n, r, A) does not exist for all sequences A (see Theorems 1 and 2 in Section 2). Looper and Saritzky [11] proved that both the anti-Waring number N(k, r) and the generalized anti-Waring number N(k, n, r, ℕ) exist for all positive integers k, n, and r.

Early results of these generalized anti-Waring numbers when restricting r to 1 used different terminology. A nondecreasing sequence S of positive integers is complete if all sufficiently large positive integers can be written as a sum of distinct elements of S. If S is a complete sequence, the threshold of completeness, θ(S), is the largest positive integer that is not expressible as a sum of distinct elements of S. Therefore, the threshold of completeness, θ(S), is one less than the generalized anti-Waring number N(1, 1, 1, S). Also, if S = (s_{i})_{i∈ℕ} is a nondecreasing sequence of positive integers such that the sequence (s_{i}^{k})_{i≥n} is complete, then the generalized anti-Waring number N(k, n, 1, S) exists and N(k, n, 1, S) − 1 = θ ((s_{i}^{k})_{i≥n}). Brown [1] defined a sequence to be complete only when the threshold of completeness is zero; we use the more general definition.

In the literature on complete sequences, some authors only report that a sequence is complete and hence the generalized anti-Waring number exists; some authors actually find the threshold of completeness. In 1952, Lekkerkerker [9] reported an account of the Zeckendorf representation (circa 1939 [17]), i.e., that every natural number is either a Fibonacci number or can be expressed as the sum of nonconsecutive Fibonacci numbers. Hence the generalized anti-Waring number for the Fibonacci sequence F is N(1, 1, 1, F) = 1. In 1975, Kløve [8] found thresholds of completeness for sequences of the form (⌊i^{α}⌋)_{i∈ℕ}, where ⌊x⌋ is the floor function, for 1 ≤ α ≤ 4.18 in increments of 0.02. In 1978, Porubský [13] proved that N(k, 1, 1, ℙ) exists for all positive integers k and the sequence of primes ℙ. Burr and Erdős [2] considered perturbations of complete sequences that resulted in noncomplete sequences and vice versa.

Generalized anti-Waring numbers extend the concept of anti-Waring numbers to sequences other than ℕ. The generalization also extends the concept of complete sequences to consider sums of r or more terms. We will present conditions needed to verify values of N(k, n, r, A) computationally, sequences for which no N(k, n, r, A) exists, and new values of N(k, n, r, A) for various sequences.

2 Verifying N(k, n, r, A), when it exists

For given positive integers k, n, r, and any nondecreasing sequence of positive integers A = (a_{i})_{i∈ℕ}, we define a positive integer to be (k, n, r, A)-good if it can be written as a sum of the k^{th} powers of r or more distinct elements of the sequence (a_{i})_{i≥n}. We define a positive integer that is not (k, n, r, A)-good to be (k, n, r, A)-bad. Hence the generalized anti-Waring number N(k, n, r, A) is the smallest positive integer such that it and every subsequent integer is (k, n, r, A)-good. Equivalently the threshold of completeness N(k, n, r, A)−1 is the largest integer that is (k, n, r, A)-bad.

The generalized anti-Waring number N(k, n, r, A) does not exist for all sequences A. For example, the sum of any elements of the sequence (2, 4, 6, 8, …) of positive even integers will never be odd. This is an instance of a more general phenomenon.

Theorem 1. Let A = (a_{i})_{i∈ℕ} be a nondecreasing sequence of positive integers. If all a_{i} for i ≥ n have a common divisor d > 1, then for any positive integers k and r, the generalized anti-Waring number N(k, n, r, A) does not exist.

Proof. Every sum of positive powers of the a_{i}, i ≥ n, is divisible by d. Since d > 1, arbitrarily large integers not divisible by d exist. Thus, arbitrarily large integers not representable in any way as a sum of powers of some of the a_{n}, a_{n+1}, … also exist.

If instead the greatest common divisor is one, then the generalized anti-Waring number may or may not exist. We will consider examples of both cases.

As an additional example, the sequence of factorials has no generalized anti-Waring number.

Theorem 2. Let A = (i!)_{i∈ℕ}, and let k, n, and r are any positive integers. Then the generalized anti-Waring number N(k, n, r, A) does not exist.

Proof. First notice that for each a_{i} ∈ A,

a_{i}^{k} mod 6 ≡ \begin{cases}1, & if i = 1; \\ 2^{k} mod 6, & if i = 2; \\ 0, & if i > 2. \end{cases}

Consider any (k, n, r, A)-good number m. Distinct integers i_{1}, i_{2}, …, i_{t} exist such that

m = a_{i_{1}}^{k} + a_{i_{2}}^{k} + ⋯ + a_{i_{t}}^{k}

where t ≥ r and i_{α} ≥ n for each α ∈ {1, 2, …, t}. Thus the sum m must be 0, 1, 2^{k}, or 1 + 2^{k} modulo 6. Since we can have at most four consecutive (k, n, r, A)-good integers, no largest (k, n, r, A)-bad integer exists.

On the other hand, in some cases the generalized anti-Waring number N(k, n, r, A) is known to exist, but its value has not been found. As mentioned above, both the anti-Waring number N(k, r) and the generalized anti-Waring number N(k, n, r, ℕ) exist for all k, n, and r [11]. A general formula for either of these is not known, but we present several values in the next section. We rewrite the following result related to complete sequences by Brown [1, Theorem 1] in terms of generalized anti-Waring numbers.

Theorem 3. Let k and n be positive integers, and let A = (a_{i})_{i∈ℕ} be a nondecreasing sequence of positive integers. The generalized anti-Waring number N(k, n, 1, A) both exists and equals one if and only if (i) a_{n} = 1 and (ii) for all integers p ≥ n, a_{p+1}^{k} ≤ 1 + ∑_{i=n}^{p} a_{i}^{k}.

This result only considers r = 1. Also since Brown [1] defined complete sequences requiring the threshold of completeness to be zero, he requires a_{n} = 1. Theorem 3 proves that all positive integers are representable as a sum of different elements of sequences such as the natural numbers, the Fibonacci numbers, and the powers of two (including 2^{0}). We must consider different conditions for the more general definition of complete sequences with any threshold of completeness.

The next result from Graham [6, Theorem 4] establishes completeness conditions for sequences generated by polynomials.

Theorem 4. Let f(x) be a polynomial with real coefficients expressed in the form

f(x) = α_{0} + α_{1}\binom{x}{1} + ⋯ + α_{n}\binom{x}{n}, α_{n} ≠ 0.

The sequence S(f) = (f(1), f(2), ⋯) is complete if and only if

1. α_{k} = p_{k}/q_{k} for some integers p_{k} and q_{k} with gcd(p_{k}, q_{k}) = 1 and q_{k} ≠ 0 for 0 ≤ k ≤ n,

2. α_{n} > 0, and

3. gcd(p_{0}, p_{1}, …, p_{n}) = 1.

Again, in terms of generalized anti-Waring numbers Theorem 4 only considers the case of r = 1 and can only be used to establish that a given generalized anti-Waring number exists. As a remark to this theorem, Graham notes that a sequence (f(1), f(2), f(3), …) is complete if and only if (f(n), f(n+1), f(n+2), …) is complete for any n. The next theorem shows that nothing like this can be expected in general.

Theorem 5. Let k, n, and r be positive integers, and let A be a sequence of nondecreasing positive integers. If the generalized anti-Waring number N(k, n, r, A) exists, then so does N(k, j, r, A) for j ∈ {1, 2, …, n − 1} and N(k, j, r, A) ≤ N(k, n, r, A). Furthermore, the converse is false.

Proof. The implication is clear. If all positive integers greater than or equal to N(k, n, r, A) can be written as a sum k^{th} powers of r or more distinct elements of (a_{i})_{i≥n}, then, with the same elements, each positive integer can be written as a sum k^{th} powers of r or more distinct elements of (a_{i})_{i≥j} for j ∈ {1, 2, …, n − 1}. Therefore, we have N(k, j, r, A) ≤ N(k, n, r, A) for j ∈ {1, 2, …, n − 1}.

To see that the converse is false, consider the sequence A = (2^{i−1})_{i∈ℕ}. From the binary representation of the positive integers, the generalized anti-Waring number N(1, 1, 1, A) clearly exists and equals one. However, the generalized anti-Waring number N(1, 2, 1, A) does not exist because no odd integer can be expressed as a sum of elements from (2^{i−1})_{i≥2}.

In general, whether N(k, n, r, A) exists or not cannot easily be determined. However, we can validate a suspect value of N(k, n, r, A) if enough consecutive integers are (k, n, r, A)- good and certain other conditions are met. Theorem 6 is a generalization of a recent result for anti-Waring numbers [5, Theorem 2.2].

Theorem 6. Let k, n, r, b, and N̂ be positive integers, and let A = (a_{i})_{i∈ℕ} with 0 < a_{i} ≤ a_{i+1} and a_{i} ∈ ℕ for all i. If the consecutive integers {N̂, …, b^{k}} are all (k, n, r, A)-good, the number N̂ −1 is (k, n, r, A)-bad, and there exists a positive integer x such that the conditions

1. N̂ ≤ b^{k} + 1 − (b − x)^{k},

2. a_{n} ≤ b − x,

3. 0 < ( ∑_{i=n}^{n+r−2} a_{i}^{k}) + 2(m − x)^{k} − (m + 1)^{k} for all m ≥ b, and

4. (m + 1)^{k} − (m − x)^{k} ≤ m^{k} for all m ≥ b

hold, then the generalized anti-Waring number N(k, n, r, A) exists and equals N̂. Note: The sum in condition 3 is zero if r = 1.

Proof. We want to prove that if ℓ ≤ m^{k} and ℓ is (k, n, r, A)-bad, then ℓ ≤ N̂ −1 by induction on m with m ≥ b.

This is clearly true for m = b as we know the consecutive integers {N̂, …, b^{k}} are all (k, n, r, A)-good.

Now suppose ℓ ≤ (m+1)^{k} and ℓ is (k, n, r, A)-bad. If ℓ ≤ m^{k}, then by induction ℓ ≤ N̂ −1. Next, consider ℓ such that

m^{k} + 1 ≤ ℓ ≤ (m + 1)^{k}.  (1)

Notice b^{k} − (b − x)^{k} ≤ m^{k} − (m − x)^{k} for m ≥ b. Using this along with (1) and condition 1, we have

N̂ ≤ ℓ − (m − x)^{k}.  (2)

To see that ℓ − (m − x)^{k} is (k, n, r, A)-bad, suppose it is (k, n, r, A)-good. Then

ℓ − (m − x)^{k} = a_{i_{1}}^{k} + a_{i_{2}}^{k} + a_{i_{3}}^{k} + ⋯ + a_{i_{t}}^{k}

where t ≥ r, i_{α} ≠ i_{β} for all α ≠ β, and i_{α} ≥ n for all α ∈ {1, 2, …, t}. Since ℓ is (k, n, r, A)- bad and

ℓ = a_{i_{1}}^{k} + a_{i_{2}}^{k} + a_{i_{3}}^{k} + ⋯ + a_{i_{t}}^{k} + (m − x)^{k},

either m − x < a_{n}, which contradicts condition 2, or a_{i_{α}} = m − x for some α ∈ {1, 2, …, t}. Therefore,

ℓ ≥ a_{n}^{k} + a_{n+1}^{k} + a_{n+2}^{k} + ⋯ + a_{n+r−2}^{k} + 2(m − x)^{k}.

If r = 1, this is just ℓ ≥ 2(m − x)^{k}. Combining with (1), we get

( ∑_{i=n}^{n+r−2} a_{i}^{k}) + 2(m − x)^{k} − (m + 1)^{k} ≤ 0.

This contradicts condition 3 and means that ℓ − (m − x)^{k} must be (k, n, r, A)-bad. Now from (1) and condition 4,

ℓ − (m − x)^{k} ≤ (m + 1)^{k} − (m − x)^{k} ≤ m^{k}.

By induction we then have ℓ − (m − x)^{k} ≤ N̂ − 1. This contradicts (2). Hence there are no ℓ that are (k, n, r, A)-bad and satisfy (1).

Most of the threshold of completeness results in the literature of complete sequences rely on work by Richert [14], where different sufficient conditions imply that a sequence is complete when restricting r = 1. Our algorithms for computing generalized anti-Waring numbers were designed to stop when x and b are found satisfying Theorem 6.

3 Values of N(k, n, r, A)

As a result of Theorems 1 and 2, we know that N(k, n, r, A) does not exist for all values of k, n, and r and all sequences A. Ideally, if the generalized anti-Waring number N(k, n, r, A) exists, a formula for it can be derived. We have found such a formula for some cases. For other cases, we have computationally found and verified N(k, n, r, A) with Theorem 6.

Johnson and Laughlin [7, Theorem 1] proved a first result

N(1, 1, r, ℕ) = ∑_{i=1}^{r} i = \frac{r}{2}(r + 1)  (3)

for the case of k = n = 1. A similar argument is valid for general values of n.

Theorem 7. For positive integers n and r, the generalized anti-Waring number is given by

N(1, n, r, ℕ) = ∑_{i=n}^{n+r−1} i = \frac{r}{2}(r + 1) + r(n − 1).

Proof. Clearly, the sum ∑_{i=n}^{n+r−1} i is the smallest integer expressible as the sum of r or more distinct integers greater than or equal to n. For any positive integer x greater than the sum ∑_{i=n}^{n+r−1} i, we have

x − ∑_{i=n}^{n+r−2} i > n + r − 1.

Finally, we have that

x = ∑_{i=n}^{n+r−2} i + (x − ∑_{i=n}^{n+r−2} i)

so the integer x is the sum of r distinct integers greater than or equal to n.

Theorem 8. For positive integers n, r, and s and integers t such that |t| < s and gcd(s, t) = 1, the generalized anti-Waring number is given by

N(1, n, r, (si + t)_{i∈ℕ}) = 1 − s + ∑_{i=n}^{n+r+s−2}(si + t).  (4)

Note: For the case of s = 1 and t = 0, this reduces to N(1, n, r, ℕ) and agrees with Theorem 7.

Proof. The sequence B = (si + t)_{i≥n} consists of all positive integers equivalent to t mod s that are greater than or equal to sn+t. For any positive integer p, the sum of any p elements of B is equivalent to pt mod s. In order to express all sufficiently large integers as the sum of r or more distinct elements of B, we need sums with the number of summands covering all equivalence classes of ℤ_{s}. The list r, r + 1, r + 2, …, r + s − 1 contains representatives of each equivalence class in ℤ_{s}. Since the integers s and t are relatively prime, the same is true for the list rt, (r + 1)t, (r + 2)t, …, (r + s − 1)t. Hence, all sums containing between r and r + s − 1 distinct elements of B will account for all sufficiently large positive integers, as we shall see. We must determine the smallest integer not expressible by one of these sums.

For p ∈ {r, r + 1, r + 2, …, r + s − 1}, let m_{p} be the sum of the first p elements of B, i.e.,

m_{p} = ∑_{i=n}^{n+p−1}(si + t) = s ( ∑_{i=n}^{n+p−1} i) + pt.

As noted before, we have m_{p} ≡ pt (mod s). We also know that m_{p} is the smallest integer equivalent to pt mod s expressible as the sum of r or more distinct elements of B. Hence the integer m_{p} − s is (1, n, r, (si + t)_{i∈ℕ})-bad. If a positive integer x ≥ m_{p} is also equivalent to pt mod s, then we have x = m_{p} + ℓs for some positive ℓ ∈ ℤ or, equivalently,

x = ℓs + ∑_{i=n}^{n+p−1}(si + t) = (s(ℓ + n + p − 1) + t) + ∑_{i=n}^{n+p−2}(si + t).

Thus, all integers equivalent to pt mod s greater than m_{p} are expressible as the sum of r or more distinct elements of B. Since we have m_{p} < m_{p+1} for all p, the last (1, n, r, (si + t)_{i∈ℕ})- bad integer is m_{r+s−1} − s. Therefore, the generalized anti-Waring number is N(1, n, r, (si + t)_{i∈ℕ}) = m_{r+s−1} − s + 1 which is (4).

k  N(k, 1) x b bad count
1  1 1 4  0
2  129 4 18  31
3  12759 5 32  2788
4  5134241 8 59  889576
5  67898772 4 45  13912682
6 11146309948 5 55 2037573096

Table 1: Values of N(k, 1, 1, ℕ)

k N(k, 1, 1, ℙ) x  b bad count
1  7 6 14  3
2  17164 54 187  2438
3  1866001 31 157  483370

Table 2: Values of N(k, 1, 1, ℙ)

For most cases, a formula for N(k, n, r, A) is not known, but we can compute particular values. In the Tables 1 to 6 we list values of N(k, n, r, A) along with the corresponding x and b that satisfy the conditions for Theorem 6 hence confirming the given generalized anti-Waring number. Tables 1, 3, and 4 use A = ℕ. In Table 1 we consider n = r = 1, i.e., the first positive integer such that it and every subsequent integer can be written as the sum k^{th} powers of distinct integers. For each k we also include a bad count, i.e., the number of positive integers that cannot be written as a sum of k^{th} powers. Table 2 lists the corresponding values over the sequence of primes ℙ. Table 3 lists generalized anti-Waring numbers for fixed n = 1 and varying k and r. We stopped the table at r = 36 but were able to compute some N(k, 1, r, ℕ) for much larger r. For example, we found that N(2, 1, 1000, ℕ) = 333951595 with x = 12898 and b = 19395. Table 4 lists generalized anti-Waring numbers for varying k, n, and r. Tables 3 and 4 omit generalized anti-Waring numbers when k = 1 because a formula for N(1, n, r, ℕ) for all n and r in ℕ exists by Theorem 7. Tables 5 and 6 list generalized anti-Waring numbers for fixed n = 1 and r = 1 over various sequences of the form (si + t)_{i∈ℕ}.

\begin{matrix}r & N(2, r) & x & b & N(3, r) & x & b & N(4, r) & x & b & N(5, r) & x & b \\ 1 & 129 & 4 & 18 & 12759 & 5 & 32 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 2 & 129 & 4 & 18 & 12759 & 5 & 32 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 3 & 129 & 4 & 18 & 12759 & 5 & 32 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 4 & 129 & 4 & 18 & 12759 & 5 & 32 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 5 & 198 & 6 & 22 & 12759 & 5 & 32 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 6 & 238 & 6 & 23 & 15279 & 6 & 33 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 7 & 331 & 8 & 26 & 15279 & 6 & 33 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 8 & 383 & 9 & 27 & 15279 & 6 & 33 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 9 & 528 & 10 & 32 & 16224 & 6 & 33 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 10 & 648 & 12 & 33 & 18149 & 6 & 35 & 5134241 & 8 & 59 & 67898772 & 4 & 45 \\ 11 & 889 & 14 & 39 & 22398 & 7 & 37 & 5191473 & 8 & 59 & 67898772 & 4 & 45 \\ 12 & 989 & 15 & 41 & 24855 & 7 & 38 & 5626194 & 8 & 60 & 67898772 & 4 & 45 \\ 13 & 1178 & 17 & 44 & 28887 & 8 & 39 & 6018930 & 8 & 62 & 71780055 & 4 & 46 \\ 14 & 1398 & 19 & 47 & 36951 & 9 & 42 & 6408466 & 9 & 62 & 74729904 & 4 & 46 \\ 15 & 1723 & 21 & 52 & 39660 & 9 & 43 & 6664722 & 9 & 62 & 81846431 & 5 & 45 \\ 16 & 1991 & 24 & 54 & 49083 & 10 & 46 & 6938867 & 9 & 63 & 92894512 & 5 & 47 \\ 17 & 2312 & 26 & 58 & 56076 & 11 & 47 & 8077523 & 9 & 66 & 95723448 & 5 & 47 \\ 18 & 2673 & 28 & 62 & 66534 & 12 & 50 & 8592323 & 9 & 67 & 112031630 & 5 & 49 \\ 19 & 3048 & 31 & 65 & 75912 & 12 & 52 & 9269124 & 10 & 67 & 124811198 & 5 & 50 \\ 20 & 3493 & 34 & 69 & 87567 & 13 & 54 & 10418260 & 10 & 69 & 142118181 & 5 & 52 \\ 21 & 4094 & 36 & 75 & 101093 & 14 & 56 & 10589380 & 10 & 70 & 163637305 & 6 & 52 \\ 22 & 4614 & 39 & 79 & 122064 & 15 & 60 & 12852837 & 11 & 72 & 189572962 & 6 & 54 \\ 23 & 5139 & 42 & 83 & 138696 & 16 & 62 & 13199973 & 11 & 73 & 210715205 & 6 & 55 \\ 24 & 5719 & 44 & 87 & 156498 & 17 & 64 & 15148358 & 11 & 76 & 247073537 & 6 & 57 \\ 25 & 6380 & 48 & 91 & 179520 & 18 & 67 & 16526214 & 12 & 76 & 285744830 & 7 & 57 \\ 26 & 7124 & 51 & 96 & 201921 & 19 & 69 & 17803895 & 12 & 78 & 319712379 & 7 & 59 \\ 27 & 7953 & 54 & 101 & 227400 & 20 & 72 & 20499591 & 13 & 81 & 374237223 & 7 & 61 \\ 28 & 8677 & 57 & 105 & 256254 & 22 & 73 & 21202776 & 13 & 81 & 430026890 & 7 & 63 \\ 29 & 9538 & 61 & 109 & 289869 & 23 & 76 & 24306872 & 13 & 84 & 491665093 & 8 & 64 \\ 30 & 10394 & 63 & 114 & 325590 & 24 & 79 & 25670088 & 14 & 84 & 558015873 & 8 & 65 \\ 31 & 11559 & 67 & 120 & 359358 & 25 & 82 & 29819129 & 14 & 88 & 640101337 & 8 & 68 \\ 32 & 12603 & 71 & 125 & 401496 & 26 & 85 & 31126025 & 15 & 88 & 737104155 & 9 & 68 \\ 33 & 13744 & 74 & 130 & 448503 & 27 & 88 & 35677050 & 15 & 92 & 839165455 & 9 & 71 \\ 34 & 14864 & 78 & 135 & 496257 & 29 & 90 & 38187306 & 16 & 92 & 950792455 & 9 & 73 \\ 35 & 16253 & 81 & 141 & 554217 & 30 & 93 & 43256507 & 16 & 96 & 1070200765 & 10 & 73 \\ 36 & 17529 & 85 & 146 & 611736 & 30 & 97 & 46180043 & 17 & 97 & 1215652918 & 10 & 76 \end{matrix}

Table 3: Values of N(k, 1, r, ℕ) and the corresponding x and b that satisfy Theorem 6. Values of N(1, n, r, ℕ) are given by Theorem 7.

\begin{matrix}r & N(2, 2, r) & x & b & N(3, 2, r) & x & b & N(4, 2, r) & x & b & N(5, 2, r) & x & b \\ 1 & 193 & 5 & 22 & 19310 & 6 & 36 & 6659841 & 9 & 62 & 84038312 & 5 & 46 \\ 2 & 193 & 5 & 22 & 19310 & 6 & 36 & 6659841 & 9 & 62 & 84038312 & 5 & 46 \\ 3 & 193 & 5 & 22 & 19310 & 6 & 36 & 6659841 & 9 & 62 & 84038312 & 5 & 46 \\ 4 & 213 & 6 & 22 & 19310 & 6 & 36 & 6659841 & 9 & 62 & 84038312 & 5 & 46 \\ 5 & 318 & 7 & 27 & 19310 & 6 & 36 & 6659841 & 9 & 62 & 84038312 & 5 & 46 \\ 6 & 334 & 8 & 26 & 19310 & 6 & 36 & 6692881 & 9 & 62 & 84038312 & 5 & 46 \\ 7 & 398 & 9 & 27 & 19310 & 6 & 36 & 6692881 & 9 & 62 & 84038312 & 5 & 46 \\ 8 & 527 & 10 & 32 & 19310 & 6 & 36 & 6692881 & 9 & 62 & 84038312 & 5 & 46 \\ 9 & 647 & 12 & 33 & 20885 & 7 & 36 & 6778897 & 9 & 62 & 84038312 & 5 & 46 \\ 10 & 888 & 14 & 39 & 24098 & 7 & 38 & 6778897 & 9 & 62 & 84038312 & 5 & 46 \\ r & N(2, 3, r) & x & b & N(3, 3, r) & x & b & N(4, 3, r) & x & b & N(5, 3, r) & x & b \\ 1 & 224 & 6 & 23 & 23775 & 7 & 38 & 7076321 & 9 & 63 & 110100822 & 5 & 49 \\ 2 & 224 & 6 & 23 & 23775 & 7 & 38 & 7076321 & 9 & 63 & 110100822 & 5 & 49 \\ 3 & 233 & 6 & 23 & 23775 & 7 & 38 & 7076321 & 9 & 63 & 110100822 & 5 & 49 \\ 4 & 314 & 7 & 26 & 23775 & 7 & 38 & 7076321 & 9 & 63 & 110100822 & 5 & 49 \\ 5 & 330 & 8 & 26 & 23775 & 7 & 38 & 7076321 & 9 & 63 & 110100822 & 5 & 49 \\ 6 & 418 & 9 & 28 & 23775 & 7 & 38 & 7076321 & 9 & 63 & 110100822 & 5 & 49 \\ 7 & 523 & 10 & 32 & 23775 & 7 & 38 & 7103505 & 9 & 63 & 110100822 & 5 & 49 \\ 8 & 643 & 12 & 33 & 24756 & 7 & 38 & 7103505 & 9 & 63 & 110100822 & 5 & 49 \\ 9 & 884 & 14 & 39 & 28221 & 7 & 41 & 7103505 & 9 & 63 & 110100822 & 5 & 49 \\ 10 & 984 & 15 & 41 & 28950 & 8 & 40 & 7103505 & 9 & 63 & 110100822 & 5 & 49 \\ r & N(2, 4, r) & x & b & N(3, 4, r) & x & b & N(4, 4, r) & x & b & N(5, 4, r) & x & b \\ 1 & 385 & 8 & 30 & 26862 & 7 & 40 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 2 & 385 & 8 & 30 & 26862 & 7 & 40 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 3 & 385 & 8 & 29 & 26862 & 7 & 40 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 4 & 385 & 8 & 28 & 26862 & 7 & 40 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 5 & 453 & 9 & 30 & 26862 & 7 & 40 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 6 & 558 & 10 & 33 & 26862 & 7 & 40 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 7 & 634 & 12 & 34 & 27528 & 7 & 40 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 8 & 875 & 14 & 39 & 28194 & 7 & 41 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 9 & 999 & 15 & 41 & 30111 & 8 & 40 & 8912545 & 9 & 68 & 129436797 & 5 & 51 \\ 10 & 1164 & 17 & 43 & 33234 & 8 & 42 & 8912545 & 9 & 68 & 130964972 & 5 & 51 \\ r & N(2, 5, r) & x & b & N(3, 5, r) & x & b & N(4, 5, r) & x & b & N(5, 5, r) & x & b \\ 1 & 493 & 9 & 34 & 34844 & 8 & 43 & 9292705 & 9 & 69 & 167956256 & 5 & 54 \\ 2 & 493 & 9 & 33 & 34844 & 8 & 43 & 9292705 & 9 & 69 & 167956256 & 5 & 54 \\ 3 & 493 & 9 & 32 & 34844 & 8 & 43 & 9292705 & 9 & 69 & 167956256 & 5 & 54 \\ 4 & 494 & 9 & 32 & 34844 & 8 & 43 & 9292705 & 9 & 69 & 167956256 & 5 & 54 \\ 5 & 542 & 10 & 33 & 34844 & 8 & 43 & 9292705 & 9 & 69 & 167956256 & 5 & 54 \\ 6 & 670 & 12 & 35 & 34844 & 8 & 43 & 9377041 & 9 & 69 & 167956256 & 5 & 54 \\ 7 & 883 & 14 & 39 & 35060 & 8 & 43 & 9377041 & 9 & 69 & 167956256 & 5 & 54 \\ 8 & 983 & 15 & 41 & 35060 & 8 & 43 & 9377041 & 10 & 68 & 167956256 & 5 & 54 \\ 9 & 1188 & 17 & 44 & 38048 & 8 & 44 & 9377041 & 10 & 68 & 167956256 & 6 & 53 \\ 10 & 1412 & 19 & 47 & 43880 & 9 & 45 & 9377041 & 10 & 68 & 167956256 & 5 & 54 \\ r & N(2, 6, r) & x & b & N(3, 6, r) & x & b & N(4, 6, r) & x & b & N(5, 6, r) & x & b \\ 1 & 637 & 10 & 37 & 40416 & 8 & 45 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 2 & 637 & 10 & 37 & 40416 & 8 & 45 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 3 & 637 & 10 & 37 & 40416 & 8 & 45 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 4 & 637 & 11 & 35 & 40416 & 8 & 45 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 5 & 834 & 13 & 40 & 40416 & 8 & 45 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 6 & 870 & 13 & 40 & 40416 & 8 & 45 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 7 & 958 & 15 & 40 & 40416 & 8 & 45 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 8 & 1163 & 17 & 43 & 41450 & 9 & 44 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 9 & 1387 & 19 & 46 & 48066 & 9 & 47 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \\ 10 & 1668 & 21 & 51 & 49893 & 10 & 46 & 11728881 & 10 & 72 & 191116579 & 6 & 54 \end{matrix}

Table 4: Values of N(k, n, r, ℕ) for n > 1 and the corresponding x and b that satisfy Theorem 6. Values of N(1, n, r, ℕ) are given by Theorem 7.

\begin{matrix}(s, t) & k = 2 & x & b & k = 3 & x & b \\ (2, −1) & 1923 & 18 & 64 & 212595 & 15 & 77 \\ (2, +1) & 2355 & 20 & 71 & 266459 & 16 & 83 \\ (3, −2) & 3250 & 23 & 83 & 942316 & 25 & 126 \\ (3, −1) & 3014 & 22 & 80 & 957226 & 25 & 126 \\ (3, +1) & 4093 & 26 & 92 & 1103569 & 26 & 132 \\ (3, +2) & 4414 & 27 & 96 & 1181758 & 27 & 135 \\ (4, −3) & 10588 & 42 & 148 & 2576040 & 35 & 174 \\ (4, −1) & 11268 & 43 & 153 & 3026615 & 37 & 184 \\ (4, +1) & 13708 & 48 & 167 & 3152462 & 37 & 187 \\ (4, +3) & 14948 & 50 & 175 & 3534459 & 39 & 193 \\ (5, −4) & 14900 & 50 & 174 & 6146241 & 47 & 232 \\ (5, −3) & 14121 & 49 & 170 & 6373428 & 47 & 236 \\ (5, −2) & 16810 & 53 & 186 & 6672804 & 48 & 239 \\ (5, −1) & 16379 & 52 & 184 & 7077048 & 49 & 244 \\ (5, +1) & 17242 & 54 & 187 & 7165274 & 49 & 245 \\ (5, +2) & 19090 & 57 & 198 & 7526193 & 50 & 249 \\ (5, +3) & 19690 & 58 & 201 & 7821959 & 51 & 252 \\ (5, +4) & 19799 & 58 & 201 & 8326652 & 52 & 257 \\ (6, −5) & 255964 & 209 & 717 & 32025571 & 82 & 402 \\ (6, −1) & 261868 & 211 & 727 & 35431051 & 85 & 416 \\ (6, +1) & 270796 & 215 & 738 & 38008681 & 87 & 426 \\ (6, +5) & 282028 & 219 & 754 & 40622251 & 88 & 436 \\ (7, −6) & 44329 & 87 & 300 & 24233667 & 74 & 367 \\ (7, −5) & 45769 & 88 & 305 & 23668124 & 74 & 363 \\ (7, −4) & 49737 & 92 & 317 & 25473560 & 76 & 373 \\ (7, −3) & 49009 & 91 & 315 & 26139255 & 76 & 376 \\ (7, −2) & 48989 & 91 & 315 & 27035708 & 77 & 380 \\ (7, −1) & 49537 & 92 & 317 & 27348027 & 77 & 382 \\ (7, +1) & 51889 & 94 & 324 & 28963994 & 79 & 389 \\ (7, +2) & 55884 & 97 & 337 & 28297320 & 78 & 387 \\ (7, +3) & 54217 & 96 & 331 & 30183369 & 80 & 394 \\ (7, +4) & 60377 & 101 & 350 & 28992218 & 79 & 389 \\ (7, +5) & 58292 & 99 & 344 & 31374203 & 81 & 400 \\ (7, +6) & 63453 & 104 & 358 & 31015095 & 81 & 397 \\ (8, −7) & 183828 & 177 & 608 & 43603746 & 91 & 445 \\ (8, −5) & 186684 & 178 & 614 & 44323025 & 91 & 448 \\ (8, −3) & 192748 & 181 & 623 & 44594177 & 91 & 449 \\ (8, −1) & 199124 & 184 & 634 & 49916598 & 95 & 466 \\ (8, +1) & 208164 & 188 & 648 & 51794250 & 96 & 472 \\ (8, +3) & 216940 & 192 & 661 & 53940372 & 97 & 479 \\ (8, +5) & 223884 & 195 & 672 & 53774817 & 97 & 478 \\ (8, +7) & 227204 & 197 & 676 & 55157135 & 98 & 482 \\ (9, −8) & 104873 & 134 & 460 & 316621582 & 176 & 861 \\ (9, −7) & 114857 & 140 & 481 & 317215246 & 176 & 862 \\ (9, −5) & 114653 & 140 & 481 & 327375655 & 178 & 871 \\ (9, −4) & 118829 & 142 & 490 & 329700964 & 179 & 872 \\ (9, −2) & 120113 & 143 & 492 & 338139583 & 180 & 880 \\ (9, −1) & 130217 & 149 & 512 & 339498184 & 180 & 882 \\ (9, +1) & 134681 & 151 & 522 & 352115215 & 183 & 891 \\ (9, +2) & 129149 & 148 & 511 & 358747834 & 184 & 897 \\ (9, +4) & 137873 & 153 & 528 & 371854375 & 186 & 908 \\ (9, +5) & 141329 & 155 & 534 & 365220868 & 185 & 902 \\ (9, +7) & 142825 & 156 & 536 & 383482411 & 188 & 917 \\ (9, +8) & 149990 & 160 & 549 & 376489804 & 187 & 911 \end{matrix}

Table 5: Values of N(k, 1, 1, (si+t)_{i∈ℕ}) and the corresponding x and b that satisfy Theorem 6. The generalized anti-Waring number N(k, n, r, (si + t)_{i∈ℕ}) does not exist if gcd(s, t) > 1 by Theorem 1, and values of N(1, n, r, (si + t)_{i∈ℕ}) are given by Theorem 8.

\begin{matrix}(s, t) & k = 2 & x & b & k = 3 & x & b \\ (10, −1) & 2866844 & 701 & 2396 & 167900541 & 142 & 698 \\ (10, +1) & 2770803 & 689 & 2356 & 164930981 & 142 & 693 \\ (11, −1) & 251377 & 207 & 711 & 188148921 & 148 & 724 \\ (11, +1) & 260001 & 211 & 723 & 200560127 & 151 & 740 \\ (12, −1) & 1186948 & 451 & 1543 & 1871937463 & 320 & 1555 \\ (12, +1) & 1207948 & 455 & 1556 & 1897625923 & 321 & 1562 \\ (13, −1) & 484333 & 288 & 986 & 427144568 & 195 & 951 \\ (13, +1) & 498269 & 292 & 1000 & 434996727 & 196 & 957 \\ (14, −1) & 14209388 & 1561 & 5333 & 718660158 & 232 & 1130 \\ (14, +1) & 14254244 & 1563 & 5342 & 750996509 & 235 & 1148 \\ (15, −1) & 878885 & 388 & 1328 & 7192487965 & 501 & 2434 \\ (15, +1) & 890945 & 390 & 1338 & 7247153841 & 502 & 2440 \\ (16, −1) & 4345668 & 863 & 2950 & 1162662009 & 272 & 1328 \\ (16, +1) & 4411364 & 869 & 2973 & 1188105593 & 274 & 1337 \\ (17, −1) & 1468737 & 501 & 1717 & 1528625985 & 298 & 1454 \\ (17, +1) & 1487777 & 505 & 1727 & 1574453445 & 302 & 1468 \\ (18, −1) & 47752420 & 2862 & 9774 & 23390399911 & 742 & 3606 \\ (18, +1) & 47891524 & 2866 & 9789 & 23431535880 & 743 & 3607 \\ (19, −1) & 2296953 & 627 & 2146 & 2670453204 & 360 & 1750 \\ (19, +1) & 2330393 & 632 & 2161 & 2654207231 & 359 & 1746 \\ (20, −1) & 12065164 & 1438 & 4915 & 3392160594 & 390 & 1895 \\ (20, +1) & 12241324 & 1449 & 4950 & 3426870488 & 391 & 1901 \end{matrix}

Table 6: Additional values of N(k, 1, 1, (si + t)_{i∈ℕ}) and the corresponding x and b that satisfy Theorem 6. The generalized anti-Waring number N(k, n, r, (si + t)_{i∈ℕ}) does not exist if gcd(s, t) > 1 by Theorem 1, and values of N(1, n, r, (si + t)_{i∈ℕ}) are given by Theorem 8.

4 Future work

With enough time and computing power, we can compute any values of N(k, n, r, A) that exist. However, we have only found a formula for cases with k = 1.

Some simple inequalities involving N(k, n, r, A) are clear. For example, for i ≤ j we have the inequalities N(k, i, r, A) ≤ N(k, j, r, A) and N(k, n, i, A) ≤ N(k, n, j, A) when each exists. We are unable to prove the inequality N(k, n, r, A) ≤ N(k + 1, n, r, A) even though all data seem to emphatically support it.

We have found and considered several algorithms for generating good numbers. However, none reveal a formula for the largest bad number, i.e., threshold of completeness for k > 1.

5 Acknowledgments

We thank the editor and the anonymous referee for their time and consideration. The referee’s report was thorough and included valuable suggestions.

References

[1] J. L. Brown, Jr., Note on complete sequences of integers, Amer. Math. Monthly 68 (1961), 557–560.

[2] S. Burr and P. Erdős, Completeness properties of perturbed sequences, J. Number Theory 13 (1981), 446–455.

[3] J. Deering and W. Jamieson, On anti-Waring numbers, to appear in J. Combin. Math. Combin. Comput.

[4] R. Dressler and T. Parker, 12,758, Math. Comp. 28 (1974), 313–314.

[5] C. Fuller, D. Prier, and K. Vasconi, New results on an anti-Waring problem, Involve 7 (2014), 239–244.

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

[7] P. Johnson and M. Laughlin, An anti-Waring conjecture and problem, Int. J. Math. Comput. Sci. 6 (2011), 21–26.

[8] T. Kløve, Sums of distinct elements from a fixed set, Math. Comp. 29 (1975), 1144–1149.

[9] C. G. Lekkerkerker, Voorstelling van natuurlikjke getallen door een som van getallen van Fibonaaci, Simon Stevin 29 (1952), 190–195.

[10] 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.

[11] N. Looper and N. Saritzky, An anti-Waring theorem and proof, to appear in J. Combin. Math. Combin. Comput.

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

[13] Š. Porubský, Sums of prime powers, Monatsh. Math 86 (1979), 301–303.

[14] H. E. Richert, Über Zerlegungen in paarweise verschiedene Zahlen, Nordisk Mat. Tidskr. 31 (1949), 120–122.

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

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

[17] E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41 (1972), 179–182.

2010 Mathematics Subject Classification: Primary 11P05; Secondary 05A17. Keywords: complete sequence, sum of powers, anti-Waring number.

(Concerned with sequence \underline{A001661}.)

Received June 18 2015; revised versions received September 13 2015; September 21 2015. Published in Journal of Integer Sequences, September 24 2015.

Return to Journal of Integer Sequences home page.