Integers That Are Sums of Uniform Powers of All Their Prime Factors:

The Sequence \underline{A068916}

Spencer P. Hurd Professor Emeritus of Mathematics The Citadel Charleston, SC USA and P.O. Box 197 Meigs, GA 31765 USA

                 spencerhurd@yahoo.com

Judson S. McCranie 105 Mackqueen Dr. Brunswick, GA 31525 USA

                  jud@judmccranie.com

This paper is dedicated to Richard K. Guy on his 102^{nd} birthday, 30 September 2018.

Abstract

For integers s ≥ 1 and n ≥ 2, we define the function T_{s} as follows: T_{s}(n) = T_{s}(p^{a}q^{b} ⋯ r^{c}) = ap^{s} + bq^{s} + ⋯ + cr^{s}. Thus T_{s}(n) is the sum of the s^{th} powers of the prime factors of n, counted according to multiplicity of the prime factors. The set T^{∗}(s) is defined as {n : T_{s}(n) = n}, and we let a(s) be the smallest element in T^{∗}(s). We consider several natural questions. Is the set T^{∗}(s) empty, finite or infinite for some particular values of s? Suppose y is a prime power, say y = p^{m}. Is it possible that y = T_{s}(y) for some s? What is the smallest element a(s) in the set T^{∗}(s)? The answer for the last question is documented, but only for certain small values of s in the title sequence, a(s), for s = 1, 2, …, namely sequence \underline{A068916} in the Online Encyclopedia of Integer Sequences. It begins 2, 16, 1096744, 3125, . . .. Some sets T^{∗}(s) are known to have one or two elements, and T^{∗}(1) is infinite. Some sets T^{∗}(s) have prime powers. In fact, infinitely often T^{∗}(s) contains p^{y} for some power y and prime p. For example T^{∗}(24) contains 3^{27}, which may be the value of a(24). The set T^{∗}(3) contains six known elements, and none of these are prime powers. We prove T^{∗}(3) does not contain any prime powers at all. Curiously, every known member of T^{∗}(s) for any value of s, except s = 3, is in fact a prime power. We also briefly discuss algorithms and functions related to T_{s}(n).

1 Introduction

The decomposition of a number into prime factors is sometimes critical for understanding the action of a function whose range and domain are contained in the set of natural numbers. Insight may be obtained from computer searches related to the function. Here these ideas play a role in the function of this note whose very definition also depends on this prime decomposition.

Definition 1. Let n > 1 be any positive integer whose prime factorization into distinct prime factors is given by n = p^{a}q^{b} ⋯ r^{c}. We define, for each positive integer s, the function T_{s} on the set {n : n ∈ ℤ, n > 1} as follows:

T_{s}(n) = T_{s}(p^{a}q^{b} ⋯ r^{c}) = ap^{s} + bq^{s} + ⋯ + cr^{s}.

Further, we say that T_{s}(n) is the sum of the s^{th} powers of the prime factors of n, counted according to multiplicity of the prime factor. The set T^{∗}(s) is defined as {n : T_{s}(n) = n}, and we denote the smallest element in T^{∗}(s) by a(s).

Example 2. T_{s}(200) = T_{s}(2^{3}5^{2}) = 2^{s} + 2^{s} + 2^{s} + 5^{s} + 5^{s} = 3(2^{s}) + 2(5^{s}) and for s = 4, T_{4}(200) = 3(2^{4})+2(5^{4}) = 1298. Since 2^{3} ∥ 200, 3·2^{4} occurs in T_{4}(200). Since T_{4}(200) ≠ 200, 200 ∉ T^{∗}(4). From Table 1, a(4) = 3125, the smallest element in T^{∗}(4).

In this note we consider several natural questions. Is the set T^{∗}(s) empty, finite or infinite for some particular values of s? Suppose y is a prime power, say y = p^{m}. Is it possible that y = T_{s}(y) for some s? What is the smallest element a(s) in the set T^{∗}(s)?

The answer for the last question is documented, but only for certain small s, and this brings us to the title sequence, which is a(s), for s = 1, 2, . . .. It is sequence \underline{A068916} in the Online Encyclopedia of Integer Sequences [5]. It begins 2, 16, 1096744, 3125, . . .. We list what is known of these values in Table 1. We also list the smallest known values as upper bounds for a(s) when a(s) is not known. We write “unknown” in Table 1 to mean not only

s a(s)  s  a(s)
1 2  12  65536 = 2^{16}
2 16 = 2^{4}  13–15 unknown
3 1096744 = 2^{3} · 11^{3} · 103 16  ≤ 17^{17}
4 3125 = 5^{5}  17  unknown
5 256 = 2^{2^{3}}  18  ≤ 19^{19}
6 823543 = 7^{7}  19–21 unknown
7 19683 = 3^{3^{2}}  22  ≤ 23^{23}
8, 9 unknown  23  ≤ 298023223876953125 = 5^{25}
10 285311670611 = 11^{11}  24  7625597484987 = 3^{27}
11 unknown
Table 1: The sequence \underline{A068916}, a(s) is the smallest element in T^{∗}(s)

is a(s) not known but also that no elements in T^{∗}(s) have even been discovered! For any set T we use card(T) to denote its cardinality, and we are especially interested in card(T^{∗}(s)) for any value of s.

For s = 16, we may calculate T_{16}(17^{17}) = 17(17^{16}) = 17^{17}. Thus, 17^{17} ∈ T^{∗}(16) and thus a(16) ≤ 17^{17}. Currently this number 17^{17} only provides an upper bound for a(16) because its minimality has not yet been confirmed by a computer search. Indeed, there is no method yet known other than a computer verification for determining the correctness of the entries in the sequence \underline{A068916}, except for very small values of s.

Two facts about Table 1 are immediately clear. First, many of the entries are powers of a prime. So, a(s) = p^{y} quite often for some power y and prime p.

Secondly, not all of the elements of T^{∗}(s) are prime powers. Note for s = 3 that a(3) is the product of seven primes, three of which are distinct. Nevertheless, it is further striking that, except for s = 3, all the entries in Table 1 are powers of a prime. It is still more striking that T^{∗}(3) has six known elements, none of which are prime powers, and these six are the only non-prime powers known to be in T^{∗}(s) for any s. (See Section 3 and Table 4.)

Theorem 3. Suppose the number y is a prime power, say y = p^{m}. Then y is in set T^{∗}(s) if and only if m = p^{k} for some k, and s = p^{k} − k.

Proof. By the hypothesis, y = p^{m}. First suppose y is in set T^{∗}(s). This means T_{s}(y) = y = p^{m}. But by the definition of T_{s}, T_{s}(p^{m}) = mp^{s}, from which mp^{s} = p^{m}. By division, m = p^{k} for k = m − s. Thus, s = m − k = p^{k} − k.

Conversely, by substitution, T_{s}(y) = T_{s}(p^{m}) = T_{(m−k)}(p^{m}) = mp^{m−k} = p^{k}p^{m−k} = p^{m} = y. So, y is in the set T^{∗}(s).

Corollary 4. Let s = p − 1 for some prime p. Then T_{s}(p^{p}) = p^{p}.

Proof. Take k = 1 in Theorem 3.

Example 5. Observe 256 is in set T^{∗}(5) since T_{5}(256) = T_{5}(2^{8}) = 8 · 2^{5} = 2^{8} = 256. This illustrates Theorem 3 as s = 5 = 2^{3} − 3, and 256 = 2^{2^{3}}.

1.1 Historical remarks

The sequence \underline{A068916} was first recorded by D. Hickerson in March 2002 in the Online Encyclopedia of Integer Sequences [5]. It was based on the related sequence \underline{A067688}, which was recorded a month earlier by J. L. Pe, on February 4 2002. The earlier sequence lists only composite m for which there is some s such that T_{s}(m) = m. Focusing on \underline{A068916} allows us to consider the sets T^{∗}(s) more deeply, as well as the numbers m that satisfy T_{s}(m) = m for some s.

The pattern for prime power elements in T^{∗}(s), that p^{p^{k}} was in T^{∗}(s) when s = p^{k} − k was noted in 2003 (JSM). The other half of Theorem 3, that all prime powers in T^{∗}(s) for any s must have this form, seems to be new here.

Later contributors D. Hickerson (March 07 2003) and J. S. McCranie (March 16 2003) confirmed earlier entries and extended the list. Donovan Johnson (May 17 2010) noted, in our notation, that T^{∗}(24) contained 3^{27} and that T^{∗}(12) contained 13^{13}. M. Marcus (\underline{A068916}) and C. R. Greathouse (\underline{A067688}) added programs for testing numbers in January 2016. McCranie (January 18 2016) put upper bounds on a(23) and a(24) in Table 1 and reported (on January 30 2016) that a(24) = 3^{27}. In between he reported that a(10) = 11^{11}. The new sequence \underline{A268036} contains material in our Table 4.

Table 2 contains a new listing of small s such that T^{∗}(s) is known to contain (at least) two elements. We conjecture that there are infinitely many s such that T^{∗}(s) contains two prime powers (see Section 5).

Recently we learned of papers [3] and [4], in which J.-M. De Koninck and F. Luca consider two different functions similar to our T_{s}. In these, an integer n is represented as a sum of equal powers s of some subset (not necessarily all) of its prime factors, and the prime factors are not counted by the multiplicity of the prime factor in the factorization. They list the second through sixth items in our Table 4 (in Section 3) in their papers. For example they also give 378 = 2 · 3^{3} · 7 = 2^{3} + 3^{3} + 7^{3}, as 378 can be written as the sum of the cubes of its prime factors, with multiplicity ignored, and 870 = 2 · 3 · 5 · 29 = 2^{2} + 5^{2} + 29^{2} equal to squares of a proper subset of its prime factors.

2 The sets T^{∗}(s) for various s

It turns out that for many values of s, card(T^{∗}(s)) ≥ 2, but there are no known values of s such that card(T^{∗}(s)) is exactly 2. The smallest values of s are shown in Table 2.

T_{1}(2) = 2 and T_{1}(4) = T_{1}(2^{2}) = 2(2^{1}) = 4. So, T^{∗}(1) contains {2, 4} and these are the prime powers guaranteed by Theorem 3. What other elements are in T^{∗}(1)? Is T^{∗}(1) a finite set?

Theorem 6. We have T^{∗}(1) = {4, 2, 3, 5, 7, …} = {4, all primes}.

Proof. For any prime p, we have T_{1}(p^{1}) = 1(p^{1}) = p. So T^{∗}(1) contains {4, all primes}. But for any composite greater than 4, the sum of its prime factors (counted by multiplicity) is less than the product.

s  p^{k} − k  q − 1  s  p^{k} − k  q − 1
2  2^{2} − 2  3 − 1  65520 2^{16} − 16 65521 − 1
12 2^{4} − 4 13 − 1  161046 11^{5} − 5 161047 − 1
58 2^{6} − 6 59 − 1  262126 2^{18} − 18 262127 − 1
238 3^{5} − 5 239 − 1 300760 67^{3} − 3 300761 − 1
3120 5^{5} − 5 3121 − 1 1295026 109^{3} − 3 1295027 − 1
6856 19^{3} − 3 6857 − 1 3442948 151^{3} − 3 3442949 − 1
29788 31^{3} − 3 29789 − 1 9393928 211^{3} − 3 9393929 − 1
50650 37^{3} − 3 50651 − 1
Table 2: Small s such that T^{∗}(s) has two prime powers, see \underline{A268594}

Are there other values of s for which T^{∗}(s) is infinite? None are known, but likewise there is no reason to suppose any is finite. Or is there? We conjecture T^{∗}(2) is a finite set.

We observe that T_{2}(16) = T_{2}(2^{4}) = 4·2^{2} = 4·4 = 16. Also, T_{2}(27) = T_{2}(3^{3}) = 3·3^{2} = 27. This shows the set T^{∗}(2) contains {16, 27}, both prime powers, and 2 = 2^{2} − 2 = 3^{1} − 1. Examination of cases shows a(2) = 16. Are other prime powers in T^{∗}(2) besides 2^{4} and 3^{3}? No, because it would require, by Theorem 3, that 2 = p^{k} − k, for some prime p and integer k. If k = 1, 2 then p = 3, 2 respectively. Suppose k > 2, p > 3, and 2 = p^{k} − k. Then we claim p^{k} = 2 + k is contradictory. To see this, observe that 2 + k < 5^{k} for any k > 2. But 3 < p implies 5^{k} ≤ p^{k} as p is an odd prime. Combining inequalities, 2 + k < 5^{k} ≤ p^{k} = 2 + k, the desired contradiction. We extend this argument to other cases in Theorem 7.

Theorem 7. Suppose p is a prime, s > 1, and s + 1 < p. Then no power of p is contained in T^{∗}(s).

Proof. We observe the result is true for s = 2, so we may suppose 3 ≤ s and 5 ≤ p. Suppose on the contrary that T_{s}(p^{m}) = p^{m} for some m. Then, by Theorem 3, m = p^{k} for some k, and s = p^{k} − k. So, p^{k} − k = s < p − 1. Thus, p^{k} < p + k − 1. Now, for k = 1, the last inequality reduces to p < p, a contradiction. If 1 < k, then define f(p) = p^{k} −(p+k −1). Note that the derivative of f, f′(p) = kp^{k−1} − 1, is positive and thus f(p) is a strictly increasing function since k > 1. Thus, p^{k} > p + k − 1, a contradiction.

An obvious consequence of Theorem 7 is that, for any s, the subset of T^{∗}(s) that contains only prime powers is finite, bounded above by the case s = p − 1.

Example 8. Using Example 5, with s = 2^{6} − 6, we get the following: T_{58}(2^{64}) = T_{58}(2^{2^{6}}) = (2^{6})T_{58}(2) = (2^{6})2^{58} = 2^{64}. Note T_{58}(59^{59}) = 59^{59}. We may calculate: log_{2}(59^{59}) = 59 · log_{2}(59) > 59 · log_{2}(32) = 59 · 5 = 295 > 64 = log_{2}(2^{64}). This shows a(58) may be 2^{64}, which is smaller than 59^{59}. We generalize this example in Theorem 11.

We have no examples such that p^{k} − k = q^{j} − j with neither j = 1 nor k = 1, and we conjecture that none exist. If p = 2 and j > 1, our computer search shows that there are no 1 2 4 5 6 7 10 12 16 18 22 23 24 27 28 30 36 40 42 46 47 52 58 60 66 70 72 77 78 82 88 96 100 102 106 108 112 119 121 122 126 130 136 138 148 150 156 162 166 167 172 178 180 190 192 196 198 210 222 226 228 232 238 240 248 250 256 262 268 270 276 280

Table 3: Numbers s of the form s = p^{k} − k for some k ≥ 0, sequence \underline{A318606}

such q for 2^{k} − k = q^{j} − j up to 1.84 × 10^{19}. C. R. Greathouse has extended this to 10^{40}. See \underline{A268594} for a partial list of s = p^{k} − k = q^{j} − j, as in Table 2.

The Catalan conjecture (now Mihăilescu’s theorem) is that p^{k} and q^{j} never differ by 1 when min (k, j) ≥ 2, except for 2^{3} = 8 and 3^{2} = 9. We also mention the related Pillai conjecture (unproved) that, for any fixed positive integer r, there are only finitely many differences of prime powers that equal r. More generally, it is equivalent to the following claim: for fixed positive integers A, B, and C, the equation Ax^{n} −By^{m} = C has only finitely many solutions (x, y, m, n) with (m, n) ≠ (2, 2).

Assume that every natural number C will occur as a difference of prime powers only finitely often. We are looking for special elements in such a finite set — those whose prime powers have a difference C and also such that the powers themselves have C as their difference. Such dual differences must be especially scarce.

Conjecture 9. Suppose p, q are distinct primes. Then we conjecture p^{k} − q^{j} ≠ k − j if j, k > 1. Further, there are infinitely many triples (p, k, q) such that p^{k} − k = q − 1.

See Table 2 for examples for which this equality holds. See Table 3 for examples of s such that T^{∗}(s) is not empty.

For every example in Table 2, the second item is s = q − 1. Is this always the case? We conjecture the following.

Conjecture 10. Whenever exactly two elements are contained in T^{∗}(s), both are prime powers and one of them is q^{q} for s = q − 1 and the other is p^{m} for m = p^{k} and s = p^{k} − k.

Theorem 11. Suppose p, q are primes with p < q and that s, k, i are natural numbers with i ≥ 1 such that p^{k} − k = q^{i} − i = s. Then asymptotically, a(s) ≤ p^{p^{k}} < q^{q^{i}}.

Proof. To begin with, a(s) ≤ p^{p^{k}} is a result of Theorem 3. Now by hypothesis we have p < q or equivalently \frac{q}{p} < 1. Let J_{1} denote the inequality p^{p^{k}} < q^{q^{i}} and let J_{2} denote the inequality (\frac{p}{q})^{s} < 1 − \frac{k−i}{p^{k}}. It is easy to show by elementary algebra, the target inequality J_{1} is true if and only if J_{2} is true asymptotically. (It is convenient for this algebra to note that p^{k} = s + k and q^{i} = s + i.) We will argue that J_{2} is true. First, since s = p^{k} − k, s increases exponentially with k and thus (\frac{p}{q})^{s} decreases exponentially towards 0. But \frac{k−i}{p^{k}} converges to 0 as well. It follows that the left-hand side of J_{2} converges to 0 and the right-hand side converges to 1 as s increases. This shows that J_{2} is true asymptotically.

n in set T^{∗}(3)  Prime decomposition
1096744 = a(3)  2^{3} · 11^{3} · 103
2836295  5 · 7 · 11 · 53 · 139
4473671462  2 · 13 · 179 · 593 · 1621
23040925705  5 · 7 · 167 · 1453 · 2713
13579716377989 19 · 157 · 173 · 1103 · 23857
119429556097859 7 · 53 · 937 · 6983 · 49199
Table 4: Known elements in T^{∗}(3), sequence \underline{A268036}

We note that for all known cases for which T^{∗}(s) has two prime powers (see Table 2), p^{k} and q^{i} with p < q, it is always the case that i = 1. For an illustration of Theorem 11, consider p = 37 in Table 2. We have k = 3, q = 50651 and i = 1, and s = q^{1} − 1 = 50650. Then J_{2} gives (\frac{2}{50651})^{50650} < 1 − \frac{2}{37^{3}} . The left side is too small to calculate without a few pages of decimal zeroes. The right side is 0.99996 . . ..

When there are two (or possibly more) prime power elements in T^{∗}(s) for some s, the lesser prime always corresponds to the smaller element and gives the lower upper bound for a(s) according to Theorem 11.

Theorem 3 gives an upper bound for a search criterion for a(s) provided there is a prime p such that s = p^{k} − k for some k. We suspect that most searches looked for these special s. We listed in Table 3 numbers of the form s = p^{k} − k for some p, k, such that s < 1000. Of course the corresponding T -values are relatively huge, as T_{s}(y) = y = p^{p^{k}}.

3 The sets T^{∗}(3) and related questions

Table 4 lists the numbers presently known to be in T^{∗}(3), a case that is strikingly different from all the other known cases.

For example, let y = 1096744 = 2^{3} · 11^{3} · 103. Then T_{3}(y) = 3 · 2^{3} + 3 · 11^{3} + 1 · 103^{3} = 1096744 = y. Exhaustive computer calculation shows 1096744 = a(3), the smallest element of T^{∗}(3).

We classify the examples in Table 4 as “irregular”. They do not occur with the prime power form suggested in Theorem 3. We do not know if the set T^{∗}(s) will often contain a lengthy product of (distinct) primes or other elements with exactly five distinct prime factors. Will any of the sets T^{∗}(s) contain numbers with arbitrarily many distinct prime factors? This is unknown.

An entry in Table 4 mentions that n = 2836295 = 5^{3} + 7^{3} + 11^{3} + 53^{3} + 139^{3} is the smallest number that is a product of five distinct prime factors and is also the sum of the cubes of these distinct prime factors. The third entry in Table 4 is due to McCranie (2003), the fourth to D. Johnson (2010), and the fifth and sixth to McCranie (February 07 2016). But see the comment at the end of Section 1.

Index s  m
1  2  4 = 2^{2}
2  2  16 = 2^{4}
3  2  27 = 3^{3}
4  5  256 = 2^{8}
5  4  3125 = 5^{5}
6  7  19683 = 3^{9}
7 12  65536 = 2^{16}
8  6  823543 = 7^{7}
9  3  1096744 = 2^{3} · 11^{3} · 103
10 3  2836295 = 5 · 7 · 11 · 53 · 139
11 27  4294967296 = 2^{32}
12 3  4473671462 = 2 · 13 · 179 · 593 · 1621
13 3  23040925705 = 5 · 7 · 167 · 1453 · 2713
14 10  2825311670611 = 11^{11}
15 24  7625597484987 = 3^{27}
16 3 13579716377989 = 19 · 157 · 8173 · 1103 · 23857
17 3 119429556097859 = 7 · 53 · 937 · 6983 · 49199
18 12  302875106592253 = 13^{13}
19? 23  298023223876953125 = 5^{25}
20 ?  unknown
Table 5: Sequence \underline{A067688}, ordered by size of m

3.1 Remarks on computation

Running our program (by JSM) on 16 CPUs for about 47 hours determined that 13579716377989 is the fifth solution for T^{∗}(3) and that there is no other smaller element in T^{∗}(4). The determination of the sixth element took 27 days.

In Table 5 we have factored each value of m so that we are able to see the interplay in the related sequences and the applications of Theorem 3. The sixth element 119429556097859 from our Table 4 is the seventeenth in the sequence \underline{A067688} (see the end of Section 1). Forty-eight days of computing by JSM revealed on April 22 2016 that 13^{13} was confirmed to be the eighteenth value (in size) of m so that T_{s}(13^{13}) = 13^{13} for s = 12, and it became the eighteenth element in \underline{A067688}. At present we can say the nineteenth element is conjectured to be 5^{25}.

Theorem 12. If s ≥ 1, p, q, …, r are 2u distinct primes, and n = pq ⋯ r, then n ∉ T^{∗}(s).

Proof. First suppose the 2u primes are odd. Observe T_{s}(n) = p^{s} + q^{s} + ⋯ + r^{s} is even, being the sum of an even number of odd integers. However, n is odd. Now suppose p = 2, and n = 2q ⋯ r. Here n is even, but T_{s}(n) sums to 2^{s} plus an odd number of odd integers and is thus odd. In both cases, n ∉ T_{s}(n).

Theorem 13. Suppose p, q, and r are three distinct odd primes. (a) If n = pqr, then n ≠ T_{3}(n). (b) If n = 2^{k}pqr, then n ≠ T_{3}(n).

Proof. First, for part (a) suppose p ≡ q ≡ r ≡ 1 (mod 4). Then n ≡ 1 (mod 4) but T_{3}(n) ≡ 1^{3} + 1^{3} + 1^{3} ≡ 3 (mod 4). Next suppose n ≡ (−1)(1)(1) ≡ −1 (mod 4). However, here T_{3}(n) ≡ (−1)^{3} + 1^{3} + 1^{3} ≡ 1 (mod 4). Next, if n ≡ (−1)(−1)(1) ≡ 1 (mod 4), then T_{3}(n) ≡ (−1)^{3} + (−1)^{3} + 1^{3} ≡ −1 (mod 4). Finally, if n ≡ (−1)(−1)(−1) ≡ −1 ≡ 3 (mod 4), then T_{3}(n) ≡ (−1)^{3} +(−1)^{3} +(−1)^{3} ≡ −3 ≡ 1 (mod 4). Now for part (b), observe, n ≠ T_{3}(n) because T_{3}(n) = k · 2^{3} + p^{3} + r^{3} + q^{3} which is odd; but n is even.

Theorem 13 also applies when there are 4k + 3 for k > 0. This, along with Theorem 12 means that for members of T^{∗}(3) that are the product of distinct odd primes, the number of primes must be 1 more than a multiple of 4.

According to Theorem 12 (for s = 3) and Theorem 13, we should begin a search for n in T^{∗}(3) by considering n = pqrst, a product of five distinct odd primes or n = p^{a}q^{b}r^{c} with each of p, q, r, a, b, c odd (and at least one exponent at least 3), or n = 2^{k}q^{b}r^{c} with b, c odd. Happily this is exactly where the elements of T^{∗}(3) have been found.

Are there any prime powers in T^{∗}(3)? No, by Theorem 3, since 3 is not equal to p^{k} − k for any p, k. This is easily checked. By Theorem 7, we need only check primes not greater than 4.

One wonders if there are many other numbers in T^{∗}(3), i.e., is T^{∗}(3) finite or very sparse? It would be curious if a sieve argument, or any argument, could show T^{∗}(x) is finite for some x, since T^{∗}(1) is infinite. In fact, the totality of examples for all known s suggest that integers in T^{∗}(3) abound, compared to T^{∗}(s) for s = 2 or s > 3.

4 Eliminating possibilities for T^{∗}(2)

For some prime decomposition forms of the variable n we are able to show T_{2}(n) is not equal to n. The general purpose here is two-fold. Ideally, since T^{∗}(2) contains at least {16, 27} one would like to prove that card(T^{∗}(2)) = 2, or to be able to use these results to simplify or direct computer searches.

In what follows we use p, q, r, s to represent odd primes in increasing order. We observe that if n = pq ⋯ s for a series of k distinct odd primes, then n ≡ 1, 3 (mod 4), T_{2}(n) ≡ k (mod 4).

We further note that, if p > 3 is prime, then (a) p ≡ 1, 2 (mod 3), and (b) p is -1 or +1 (mod 6), and so p^{2} ≡ 1 (mod 6). Similarly, since any odd integer u is 4v + 1 or 4v − 1 for some v, it follows that u^{2} ≡ 1 (mod 8).

Lemma 14. Suppose n = p^{a}q^{b} for two distinct odd primes p, q.

(a) If a + b ≡ 0 (mod 2), then n ≠ T_{2}(n).

(b) If a = 2 and b = 1 then n ≠ T_{2}(n).

Proof. For part (a), if a+b is even, then T_{2}(n) is even but n is odd. For part (b), if n = T_{2}(n), then n = p^{2}q = 2p^{2} + q^{2} = T_{2}(n), from which p^{2}(q − 2) = q^{2}. This last equation implies q divides either p or (q − 2), an impossibility in either case.

Lemma 15. Suppose n = p^{2a}q^{2b+1} where p, q are distinct odd primes. Then

(a) if q > 2a or if p > 2b + 1, then n ≠ T_{2}(n).

(b) if q^{2} ∤ a or if p^{2} ∤ 2b + 1, then n ≠ T_{2}(n).

Proof. Part (a): Suppose q > 2a. If, on the contrary, n = p^{2a}q^{2b+1} = T_{2}(n) = 2ap^{2} + (2b + 1)q^{2}, then rearranging terms, p^{2a}q^{2b+1} −2ap^{2} = (2b+1)q^{2}. This implies p^{2}[p^{2a−2}q^{2b+1} −2a] = (2b + 1)q^{2}. The last equation implies, since q cannot divide p^{2}, that q must divide the term in brackets. This is only possible if q divides 2a. But q is larger than 2a. The other case is similar, and in either case, n ≠ T_{2}(n).

Part (b): The equation p^{2}(p^{2a−2}q^{2b+1} − 2a) = (2b + 1)q^{2} implies both that q^{2} divides the term (p^{2a−2}q^{2b+1} − 2a), and also that p^{2} divides 2b + 1. But this contradicts the hypothesis, and we conclude n ≠ T_{2}(n).

Lemma 16. If n = 2^{k}pq, then n is not equal to T_{2}(n).

Proof. Supposing otherwise, first let k = 1. Now q = p + a for some integer a. Then n = 2p(p + a) and T_{2}(n) = 4 + p^{2} + (p + a)^{2}. Thus, equating n and T_{2}(n), we get 2p^{2} + 2pa = 4 + p^{2} + p^{2} + 2pa + a^{2}. This simplifies to 0 = 4 + a^{2}, a contradiction. If k > 1, then n ≡ 0 (mod 4), but T_{2}(n) ≡ 4k + p^{2} + q^{2} ≡ 2 (mod 4).

Lemma 17. (a) Suppose n = 2^{k}pq ⋯ r and k > 0. If pq ⋯ r is a product of an odd number of distinct primes, then n ∉ T^{∗}(2).

(b) Let n = 2^{k}p^{x}q^{y} ⋯ r^{z}, k > 0. Suppose the p, q, …, r are distinct odd primes and suppose that 2m + 1 of the exponents x, y, …, z are odd. Then n ∉ T^{∗}(2).

(c) Suppose n = 2^{k}pq ⋯ r and k > 1. If pq ⋯ r is a product of 4m + 2 distinct primes, then n ∉ T^{∗}(2).

Proof. This follows at once for (a) and (b) since n is even but T_{2}(n) is odd. Part (c) follows because n ≡ 0 (mod 4) but T_{2}(n) ≡ 2 (mod 4).

Lemma 18. Suppose n = 2^{k}pqrs and 1 ≤ k.

(a) If k = 1 then n ≠ T_{2}(n).

(b) If k = 2, then n ≠ T_{2}(n).

(c) Suppose p = 3 and n = 2^{k} · 3qrs. If k = 6m + 1 or 6m + 5, then n = 2^{k} · 3qrs ≠ T_{2}(n).

Proof. For (a), if k = 1, then n ≡ 2 (mod 4). But then T_{2}(n) ≡ 2^{2} + p^{2} + q^{2} + r^{2} + s^{2} ≡ 0 (mod 4).

For part (b) first let 3 < p. Then n ≡ 1, 2 (mod 3), but then T_{2}(n) ≡ 2 · 2^{2} + p^{2} + q^{2} + r^{2} + s^{2} ≡ 8 + 1 + 1 + 1 + 1 ≡ 12 ≡ 0 (mod 3). Now, let p = 3. Then n = 12qrs ≡ 0 (mod 3). Note that T_{2}(n) ≡ 2 · 2^{2} + 9 + q^{2} + r^{2} + s^{2} ≡ 8 + 0 + 1 + 1 + 1 ≡ 2 (mod 3).

For part (c), n ≡ 0 (mod 3) since p = 3. Say k = 6m + w, for w = 1 or 5. Then T_{2}(n) ≡ 4(6m + w) + 0 + 1 + 1 + 1 ≡ w ≡ 1, 5 (mod 3).

Theorem 19. Suppose n = 2^{k}pqrs. If k = 2m, then n ≠ T_{2}(n).

Proof. In view of Lemma 18, we assume 4 ≤ k = 2m. Now n ≡ 0 (mod 8), by hypothesis. We note that every odd integer u satisfies u = 4U + 1 or u = 4U − 1 for some U. In either case, u^{2} ≡ 1 (mod 8). Thus, T_{2}(n) = 2m(2^{2}) + p^{2} + q^{2} + r^{2} + s^{2} ≡ 4 (mod 8).

Theorem 20. Suppose n = 2^{k}pqrs for k = 6m + 5. Then n ≠ T_{2}(n).

Proof. We assume first, in view of Lemma 18(b), that 3 < p < q < r < s. Then n ≡ 1, 2 (mod 3) as each odd prime is ≡ 1, 2 (mod 3). However, T_{2}(n) ≡ (6m+5)4+1+1+1+1 ≡ 0 (mod 3). Now we assume p = 3. Then n ≡ 0 (mod 3), but T_{2}(n) ≡ (6m+5)4+0+1+1+1 ≡ 2 (mod 3).

Theorem 21. Suppose n = 2^{k}pqrs for k = 6m + 1. If n = T_{2}(n), then n ≡ 2 (mod 3).

Proof. By Lemma 18(c) we need not consider possibility p = 3. Hence, we now suppose 3 < p < q < r < s. Now, n = T_{2}(n) ≡ (6m + 1)4 + 1 + 1 + 1 + 1 ≡ 8 ≡ 2 (mod 3).

Corollary 22. Suppose n = 2^{k}pqrs for k = 6m + 1. If n = T_{2}(n), then pqrs ≡ 1 (mod 3).

Proof. We first note that 2^{6m+1} ≡ ((2^{6})^{m}) · 2 ≡ 1^{m} · 2 ≡ 2 (mod 3). If pqrs ≡ 2 (mod 3), then we have n ≡ 2^{6t+1}pqrs ≡ 2 · 2 ≡ 1 (mod 3), but this contradicts Theorem 21.

Theorem 23. Suppose n = 2^{k}pqrs for k = 6m + 3. If n = T_{2}(n), then n ≡ 1 (mod 3).

Proof. Observe 2^{k} ≡ (−1)^{6m+3} ≡ −1 ≡ 2 (mod 3). Thus, n = T_{2}(n) ≡ (6m + 3)4 + 1 + 1 + 1 + 1 ≡ 1 (mod 3).

Corollary 24. Suppose n = 2^{k}pqrs for k = 6m + 3. If n = T_{2}(n), then pqrs ≡ 2 (mod 3).

Proof. If pqrs ≡ 1 (mod 3), then n ≡ 2^{6t+1}pqrs ≡ 2 · 1 ≡ 2 (mod 3), contradicting Theorem 23.

Theorem 25. Suppose that n is a product of u distinct odd primes each greater than 3.

(a) If u = 6t + 3, then n ≠ T_{2}(n).

(b) If u = 6t + 1 and n = T_{2}(n), then it is necessary that an even number (possibly zero) of the primes must be congruent to 2 (mod 3).

(c) If u = 6t + 5 and n = T_{2}(n), then it is necessary that an odd number of the primes must be congruent to 2 mod 3.

Proof. (a) If y is any odd prime greater than 3, then y ≡ 1, −1 (mod 6). Thus, y^{2} ≡ 1 (mod 6). It follows that y^{2} ≡ 1 (mod 3). From this we infer T_{2}(n) ≡ 6t + 3 ≡ 0 (mod 3). But n is not a multiple of 3.

For part (b), T_{2}(n) ≡ 6t + 1 ≡ 1 (mod 3). Now n ≡ 1 (mod 3) since T_{2}(n) is. Thus the quantity of the prime factors which are congruent to 2 (mod 3) must be even — as, in pairs, they are (3m + 2)(3j + 2) ≡ 1 (mod 3).

For (c), T_{2}(n) ≡ 6t + 5 (mod 6) and thus T_{2}(n) ≡ 2 (mod 3). Hence, n ≡ 2 (mod 3). It follows that an odd number of the prime factors must be congruent to 2 (mod 3).

Corollary 26. Suppose n is a product distinct odd prime factors and n = 3qrs ⋯ t. Then, if n = T_{2}(n), n has 6u + 1 distinct odd factors for some u > 1.

Proof. Now n must have an odd number 2w+1 of distinct odd prime factors by Theorem 12. We calculate T_{2}(n) = 9 + q^{2} + r^{2} + ⋯ + t^{2} ≡ 2w (mod 3). Since T_{2}(n) = n ≡ 0 (mod 3) we see w = 3u for some u. Thus n has 6u + 1 distinct prime factors.

Theorem 27.

(a) If n = 2^{k}p^{2}qrs, then n ∉ T^{∗}(2).

(b) If n = 2^{k}(pq)^{2}rs and k > 1, then n ∉ T^{∗}(2).

(c) If n = 2^{k}(pqr)^{2}s then n ∉ T^{∗}(2).

(d) If n = p^{2}qrst, then n ∉ T^{∗}(2).

Proof. For part (a), n is even and T_{2}(n) is odd. For part (b), n ≡ 0 (mod 4) but T_{2}(n) ≡ 4k + 2p^{2} + 2q^{2} + r^{2} + s^{2} ≡ 2 (mod 4). For (c) T_{2}(n) = 4k + 2p^{2} + 2q^{2} + 2r^{2} + s^{2} ≡ 1 (mod 2). But n is even. For part (d), n is odd but T_{2}(n) is even.

Algorithm 1: Application of lemmas. Set n = 2^{6m+1}pqrs with pqrs ≡ 1 (mod 3).

(a) Select p = 2 (mod 3). Now exactly 1 or 3 of q, r, s must be 2 (mod 3). Test cases.

(b) Select p ≡ 1 (mod 3). Now exactly 2 or none of q, r, s is 2 (mod 3). Test cases. Set n = 2^{6m+3}pqrs with pqrs ≡ 2 (mod 3).

(c) Select p ≡ 1 (mod 3). Then one or three of q, r, s must be 2 (mod 3). Test cases.

(d) Select p = 2 (mod 3). Then none or two of q, r, s must be 2 (mod 3). Test cases.

Algorithm 2: Look at the Quadratic. Consider n = 2^{k}pqrs = T_{2}(n). This is quadratic in s. It is necessary that the discriminant Δ = b^{2} − 4ac be a perfect square. Evaluate the discriminant Δ to see if it is a perfect square: \sqrt{Δ} = \sqrt{2^{2k}p^{2}q^{2}r^{2} − 16k − 4(p^{2} + q^{2} + r^{2})}, and this expression is independent of s. (We actually factor a 4 before calculating Δ.)

In general, using Algorithm 2, we can say there are no ‘small’ solutions to n = T_{2}(n), meaning Δ is not a square number often enough, at least for b^{2} − 4ac < 2^{63}, for any 3 ≤ k < 33.

With k fixed at 3, our initial computer search was unsuccessful. We determined that our search always stopped because of the discriminant Δ. It was almost never a square. In first week of April 2016, for k = 3, we checked p in the first 100 primes, q in the first 5000 primes, and r in the first 10,000 primes. This revealed \sqrt{Δ} was never an integer, and thus neither was s.

We revised the algorithm, improving the search. First setting k = 3, the smallest ‘admissible’ value, we let the discriminant go up to 10^{24}, rather than specifically limiting p, q, and r. At last we finally found a square discriminant with p, q relatively small: p = 3, q = 23, and r = 304151. The number r = 304151 is the 26, 335^{th} prime. We mention that this discriminant Δ is given by Δ = 7046784011265625 = 5^{6} · 11^{2} · 61051^{2} = 83945125^{2}.

It did not lead to a suitable s. The resulting s = 167890801 is composite (13·97·211·631). The other root s = 551 = 19 · 29 was not a prime either but since p < s, it would have been considered and discarded earlier. Thus, the calculated n is n = 8 · 3 · 23 · 304151 · 167890801 = 28187413568252952. No other discriminant Δ < 10^{24} resulted in an integer s, with p < q < r < 2^{34}.

For this we had k fixed at 3. The next ‘admissible’ values of k are 7, 9, 13, and 15. But k = 13 for example will make the numbers 1000 times as large. As Richard K. Guy said, “There are not enough small numbers to meet the many demands made of them.” See [1, 2].

If you are looking at numbers on the order of 10^{30}, only about 1 in 10^{15} is a square. When the numbers are under 2^{64} (as much as the hardware does natively) we can check several hundred million per second on one CPU. When they get larger, we have to go to other methods, and can check on the order of 10^{6} per second per CPU. And 10^{15} divided by 10^{6} is a lot of seconds.

5 Conclusion

In searching for two prime power elements in a set T^{∗}(s) one needs to solve s = p^{k}−k = q^{i}−i, or equivalently solve for a positive integer solution to the equation p^{k} − q^{i} = k − i, for p, q distinct primes. Such solutions are plentiful for i = 1. It is clear that other solutions with i > 1 are very rare and may not exist.

C. R. Greathouse reports (private correspondence, February 08 2016) that there are no instances of such q^{i} with i > 1 up to 10^{40}. But there are about ten thousand less than 10^{40} with i = 1. For a contrast, when s = 3, the most abundant case, the elements in T^{∗}(3) start quite large and get much larger. Nevertheless, searching among larger numbers produced no more solutions.

The absence of “irregular” values in T^{∗}(2), or for other small s, is surprising to us — so surprising that we conjecture that card(T^{∗}(2)) = 2. Though we did not prove the conjecture, we were able to eliminate many forms for an integer n so that n ∉ T^{∗}(2). In any case, it is clear that infinitely many sets T^{∗}(s) will contain some power of a prime p. In fact, whenever s = p^{k} − k for some k, p^{p^{k}} will be in T^{∗}(s). But whether these values will be the minimum values (or the only values) in T^{∗}(s) is another (difficult) question.

References

[1] Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), 697–712.

[2] Richard K. Guy, The second strong law of small numbers. Math. Mag. 63 (1990), 3–20.

[3] Jean-Marie De Koninck and Florian Luca, Partial sums of powers of prime factors, J. Integer Sequences 10 (2007) Article 07.1.6.

[4] Jean-Marie De Koninck and Florian Luca, Integers representable as the sum of powers of their prime factors, Funct. Approx. Comment. Math. 33 (2005), 57–72.

[5] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences. Available at

   https://oeis.org.

2010 Mathematics Subject Classification: Primary 11A15; Secondary 11Y50, 11Y55. Keywords: factorization, sum of powers, integer sequence.

(Concerned with sequences \underline{A067688}, \underline{A068916}, \underline{A268036}, \underline{A268594}, and \underline{A318606}.)

Received August 20 2018; revised versions received March 20 2019; March 21 2019; May 13 2019. Published in Journal of Integer Sequences, May 18 2019.

Return to Journal of Integer Sequences home page.