Partial Sums of Powers of Prime Factors

Jean-Marie De Koninck Département de Mathématiques et de Statistique Université Laval Québec G1K 7P4 Canada

                  jmdk@mat.ulaval.ca

Florian Luca Mathematical Institute, UNAM Ap. Postal 61-3 (Xangari) CP 58 089 Morelia, Michoacán Mexico

                 fluca@matmor.unam.mx

Abstract

Given integers k ≥ 2 and ℓ ≥ 3, let S_{k,ℓ}^{∗} stand for the set of those positive integers n which can be written as n = p_{1}^{k} + p_{2}^{k} + ⋯ + p_{ℓ}^{k}, where p_{1}, p_{2}, …, p_{ℓ} are distinct prime factors of n. We study the properties of the sets S_{k,ℓ}^{∗} and we show in particular that,

given any odd ℓ ≥ 3, # ⋃_{k=2}^{∞} S_{k,ℓ}^{∗} = +∞.

1 Introduction

In [1], we studied those numbers with at least two distinct prime factors which can be expressed as the sum of a fixed power k ≥ 2 of their prime factors. For instance, given an integer k ≥ 2, and letting

S_{k} := {n : ω(n) ≥ 2 and n = ∑_{p|n} p^{k}},

where ω(n) stands for the number of distinct prime factors of n, one can check that the following 8 numbers belong to S_{3}:

378 = 2 · 3^{3} · 7 = 2^{3} + 3^{3} + 7^{3},
2548 = 2^{2} · 7^{2} · 13 = 2^{3} + 7^{3} + 13^{3},
2 836 295 = 5 · 7 · 11 · 53 · 139 = 5^{3} + 7^{3} + 11^{3} + 53^{3} + 139^{3},
4 473 671 462 = 2 · 13 · 179 · 593 · 1621 = 2^{3} + 13^{3} + 179^{3} + 593^{3} + 1621^{3},
23 040 925 705 = 5 · 7 · 167 · 1453 · 2713 = 5^{3} + 7^{3} + 167^{3} + 1453^{3} + 2713^{3},
13 579 716 377 989 = 19 · 157 · 173 · 1103 · 23857 = 19^{3} + 157^{3} + 173^{3} + 1103^{3} + 23857^{3},
21 467 102 506 955 = 5 · 7^{3} · 313 · 1439 · 27791 = 5^{3} + 7^{3} + 313^{3} + 1439^{3} + 27791^{3}
119 429 556 097 859 = 7 · 53 · 937 · 6983 · 49199 = 7^{3} + 53^{3} + 937^{3} + 6983^{3} + 49199^{3}.

In particular, we showed that 378 and 2548 are the only numbers in S_{3} with exactly three distinct prime factors.

We did not find any number belonging to S_{k} for k = 2 or k ≥ 4, although each of these sets may very well be infinite.

In this paper, we examine the sets

S_{k}^{∗} := {n : ω(n) ≥ 2 and n = ∑_{p|n}^{∗}p^{k}} (k = 2, 3, …),

where the star next to the sum indicates that it runs over some subset of primes dividing n. For instance, 870 ∈ S_{2}^{∗}, because

870 = 2 · 3 · 5 · 29 = 2^{2} + 5^{2} + 29^{2}.

Clearly, for each k ≥ 2, we have S_{k}^{∗} ⊇ S_{k}. Moreover, given integers k ≥ 2 and ℓ ≥ 3, let S_{k,ℓ}^{∗} stand for the set of those positive integers n which can be written as n = p_{1}^{k} + p_{2}^{k} + ⋯ + p_{ℓ}^{k}, where p_{1}, p_{2}, …, p_{ℓ} are distinct prime factors of n, so that for each integer k ≥ 2,

S_{k}^{∗} = ⋃_{ℓ=3}^{∞} S_{k,ℓ}^{∗}.

We study the properties of the sets S_{k,ℓ}^{∗} and we show in particular that, given any odd ℓ ≥ 3,

the set ⋃_{k=2}^{∞} S_{k,ℓ}^{∗} is infinite. We treat separately the cases ℓ = 3 and ℓ ≥ 5, the latter case

being our main result.

In what follows, the letter p, with or without subscripts, always denotes a prime number.

2 Preliminary results

We shall first consider the set S_{2}^{∗}. Note that if n ∈ S_{2}^{∗}, then P (n), the largest prime divisor of n, must be part of the partial sum of primes which allows n to belong to S_{2}^{∗}. Indeed, assume the contrary, namely that, for some primes p_{1} < p_{2} < ⋯ < p_{r},

n = p_{1}^{α_{1}} ⋯ p_{r}^{α_{r}} = p_{i_{1}}^{2} + ⋯ + p_{i_{ℓ}}^{2} ∈ S_{2}^{∗},

where i_{1} < i_{2} < ⋯ < i_{ℓ} ≤ r − 1, with r ≥ 3. Then

p_{1} ⋯ p_{r−2}p_{r−1}p_{r} ≤ n < ℓp_{i_{ℓ}}^{2} ≤ rp_{r−1}^{2},

so that p_{1} ⋯ p_{r−2}p_{r} < rp_{r−1} < rp_{r}, which implies that p_{1} ⋯ p_{r−2} < r, which is impossible for r ≥ 3.

While by a parity argument one can easily see that each element of S_{k} (for any k ≥ 2) must have an odd number of prime factors, one can observe that elements of S_{k}^{∗} can on the contrary be written as a sum of an even number of prime powers, as can be seen with 298995972 ∈ S_{2}^{∗} (see below).

We can show that if Schinzel’s Hypothesis is true (see Schinzel [2]), then the set S_{3}^{∗} is infinite. We shall even prove more.

Theorem 1. If Schinzel’s Hypothesis is true, then #S_{3,3}^{∗} = +∞.

Proof. Assume that k is an even integer such that r = k^{2} − 9k + 21 and p = k^{2} − 7k + 13 are both primes, then n = 2rp(r + k) ∈ S_{3,3}^{∗}. Indeed, in this case, one can see that

n = 2rp(r + k) = 2^{3} + r^{3} + p^{3},  (1)

since both sides of (1) are equal to 2k^{6} − 48k^{5} + 492k^{4} − 2752k^{3} + 8844k^{2} − 15456k + 11466. Now Schinzel’s Hypothesis guarantees that there exist infinitely many even k’s such that the corresponding numbers r and p are both primes.

Note that the first such values of k are k = 2, 6, 10, 82 and 94. These yield the following four elements of S_{3,3}^{∗} (observing that k = 2 and k = 6 provide the same number, namely n = 378):

378 = 2 · 3^{3} · 7 = 2^{3} + 3^{3} + 7^{3},
109306 = 2 · 31 · 41 · 43 = 2^{3} + 31^{3} + 43^{3},
450843455098 = 2 · 6007 · 6089 · 6163 = 2^{3} + 6007^{3} + 6163^{3},
1063669417210 = 2 · 8011 · 8105 · 8191 = 2^{3} + 8011^{3} + 8191^{3}.

Not all elements of S_{3}^{∗} are generated in this way. For instance, the following numbers also belong to S_{3}^{∗}:

23391460 = 2^{2} · 5 · 23 · 211 · 241 = 2^{3} + 211^{3} + 241^{3},
173871316 = 2^{2} · 223 · 421 · 463 = 2^{3} + 421^{3} + 463^{3},
126548475909264420 = 2^{2} · 3 · 5 · 11 · 83 · 101 · 45569 · 501931
= 2^{3} + 5^{3} + 83^{3} + 45569^{3} + 501931^{3},

as well as all those elements of S_{3} mentioned in Section 1.

Theorem 2. # ⋃_{k=2}^{∞} S_{k,3}^{∗} = +∞.

Proof. This follows immediately from the fact that for each element n ∈ S_{k,3}^{∗}, one can find a corresponding element n′ ∈ S_{k(2r+1),3}^{∗} for r = 1, 2, . . .. Indeed, if n ∈ S_{k,3}^{∗}, then it means that

n = p_{1}^{k} + p_{2}^{k} + p_{3}^{k}

for some distinct primes divisors p_{1}, p_{2}, p_{3} of n. In particular, it means that p_{a}|(p_{b}^{k} + p_{c}^{k}) for each permutation (a, b, c) of the integers 1, 2 and 3. We claim that, given any positive integer r, the number

n′ := p_{1}^{k(2r+1)} + p_{2}^{k(2r+1)} + p_{3}^{k(2r+1)}

belongs to S_{k(2r+1),3}^{∗}. Indeed, we only need to show that p_{a}|(p_{b}^{k(2r+1)} + p_{c}^{k(2r+1)}) for each permutation (a, b, c) of the integers 1, 2 and 3. But this follows from the fact that (p_{b}^{k} + p_{c}^{k}) divides (p_{b}^{k(2r+1)} + p_{c}^{k(2r+1)}); but since p_{a} divides (p_{b}^{k} + p_{c}^{k}), we have that p_{a} divides (p_{b}^{k(2r+1)} + p_{c}^{k(2r+1)}) and therefore that n′ ∈ S_{k(2r+1),3}^{∗}. Since 378 ∈ S_{3,3}^{∗}, the proof is complete. Remark. It clearly follows from Theorems 1 and 2 that #S_{3(2r+1),3}^{∗} = +∞ for any r ≥ 1.

3 Proof of the main result

Theorem 3. Given any odd integer ℓ ≥ 5,

# ⋃_{k=2}^{∞} S_{k,ℓ}^{∗} = +∞.

This is an immediate consequence of the following two lemmas. Lemma 3.1. Let t = 2s ≥ 2 be an even integer and p_{1}, …, p_{t} be primes such that

(i) p_{i} ≡ 3 (mod 4) for all i = 1, …, t. (ii) gcd(p_{i}, p_{j} − 1) = 1 for all i, j in {1, …, t}. (iii) gcd(p_{i} − 1, p_{j} − 1) = 2 for all i ≠ j in {1, …, t}. Assume furthermore that a_{1}, …, a_{t} are integers and n_{1}, …, n_{t} are odd positive integers such that (iv) gcd(2n_{i} + 1, p_{i} − 1) = 1 for all i = 1, …, t.

(v) p_{i} | ∑_{j=1}^{t} p_{j}^{n_{i}} + a_{i}^{n_{i}} for all i = 1, …, t.

(vi) s = t/2 of the t numbers (\frac{a_{i}}{p_{i}} ) for i = 1, …, t are equal to 1 and the other s are equal

to −1. Then there exist infinitely many primes p such that S_{\frac{p−1}{2} ,t+1}^{∗} contains at least one element.

Proof. Let a be such that

a ≡ 2n_{i} + 1 (mod (p_{i} − 1)/2),  a ≡ 3 (mod 4),  a ≡ a_{i} (mod p_{i})  (2)

for all i = 1, …, t. The fact that the above integer a exists is a consequence of the Chinese Remainder Theorem and conditions (i)-(iii) above. Since n_{i} is odd, (p_{i} − 1)/2 is also odd and a ≡ 3 (mod 4), we conclude that the congruence a ≡ 2n_{i} + 1 (mod (p_{i} − 1)/2) implies a ≡ 2n_{i} + 1 (mod 2(p_{i} − 1)).

Now let M = 4 ∏_{i=1}^{t} \frac{p_{i}(p_{i} − 1)}{2}. Note that the number a is coprime to M by conditions

(i)-(iv). Thus, by Dirichlet’s Theorem on primes in arithmetic progressions, it follows that there exist infinitely many prime numbers p such that p ≡ a (mod M). It is clear that these primes satisfy the same congruences (2) as a does. Let p be such a prime and set

n = ∑_{i=1}^{t} p_{i}^{(p−1)/2} + p^{(p−1)/2}.

Note that since p ≡ 2n_{i} + 1 (mod 2(p_{i} − 1)), we get that (p − 1)/2 ≡ n_{i} (mod p_{i} − 1). Therefore by Fermat’s Little Theorem and condition (v) we get

n ≡ ∑_{j=1}^{t} p_{j}^{n_{i}} + p^{n_{i}} ≡ ∑_{j=1}^{t} p_{j}^{n_{i}} + a_{i}^{n_{i}} ≡ 0 (mod p_{i})

for all i = 1, …, t. Finally, conditions (i), (v) and the Quadratic Reciprocity Law show that from the t = 2s numbers

(\frac{p_{i}}{p} ) = − (\frac{p}{p_{i}} ) = − (\frac{a_{i}}{p_{i}} ) ,

exactly half of them are 1 and the other half are −1. Thus, half of the numbers p_{i}^{(p−1)/2} are congruent to 1 modulo p and the other half are congruent to −1 modulo p which shows that n is a multiple of p. Hence, n is a multiple of p_{i} for i = 1, …, t and of p as well, which implies that n ∈ S_{\frac{p−1}{2} ,t+1}^{∗}.

Lemma 3.2. If s ≥ 2 then there exist primes p_{i} and integers a_{i}, n_{i} for i = 1, …, t satisfying the conditions of Lemma 3.1.

Proof. Observe that t − 1 ≥ 3. Choose primes p_{1}, …, p_{t−1} such that p_{i} ≡ 11 (mod 12) for all i = 1, …, t − 1, gcd(p_{i}, p_{j} − 1) = 1 for all i, j in {1, …, t − 1}, gcd(p_{i} − 1, p_{j} − 1) = 2 for all i ≠ j in {1, …, t − 1} and finally p_{1} + ⋯ + p_{t−1} is coprime to p_{1} ⋯ p_{t−1}. Note that N = p_{1}+⋯+p_{t−1} is an odd number. Such primes can be easily constructed starting with say p_{1} = 11 and recursively defining p_{2}, …, p_{t−1} as primes in suitable arithmetic progressions. Take n_{i} = 1 for i = 1, …, t. Let q_{1}, …, q_{ℓ} be all the primes dividing N. Pick some integers

a_{1}, …, a_{t−1} such that s of the numbers (\frac{−a_{i}}{p_{i}} ) are −1 and the other s − 1 are 1. Now

choose a prime p_{t} such that p_{t} ≡ 11 (mod 12), p_{t} is coprime to p_{i} − 1 for i = 1, …, t − 1, p_{t} ≡ −a_{i} − N (mod p_{i}) for i = 1, …, t − 1, and (\frac{q_{i}}{p_{t}} ) = 1 for all i = 1, …, ℓ. For these last

congruences to be fulfilled, we note that it is enough to choose p_{t} ≡ 1 (mod q_{u}) if q_{u} ≡ 1 (mod 4) and p_{t} ≡ −1 (mod q_{u}) if q_{u} ≡ 3 (mod 4), where u = 1, …, ℓ. Notice that this choice is consistent with the fact that p_{t} ≡ 11 (mod 12) if it happens that one of the q_{u} is 3. So far, the primes p_{1}, …, p_{t} satisfy conditions (i)–(iii) of Lemma 3.1. Finally, put a_{t} = −N.

Note that (\frac{−a_{t}}{p_{t}} ) = ∏_{u=1}^{ℓ} (\frac{q_{u}}{p_{t}} )^{α_{u}} = 1. Here, α_{u} is the exact power of q_{u} in −a_{t}. Hence,

exactly s of the numbers (\frac{−a_{i}}{p_{i}} ) are 1 and the others are −1 and since all primes p_{i} are

congruent to 3 modulo 4 the same remains true if one replaces −a_{i} by a_{i}. Thus, condition (vi) of Lemma 3.1 holds. Now one checks immediately that (v) holds with n_{i} = 1 for all i = 1, …, t, because for all i = 1, …, t − 1 we have

∑_{j=1}^{t} p_{j}^{n_{j}} + a_{i}^{n_{i}} ≡ N + p_{t} + a_{i} (mod p_{i}) ≡ 0 (mod p_{i}),

while

∑_{j=1}^{t} p_{j}^{n_{j}} + a_{t} = N + p_{t} − N ≡ 0 (mod p_{t}),

and (iv) is obvious because 2n_{i} + 1 = 3 and p_{i} − 1 ≡ 10 (mod 12) is not a multiple of 3 for i = 1, …, t.

Remark. The above argument does not work for s = 1. Indeed, in this case t − 1 = 1, therefore p_{1} + ⋯ + p_{t−1} = p_{1} and this is not coprime to p_{1}.

4 Computational results and further remarks

To conduct a search for elements of S_{k}^{∗}, one can proceed as follows. If n ∈ S_{k,ℓ}^{∗}, then there exists a positive number Q and primes p_{1}, p_{2}, …, p_{ℓ} such that

n = Qp_{1} ⋯ p_{ℓ−1}p_{ℓ} = p_{1}^{k} + ⋯ + p_{ℓ−1}^{k} + p_{ℓ}^{k},

so that a necessary condition for n to be in S_{k,ℓ}^{∗} is that p_{ℓ}|(p_{1}^{k} + ⋯ + p_{ℓ−1}^{k}). (Note that some of the p_{i}’s may also divide Q.)

For instance, in order to find n ∈ S_{k,3}^{∗}, we examine the prime factors p of r^{k} + q^{k} as

2 ≤ r < q run through the primes up to a given x, and we then check if Q := \frac{r^{k} + q^{k} + p^{k}}{rqp}

is an integer. If this is so, then the integer n = Qrqp belongs to S_{k,3}^{∗}.

Proceeding in this manner (with ℓ = 3, 4), we found the following elements of S_{2}^{∗}:

870 = 2 · 3 · 5 · 29 = 2^{2} + 5^{2} + 29^{2},
188355 = 3 · 5 · 29 · 433 = 5^{2} + 29^{2} + 433^{2},
298995972 = 2^{2} · 3 · 11 · 131 · 17291 = 3^{2} + 11^{2} + 131^{2} + 17291^{2},
1152597606 = 2 · 3 · 5741 · 33461 = 2^{2} + 5741^{2} + 33461^{2},
1879906755 = 3 · 5 · 2897 · 43261 = 5^{2} + 2897^{2} + 43261^{2},
5209105541772 = 2^{2} · 3 · 11 · 17291 · 2282281 = 3^{2} + 11^{2} + 17291^{2} + 2282281^{2}.

Although we could not find any elements of S_{4}, we did find some elements of S_{4}^{∗}, but they are quite large. Here are six of them:

107827277891825604 = 2^{2} · 3 · 7 · 31 · 67 · 18121 · 34105993 = 3^{4} + 31^{4} + 67^{4} + 18121^{4},
48698490414981559698 = 2 · 3^{4} · 7 · 13 · 17 · 157 · 83537 · 14816023 = 2^{4} + 17^{4} + 83537^{4},

3137163227263018301981160710533087044 = 2^{2} · 3^{2} · 7 · 11 · 191 · 283 · 7541 · 1330865843 · 2086223663996743 = 3^{4} + 7^{4} + 191^{4} + 1330865843^{4},

129500871006614668230506335477000185618 = 2 · 3^{2} · 7 · 13^{2} · 31 · 241 · 15331 · 21613 · 524149 · 1389403 · 3373402577 = 2^{4} + 241^{4} + 3373402577^{4},

225611412654969160905328479254197935523312771590

= 2 · 3^{2} · 5 · 7 · 13^{2} · 37 · 41 · 109 · 113 · 127 · 151 · 541 · 911 · 5443

·3198662197 · 689192061269

= 5^{4} + 7^{4} + 113^{4} + 127^{4} + 911^{4} + 689192061269^{4}, 17492998726637106830622386354099071096746866616980

= 2^{2} · 5 · 7 · 23 · 31 · 97 · 103 · 373 · 1193 · 8689 · 2045107145539 · 2218209705651794191 = 2^{4} + 103^{4} + 373^{4} + 1193^{4} + 2045107145539^{4}.

Note that these numbers provide elements of S_{4,3}^{∗}, S_{4,4}^{∗}, S_{4,5}^{∗} and S_{4,6}^{∗}. The smallest elements of S_{2}^{∗}, S_{3}^{∗}, …, S_{10}^{∗} are the following:

870 = 2 · 3 · 5 · 29 = 2^{2} + 5^{2} + 29^{2}
378 = 2 · 3^{3} · 7 = 2^{3} + 3^{3} + 7^{3}
107 827 277 891 825 604 = 2^{2} · 3 · 7 · 31 · 67 · 18121 · 34105993 = 3^{4} + 31^{4} + 67^{4} + 18121^{4}
178 101 = 3^{2} · 7 · 11 · 257 = 3^{5} + 7^{5} + 11^{5}
594 839 010 = 2 · 3 · 5 · 17 · 29 · 37 · 1087 = 2^{6} + 5^{6} + 29^{6}
275 223 438 741 = 3 · 23 · 43 · 92761523 = 3^{7} + 23^{7} + 43^{7}
26 584 448 904 822 018 = 2 · 3 · 7 · 17 · 19 · 113 · 912733109 = 2^{8} + 17^{8} + 113^{8}
40 373 802 = 2 · 3^{4} · 7 · 35603 = 2^{9} + 3^{9} + 7^{9}
420 707 243 066 850 = 2 · 3^{2} · 5^{2} · 29 · 32238102917 = 2^{10} + 5^{10} + 29^{10}.

Below is a table of the smallest element n ∈ S_{k,ℓ}^{∗} for ℓ = 3, 4, 5, 6, 7 (with a convenient k):

ℓ n
3 378 = 2 · 3^{3} · 7 = 2^{3} + 3^{3} + 7^{3}
4 298995972 = 2^{2} · 3 · 11 · 131 · 17291 = 3^{2} + 11^{2} + 131^{2} + 17291^{2}
5 2 836 295 = 5 · 7 · 11 · 53 · 139 = 5^{3} + 7^{3} + 11^{3} + 53^{3} + 139^{3}
6 (a 48 digit number) = 5^{4} + 7^{4} + 113^{4} + 127^{4} + 911^{4} + 689192061269^{4}
7 (a 145 digit number) = 2^{14} + 3^{14} + 5^{14} + 11^{14} + 29^{14} + 149^{14} + 19809551197^{14}

Theorem 3 provides a way to construct infinitely many elements of S_{k,ℓ}^{∗} given any fixed positive odd integer ℓ. However, in practice, the elements obtained are very large. Indeed, take the case k = 5. With the notation of Lemma 1, we have t = 4; one can then choose {p_{1}, p_{2}, p_{3}, p_{4}} = {11, 47, 59, 227}. As suggested in Lemma 2, let n_{i} = 1 for i = 1, 2, 3, 4. An appropriate set of integers a_{i}’s is given by {a_{1}, a_{2}, a_{3}, a_{4}} = {8, 32, 10, 110}, which gives

\{(\frac{a_{i}}{p_{i}} ) : i = 1, 2, 3, 4\} = \{−1, 1, −1, 1\}. Looking for a solution a of the set of congruences

\{ \begin{matrix}a ≡ 3 (mod \frac{p_{i}−1}{2}) (i = 1, 2, 3, 4) \\ a ≡ 3 (mod 4) \\ a ≡ a_{i} (mod p_{i}) (i = 1, 2, 3, 4) \end{matrix} ,

we obtain a = 4 619 585 064 883. With M = 4 ∏_{i=1}^{4} \frac{p_{i}(p_{i} − 1)}{2} = 10 437 648 923 020, we notice

that indeed gcd(a, M) = 1. As the smallest prime number p ≡ a (mod M), we find p = 10M + a = 108 996 074 295 083. This means that the smallest integer n ∈ S_{k,5}^{∗} constructed with our algorithm is given by

n = ∑_{i=1}^{4} pi^{\frac{p−1}{2}} + p^{\frac{p−1}{2}} ,

which is quite a large integer since

n ≈ p^{\frac{p−1}{2}} ≈ (10^{14})^{\frac{1}{2} ·10^{14}} ≈ 10^{7·10^{14}}.

References

[1] J. M. De Koninck and F. Luca, Integers representable as the sum of powers of their prime factors, Functiones et Approximatio 33 (2005), 57–72.

[2] A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arith. 4 (1958), 185–208. Corrigendum: 5 (1959), 259.

2000 Mathematics Subject Classification: Primary 11A41; Secondary 11A25. Keywords: prime factorization.

Received January 5 2006; revised version received December 30 2006. Published in Journal of Integer Sequences, December 30 2006.

Return to Journal of Integer Sequences home page.