Third-Order Recurrence Sequences with Infinitely Many Terms not Equal to the Sum of Two Prime Powers

Daniel Baczkowski and Bruce Keener Department of Mathematics The University of Findlay 1000 N. Main Street Findlay, OH 45840 USA

                    baczkowski@findlay.edu
                      keenerb@findlay.edu

Abstract We show in each of the Tribonacci, Padovan, Van der Laan, Perrin, Leonardo, and Narayana’s cows sequences that there are infinitely many terms that cannot be represented as the sum of two prime powers.

1 Introduction

One of the oldest and best-known unsolved problems in mathematics is Goldbach’s conjecture originating in 1742. It states that every even integer at least 4 is the sum of two prime numbers. When considering positive integers that cannot be represented as the sum of two primes (or not the sum of two prime powers) one is drawn toward the odd integers. Cohen and Selfridge [4] proved there exist infinitely many odd integers that are not the sum and not the difference of a power of two and a prime. Z.-W. Sun [10] found a smaller such integer when proving there exist infinitely many integers not of the form ±p^{a} ± q^{b} with primes p and q and nonnegative integers a and b. Moreover, it has been proven that there exist infinitely many polygonal numbers that are not the sum and not the difference of two prime powers [1].

That is, there exist infinitely many polygonal numbers that cannot be represented as p^{a} ± q^{b} with primes p and q and nonnegative integers a and b.

Luca and Stănică [9] showed there exist infinitely many Fibonacci numbers that cannot be represented as a sum of two prime powers. Similar results were proven for the Lucas numbers [2]. In this work, we prove analogous results for some third-order recurrence sequences. Moreover, we provide a general procedure for producing such results like those mentioned in the works above. Covering systems have been the main tool utilized in these works above and are the main tool used in this work.

A covering system of congruences (or more often simply called a covering) for the integers is a finite collection of congruences with the property that every integer satisfies at least one congruence in the system. More precisely, a covering for the integers is a finite set {(a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{t}, b_{t})} for which each integer n satisfies n ≡ a_{i} (mod b_{i}) for some 1 ≤ i ≤ t. The notion of coverings originated in the seminal paper of Erdős [6] who proved there are infinitely many odd numbers that are not of the form 2^{k} + p, where p is a prime.

Let r = (r_{k})_{k≥0} denote an integer valued linear homogeneous recurrence sequence. It is well known that such sequences are periodic modulo a positive integer m (e.g., [3, 5]). For a positive integer m, let h(m) = h_{r}(m) be the period of the sequence modulo m, and for an integer x let

A(x, m) = A_{r}(x, m) := {y (mod h(m)) : r_{y} ≡ x (mod m) with 0 ≤ y ≤ h(m) − 1}.

That is, A(x, m) is the set of all congruence classes y modulo h(m) such that r_{y} ≡ x (mod m). Throughout for some degree three linear homogeneous recurrence sequences, we compute such A sets. We simply use A(x, m) for each recurrence sequence. Since we consider each recurrence sequence in separate sections, there should be no confusion to the underlying sequence.

2 General procedure

In what follows, we present sufficient conditions and a general procedure for proving that a linear homogeneous recurrence sequence of integers has infinitely many terms (a positive proportion) that cannot be represented as the sum of two prime powers (i.e., cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b).

Theorem 1. Let (r_{k})_{k≥0} be a linear homogeneous recurrence sequence of integers. For each 1 ≤ i ≤ t, let a_{i} ≥ 0 and b_{i} > 0 be integers and p_{i} be prime. Consider the following system of congruences:

n ≡ a_{1} (mod b_{1}) & r_{k} ≡ 2^{a_{1}} (mod p_{1})
n ≡ a_{2} (mod b_{2}) & r_{k} ≡ 2^{a_{2}} (mod p_{2})
⋮
n ≡ a_{t} (mod b_{t}) & r_{k} ≡ 2^{a_{t}} (mod p_{t})  (1)

Let a_{0} = 0 and p_{0} = 2. Furthermore, assume

(i) The congruences involving n form a covering of the integers.

(ii) We have 2^{b_{i}} ≡ 1 (mod p_{i}) for each 1 ≤ i ≤ t.

(iii) There exists an integer k_{0} ∈ ⋂_{0≤i≤t} A(2^{a_{i}}, p_{i}).

Then for every k ≡ k_{0} (mod lcm(h(p_{0}), h(p_{1}), …, h(p_{t}))) that is sufficiently large we have r_{k} cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b.

Proof. Suppose the congruences involving n from Eqs. (1) form a covering of the integers and 2^{b_{i}} ≡ 1 (mod p_{i}) for each 1 ≤ i ≤ t. Let a_{0} = 0 and p_{0} = 2. Also, suppose that there exists an integer

k_{0} ∈ ⋂_{0≤i≤t} A(2^{a_{i}}, p_{i}).  (2)

Since the intersection in (2) is nonempty and contains k_{0}, note that every k ≡ k_{0} (mod L) with L = lcm(h(p_{0}), h(p_{1}), …, h(p_{t})) will also be in the intersection. Lastly, note that k ∈ A(1, 2) ensures that r_{k} is odd.

Now, suppose some r_{k} can be expressed as a sum of two prime powers; that is, suppose r_{k} = p^{a} + q^{b} for some primes p, q and nonnegative integers a, b. Since r_{k} is odd, one of the primes must be 2. Without loss of generality, we can write r_{k} = 2^{a} + q^{b}. Since the congruences involving n in Eqs. (1) form a covering of the integers, a must fit into a residue class expressed in one of the rows of the table. Suppose we have a ≡ a_{i} (mod b_{i}), where n ≡ a_{i} (mod b_{i}) & r_{k} ≡ 2^{a_{i}} (mod p_{i}) is row i in Eqs. (1). Since 2^{b_{i}} ≡ 1 (mod p_{i}), we deduce that r_{k} ≡ 2^{a} (mod p_{i}). In particular, p_{i} | (r_{k} − 2^{a}). However, r_{k} − 2^{a} = q^{b}, which implies that q = p_{i}. Thus, q ∈ {p_{1}, p_{2}, …, p_{t}}.

Let α_{1}, α_{2}, …, α_{s} denote the characteristic roots of the characteristic equation of r = (r_{j})_{j≥0}. Since r is a linear homogeneous recurrence sequence of integers, there exists complex numbers A_{1}, A_{2}, …, A_{s} such that

r_{j} = A_{1}α_{1}^{j} + A_{2}α_{2}^{j} + ⋯ + A_{s}α_{s}^{j}

for each j ≥ 0. Consider the equation

A_{1}α_{1}^{j} + A_{2}α_{2}^{j} + ⋯ + A_{s}α_{s}^{j} = 2^{a} + q^{b}.

This equation with q ∈ {p_{1}, p_{2}, …, p_{t}} can be viewed as an S-unit equation known to have only finitely many solutions (j, a, b) [7]. Thus, for sufficiently large k, we deduce that there are no solutions to r_{k} = 2^{a} + q^{b} with q ∈ {p_{1}, p_{2}, …, p_{t}}. It follows that if k is sufficiently large and k ≡ k_{0} (mod L), then r_{k} is not a sum of two prime powers. Hence, the conclusion of the theorem holds.

We now use Theorem 1 to prove results about some third-order recurrence sequences.

3 Tribonacci

Let (T_{k})_{k≥0} be the sequence of Tribonacci numbers defined by T_{0} = 0, T_{1} = 1, T_{2} = 1, and T_{k} = T_{k−1} + T_{k−2} + T_{k−3} for all k ≥ 3. As our first application of Theorem 1, we prove a theorem about the Tribonacci numbers.

Theorem 2. There are infinitely many Tribonacci numbers T_{k} that cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b. In fact, this occurs for every sufficiently large k ≡ 3817 (mod 163843680).

Proof. First consider the following table.

n ≡ 1 (mod 2) & T_{k} ≡ 2^{1} (mod 3)
n ≡ 2 (mod 4) & T_{k} ≡ 2^{2} (mod 5)
n ≡ 0 (mod 8) & T_{k} ≡ 2^{0} (mod 17)
n ≡ 1 (mod 3) & T_{k} ≡ 2^{1} (mod 7)
n ≡ 0 (mod 12) & T_{k} ≡ 2^{0} (mod 13)
n ≡ 20 (mod 24) & T_{k} ≡ 2^{20} (mod 241)

Table 1: Tribonacci congruences.

Note assumptions (i) and (ii) in Theorem 1 hold. The solutions for k such that T_{k} is odd and for each of the congruences involving T_{k} in Table 1 are

A(1, 2)  = {1, 2} (mod 4)
A(2^{1}, 3)  = {3, 8, 10} (mod 13)
A(2^{2}, 5)  = {4, 7, 8, 10, 11, 12, 17, 23, 28} (mod 31)
A(2^{0}, 17) = {1, 2, 17, 20, 21, 34, 52, 60, 62, 67, 69, 72, 73, 83, 89, 94} (mod 96)
A(2^{1}, 7)  = {3, 8, 10, 20, 25, 30, 33, 34, 43} (mod 48)
A(2^{0}, 13) = {\{1, 2, 11, 17, 36, 42, 72, 79, 82, 83, 93, 121, 127, 134, 141, 150, 161, \atop 166\} (mod 168)}
A(2^{20}, 241) = {458, 569, 745, 1117, 1686, 2137, 2443, 3146, 3449, 3817, 3915, 4195, ; 4410, 4524, 5176, 5669, 5701, 5738, 6115, 6685, 8014, 8339, 8345, 8709, ; 8938, 9066, 9194, 9196, 9526, 10166, 10216, 10239, 10510, 10719, 10793, ; 11213, 11286, 11636, 12067, 12081, 12869, 13126, 13133, 13633, 14402, ; 14666, 14861, 15553, 15667, 15974, 16172, 16291, 16618, 16687, 16698, ; 16825, 17251, 17459, 17512, 17612, 17628, 17772, 17950, 18000, 18426, ; 18484, 18851, 18905, 19041, 19070, 19357, 19483, 19509, 20028, 20234, ; 20316, 20581, 20716, 21015, 21034, 21101, 21112, 21520, 22166, 22560, ; 22605, 23044, 23175, 23322, 24371, 24654, 25004, 25405, 25567, 25692, ; 25755, 26204, 26254, 26642, 27324, 27402, 27754, 27956, 27974, 28073, ; 28218, 28720, 28845, 28890, 28956, 28974} (mod 29040).

Observe that the intersection of the A-sets above is nonempty; in fact, there are 216 distinct residues modulo 163843680 with the smallest being 3817. The result now follows from Theorem 1.

4 Padovan

Let (P_{k})_{k≥0} be the sequence of Padovan numbers defined by P_{0} = 1, P_{1} = 1, P_{2} = 1, and P_{k} = P_{k−2} +P_{k−3} for all k ≥ 3. We proceed with a similar theorem for the Padovan numbers.

Theorem 3. There are infinitely many Padovan numbers P_{k} that cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b. In fact, this occurs for every sufficiently large k ≡ 45750 (mod 967206240).

Proof. First consider the following table.

n ≡ 1 (mod 2) & P_{k} ≡ 2^{1} (mod 3)
n ≡ 2 (mod 4) & P_{k} ≡ 2^{2} (mod 5)
n ≡ 4 (mod 8) & P_{k} ≡ 2^{4} (mod 17)
n ≡ 2 (mod 3) & P_{k} ≡ 2^{2} (mod 7)
n ≡ 0 (mod 12) & P_{k} ≡ 2^{0} (mod 13)
n ≡ 16 (mod 24) & P_{k} ≡ 2^{16} (mod 241)

Table 2: Padovan congruences.

Note assumptions (i) and (ii) in Theorem 1 hold. The solutions for k such that P_{k} is odd and for each of the congruences involving P_{k} in Table 2 are

A(1, 2)  = {0, 1, 2, 5} (mod 7)
A(2^{1}, 3)  = {3, 4, 7} (mod 13)
A(2^{2}, 5)  = {6, 9, 15, 18} (mod 24)
A(2^{4}, 17) = {\{11, 37, 49, 53, 61, 92, 112, 115, 124, 135, 150, 173, 176, 186, 187, 227, \atop 246, 257, 279, 282\} (mod 288)}
A(2^{2}, 7)  = {6, 19, 20, 25, 27, 30, 32, 33, 34} (mod 48)
A(2^{0}, 13) = {\{0, 1, 2, 30, 66, 72, 92, 100, 131, 157, 170, 171, 176, 178, 181\} \atop (mod 183)}

A(2^{16}, 241) = {78, 285, 495, 545, 560, 801, 983, 1042, 1065, 1160, 1346, 1892, 1996, ; 2294, 2398, 2697, 3580, 3698, 4578, 4687, 4912, 5133, 5592, 6027, 6751, ; 7462, 7559, 7681, 7690, 7808, 8536, 8584, 9027, 9080, 9140, 9180, 9718, ; 10135, 10470, 11252, 11393, 11500, 11607, 11617, 11635, 11644, 11721, ; 12154, 12290, 12481, 12524, 13076, 13082, 13355, 13972, 14650, 15012, ; 15051, 15620, 16272, 17019, 17038, 17424, 17705, 17782, 18044, 18438, ; 18532, 18569, 18643, 19437, 19530, 19698, 19730, 19794, 20020, 20131, ; 20305, 20427, 20538, 20671, 20806, 21086, 21279, 21553, 21726, 22170, ; 22461, 22488, 22889, 23014, 23055, 23095, 23409, 23716, 23918, 24100, ; 24156, 24503, 25260, 25664, 25683, 26107, 26123, 26135, 26302, 27037, ; 27714, 27729, 27857, 27982, 28686, 29228, 29289, 29367, 29964, 30474, ; 30525, 30877, 31017, 31581, 31637, 31752, 31777, 32185, 32647, 32778, ; 33167, 33322, 33392, 33516, 34123, 34238, 34705, 34776, 34916, 35105, ; 35482, 35873, 35957, 36115, 36188, 36230, 36240, 36316, 36362, 36706, ; 36852, 37119, 37293, 37344, 37416, 37496, 37906, 38088, 38284, 38694, ; 38707, 38708, 38713, 38715, 38718, 38720, 38721, 38722, 38758, 39067, ; 39132, 39286, 39324, 39350, 39670, 39859, 39938, 40142, 40723, 41159, ; 41571, 41760, 41772, 42112, 42739, 42923, 43088, 43636, 43764, 43983, ; 44075, 44265, 44296, 45034, 45073, 45750, 45815, 45967, 46074, 46251, ; 46428, 46467, 46663, 46985, 47047, 48464, 48686, 48694, 48771, 49263, ; 49398, 49790, 50054, 50112, 50851, 50889, 51865, 52352, 52374, 52862, ; 53043, 53651, 53906, 54056, 54257, 54283, 54564, 54830, 55270, 55507, ; 55748, 55864, 55899, 56051, 56207, 56263, 56791, 56841, 56953, 57435, ; 57708, 57751, 57837} (mod 58080).

The intersection of the A-sets above is nonempty, and there are 360 distinct residues modulo 967206240 with the smallest being 45750. The result follows from Theorem 1.

5 Van der Laan

Let (V_{k})_{k≥0} be the sequence of Van der Laan numbers defined by V_{0} = 1, V_{1} = 0, V_{2} = 1, and V_{k} = V_{k−2} + V_{k−3} for all k ≥ 3.

Theorem 4. There are infinitely many Van der Laan numbers V_{k} that cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b. In fact, this occurs for every sufficiently large k ≡ 45752 (mod 967206240).

The proof of the theorem follows from the observation that V_{k} = P_{k−2}. From this fact, we are able to use the same covering as Table 2 and deduce that the intersection of the A-sets is nonempty; in fact, there are 360 total intersections with the smallest solution coming from k ≡ 45752 (mod 967206240).

6 Perrin

Let (E_{k})_{k≥0} be the sequence of Perrin numbers defined by E_{0} = 3, E_{1} = 0, E_{2} = 2, and E_{k} = E_{k−2} + E_{k−3} for all k ≥ 3.

Theorem 5. There are infinitely many Perrin numbers E_{k} that cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b. In fact, this occurs for every sufficiently large k ≡ 472190 (mod 967206240).

Proof. First consider the following table.

n ≡ 1 (mod 2) & E_{k} ≡ 2^{1} (mod 3)
n ≡ 0 (mod 4) & E_{k} ≡ 2^{0} (mod 5)
n ≡ 6 (mod 8) & E_{k} ≡ 2^{6} (mod 17)
n ≡ 1 (mod 3) & E_{k} ≡ 2^{1} (mod 7)
n ≡ 2 (mod 12) & E_{k} ≡ 2^{2} (mod 13)
n ≡ 18 (mod 24) & E_{k} ≡ 2^{18} (mod 241)

Table 4: Perrin congruences.

Note assumptions (i) and (ii) in Theorem 1 hold. The solutions for k such that E_{k} is odd and for each of the congruences involving E_{k} in Table 4 are

A(1, 2)  = {0, 3, 5, 6} (mod 7)
A(2^{1}, 3)  = {2, 4, 5, 6, 10, 12} (mod 13)
A(2^{0}, 5)  = {14, 22} (mod 24)
A(2^{6}, 17) = {41, 60, 94, 115, 121, 151, 156, 158, 198, 227, 263} (mod 288)
A(2^{1}, 7)  = {2, 4, 14, 27, 28, 45} (mod 48)
A(2^{2}, 13) = {\{10, 20, 32, 43, 48, 50, 54, 60, 70, 75, 77, 86, 101, 118, 130, 153, \atop 159, 178\} (mod 183)}
A(2^{18}, 241) = {162, 224, 867, 983, 1020, 1240, 1799, 1901, 1906, 1908, 2184, ; 2446, 2977, 3401, 3454, 3475, 3520, 3580, 3624, 3816, 3879, 4583, ; 4923, 5212, 5331, 5559, 5591, 6521, 7011, 7021, 7338, 7417, 7550, ; 7741, 7864, 8338, 8378, 8440, 8492, 8647, 8686, 8760, 8776, 9122, ; 9270, 9460, 9534, 9611, 10026, 10274, 10279, 10281, 11175, 11185, ; 11375, 11591, 11615, 11859, 11917, 12099, 12357, 12647, 13085, ; 13500, 13586, 13772, 14186, 14191, 14193, 14389, 14552, 14636, ; 14740, 15174, 15295, 15537, 15648, 15769, 15957, 16078, 16867, ; 17165, 17716, 19070, 19294, 19870, 20280, 20375, 20421, 20497, ; 21364, 21495, 21591, 21746, 22114, 22232, 22532, 23133, 23280, ; 23528, 23905, 24032, 24055, 24136, 24355, 24843, 25129, 25179, ; 25281, 25485, 25686, 26058, 26077, 26110, 26196, 26417, 26705,

26999, 27030, 27055, 27297, 27767, 27819, 28079, 28329, 28772, 29586, 29716, 29759, 29798, 30537, 31046, 31063, 31318, 31655, 31929, 32507, 32574, 33204, 33846, 34154, 34311, 34397, 34707, 34738, 34800, 34849, 34986, 35089, 35200, 35777, 36109, 36144, 36373, 36412, 36488, 36664, 36674, 37478, 37515, 37684, 37879, 38361, 38715, 38742, 39004, 39033, 39042, 40211, 40450, 40596, 41029, 41337, 41518, 41792, 41834, 41921, 42317, 42476, 42741, 43097, 43371, 43485, 44022, 44194, 44378, 44466, 45061, 45097, 45204, 45980, 47105, 47335, 47846, 48137, 48349, 48456, 48907, 49084, 49090, 49145, 49442, 49571, 49660, 49882, 50186, 51127, 51131, 51391, 51467, 51581, 51873, 51943, 52401, 52786, 53268, 53705, 53893, 53984, 54048, 54427, 55121, 55318, 55974, 56073, 56091, 56784, 56821, 57082, 57427, 57453} (mod 58080).

The intersection of the A-sets above is nonempty, and there are 288 distinct residues modulo 967206240 with the smallest being 472190. The result follows from Theorem 1.

7 Leonardo

Let (L_{k})_{k≥0} be the sequence of Leonardo numbers defined by L_{0} = 1, L_{1} = 1 and L_{k} = L_{k−1} + L_{k−2} + 1 for k ≥ 2. It is easy to show that L_{k} = 2L_{k−1} − L_{k−3} for all k ≥ 3; that is, the Leonardo sequence can be converted into a third-order linear homogeneous recurrence sequence.

Theorem 6. There are infinitely many Leonardo numbers L_{k} that cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b. In fact, this occurs for every sufficiently large k ≡ 539073 (mod 3543120).

Proof. First consider the following table.

n ≡ 0 (mod 2) & L_{k} ≡ 2^{0} (mod 3)
n ≡ 3 (mod 4) & L_{k} ≡ 2^{3} (mod 5)
n ≡ 0 (mod 3) & L_{k} ≡ 2^{0} (mod 7)
n ≡ 5 (mod 12) & L_{k} ≡ 2^{5} (mod 13)
n ≡ 7 (mod 18) & L_{k} ≡ 2^{7} (mod 19)
n ≡ 13 (mod 36) & L_{k} ≡ 2^{13} (mod 37)
n ≡ 1 (mod 9) & L_{k} ≡ 2^{1} (mod 73)

Table 7: Leonardo congruences.

Note assumptions (i) and (ii) in Theorem 1 hold. Also, note L_{k} is always odd. The solutions for k in each of the congruences involving L_{k} in Table 7 are

A(2^{0}, 3) = {0, 1, 6} (mod 8)
A(2^{3}, 5) = {2, 13, 15, 16} (mod 20)
A(2^{0}, 7) = {0, 1, 5, 14} (mod 16)
A(2^{5}, 13) = {17, 23} (mod 28)
A(2^{7}, 19) = {9} (mod 18)
A(2^{13}, 37) = {5, 31} (mod 76)
A(2^{1}, 73) = {15, 57} (mod 148).

Observe that the intersection of the A-sets above is nonempty; in fact, every integer k ≡ 539073 (mod 3543120) is in the intersection of the A-sets above. The result follows from Theorem 1.

8 Narayana’s cows

Let (N_{k})_{k≥0} denote Narayana’s cows sequence defined by N_{0} = 0, N_{1} = 1, N_{2} = 1, and N_{k} = N_{k−1} + N_{k−3} for all k ≥ 3. We refer to these as NC numbers.

Theorem 7. There are infinitely many NC numbers N_{k} that cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b. In fact, this occurs for every sufficiently large k ≡ 137042 (mod 718391520).

Proof. First consider the following table.

n ≡ 0 (mod 2) & N_{k} ≡ 2^{0} (mod 3)
n ≡ 3 (mod 4) & N_{k} ≡ 2^{3} (mod 5)
n ≡ 5 (mod 8) & N_{k} ≡ 2^{5} (mod 17)
n ≡ 2 (mod 3) & N_{k} ≡ 2^{2} (mod 7)
n ≡ 9 (mod 12) & N_{k} ≡ 2^{9} (mod 13)
n ≡ 1 (mod 24) & N_{k} ≡ 2^{1} (mod 241)

Table 8: Narayana congruences.

Note assumptions (i) and (ii) in Theorem 1 hold. The solutions for k such that N_{k} is odd and for each of the congruences involving N_{k} in Table 8 are

A(1, 2) = {1, 2, 3, 5} (mod 7)
A(2^{0}, 3) = {1, 2, 3, 6} (mod 8)
A(2^{3}, 5) = {5, 9, 11, 14, 21, 22, 24} (mod 31)
A(2^{5}, 17) = {\{18, 49, 54, 58, 68, 78, 105, 110, 115, 152, 163, 193, \atop 216, 228, 242, 278, 281\} (mod 288)}
A(2^{2}, 7) = {6, 13, 14, 17, 20, 21, 22, 42, 46} (mod 57)
A(2^{9}, 13) = {\{29, 34, 60, 67, 68, 79, 83, 89, 92, 119, 122, 136, 154, \atop 156\} (mod 168)}

A(2^{1}, 241) = {4, 190, 241, 667, 707, 944, 1117, 1199, 1522, 1767, ; 1910, 2043, 2302, 2610, 2677, 2771, 2777, 3079, 3203, ; 3232, 3252, 3482, 3546, 4145, 4172, 4276, 4330, 4340, ; 4411, 4447, 4518, 4521, 4628, 4680, 5020, 5484, 5857, ; 5925, 5993, 6425, 6513, 6646, 6668, 7266, 7542, 8956, ; 9006, 9032, 9198, 9384, 9485, 9520} (mod 9680).

The intersection of the A-sets above is nonempty, and there are 147 distinct residues modulo 718391520 with the smallest being 137042. The result follows from Theorem 1.

9 Concluding remarks

Given a third-order integer valued linear homogeneous recurrence sequence r = (r_{k})_{k≥0}, consider the sequence \overline{r} = (\overline{r_{k}})_{k≥0} defined with the same recurrence relation as r but with initial conditions \overline{r_{j}} = r_{j} +2m_{j}p_{1}p_{2} ⋯ p_{t} for each j ∈ \{0, 1, 2\}, where m_{0}, m_{1}, m_{2} are integers and p_{1}, p_{2}, …, p_{t} are primes. Then \overline{r_{k}} ≡ r_{k} (mod p_{i}) for every 1 ≤ i ≤ t and k ≥ 0, which implies that A_{r}(x, p_{i}) ⊆ A\overline{r}(x, p_{i}) for each 1 ≤ i ≤ t. Moreover, A_{r}(1, 2) ⊆ A\overline{r}(1, 2). Thus, for each of the named sequences described within this work, one can define another sequence containing infinitely many terms that cannot be represented as a sum of two prime powers. For example, consider the Tribonacci numbers. Given integers m_{0}, m_{1}, and m_{2}, define the sequence \overline{r} by

\overline{r_{k}} = T_{k} + 2 · 3 · 5 · 17 · 7 · 13 · 241 · m_{k}

for k ∈ \{0, 1, 2\} and \overline{r_{k}} = \overline{r_{k−1}} + \overline{r_{k−2}} + \overline{r_{k−3}} for all k ≥ 3. From Theorem 2 we deduce for every choice of integers m_{0}, m_{1}, and m_{2} that \overline{r} has infinitely many k such that \overline{r_{k}} cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b. In fact, this occurs for every sufficiently large k ≡ 3817 (mod 163843680). Therefore, our results can be used to produce classes of degree three linear homogeneous recurrence sequences such that each sequence has infinitely many terms that cannot be represented as the sum of two prime powers. The following is an immediate corollary summarizing this.

Corollary 1. There are infinitely many degree three linear homogeneous recurrence sequences such that each sequence has infinitely many terms that cannot be represented as p^{a} + q^{b} for some primes p, q and nonnegative integers a, b.

Lastly, we wonder for each of the named sequences described within this work if there exist infinitely many terms that are not the sum and not the difference of two prime powers. More precisely, let (r_{k})_{k≥0} denote one of the sequences studied in this work. Does there exist infinitely many k such that r_{k} cannot be represented as p^{a} ± q^{b} for some primes p, q and nonnegative integers a, b (i.e., cannot be represented as the sum or difference of two prime powers)? The current techniques to prove such results are related to proving the existence of infinitely many terms of the sequence that are simultaneously Sierpiński and Riesel numbers.

For the Fibonacci numbers, such a question appears to be related to the open problem of whether there exist infinitely many Fibonacci numbers that are both Sierpiński and Riesel numbers [8].

References

[1] D. Baczkowski and J. Eitner, Polygonal numbers that cannot be represented as p^{a} ± q^{b}, J. Comb. Number Theory 10 (2018), 19–25.

[2] D. Baczkowski, O. Fasoranti, and C. E. Finch, Lucas-Sierpiński and Lucas-Riesel numbers, Fibonacci Quart. 49 (2011), 334–339.

[3] J. L. Brenner, Linear recurrence relations, Amer. Math. Monthly 61 (1954), 171–173.

[4] F. R. Cohen and J. L. Selfridge, Not every number is the sum or difference of two prime powers, Math. Comp. 29 (1975), 79–81.

[5] H. T. Engstrom, Periodicity in sequences defined by linear recurrence relations, Proc. Natl. Acad. Sci. USA 16 (1930), 663–665.

[6] P. Erdős, On integers of the form 2^{k} + p and some related problems, Summa Brasil. Math. 2 (1950), 113–123.

[7] J.-H. Evertse, H. P. Schlickewei, and W. M. Schmidt, Linear equations in variables which lie in a multiplicative group, Ann. Math. 155 (2002), 807–836.

[8] D. P. Ismailescu and P. S. Park, On pairwise intersections of the Fibonacci, Sierpiński, and Riesel sequences, J. Integer Sequences 16 (2013), Article 13.9.8.

[9] F. Luca and P. Stănică, Fibonacci numbers that are not sums of two prime powers, Proc. Amer. Math. Soc. 133 (2005), 1887–1890.

[10] Z.-W. Sun, On integers not of the form ±p^{a} ± q^{b}, Proc. Amer. Math. Soc. 128 (2000), 997–1002.

2020 Mathematics Subject Classification: Primary 11A07; Secondary 11A41, 11B25, 11P32. Keywords: covering system, recurrence relation, Goldbach.

(Concerned with sequences \underline{A000073}, \underline{A000930}, \underline{A000931}, \underline{A001595}, and \underline{A001608}.)

Received January 29 2026; revised version received March 19 2026. Published in Journal of Integer Sequences, March 24 2026.

Return to Journal of Integer Sequences home page.