A Tribonacci-Like Sequence of Composite Numbers

Ivan Lunev Department of Mathematics and Mechanics Saint-Petersburg State University 28 Universitetsky Prospect St. Petersburg, 198504 Russia

                  lun-vano@yandex.ru

Abstract

We find a new Tribonacci-like sequence of positive integers ⟨x_{0}, x_{1}, x_{2}, …⟩ given by x_{n} = x_{n−1} + x_{n−2} + x_{n−3} , n ≥ 3, and gcd(x_{0}, x_{1}, x_{2}) = 1 that contains no prime numbers. We show that the sequence with initial values x_{0} = 151646890045, x_{1} = 836564809606, x_{2} = 942785024683 is the current record in terms of the number of digits.

1 Introduction

Šiurys [10] found initial values

x_{0} = 99202581681909167232
x_{1} = 67600144946390082339
x_{2} = 139344212815127987596,

satisfying gcd(x_{0}, x_{1}, x_{2}) = 1, such that the Tribonacci-like sequence given by

x_{n} = x_{n−1} + x_{n−2} + x_{n−3} for n ≥ 3  (1)

contains no prime numbers. Similar problems were considered for Fibonacci-like sequences given by x_{n} = x_{n−1} + x_{n−2} for n ≥ 2 (Graham [2]; Knuth [5]; Wilf [13]; Nicol [7]; Vsemirnov [12]; Ismailescu and Son [3]), sequences given by a_{n} = k2^{n} + 1 (Sierpiński [8]; Jaeschke [4]), binary linear recurrent sequences ( Dubickas, Novikas, and Šiurys [1]; Somer [11]) and some linear recurrent sequences of higher orders (Šiurys [9]).

The main result of this note is as follows.

2 The main results

Theorem 1. Let ⟨x_{0}, x_{1}, x_{2}, …⟩ be defined by (1) and gcd(x_{0}, x_{1}, x_{2}) = 1 with the following initial values:

x_{0} = 151646890045, x_{1} = 836564809606, x_{2} = 942785024683.

Then ⟨x_{0}, x_{1}, x_{2}, …⟩ contains no prime numbers.

Remark 2. If we allow non-positive values, we can find a slightly smaller (in absolute value) initial triple, namely

x_{0} = 730344594529, x_{1} = −45426674968, x_{2} = 151646890045.

3 Proof of Theorem 1

In this section we complete the proof of Theorem 1.

Proof of Theorem 1. First, recall Šiurys’ idea [10]. Consider the additional sequences (s_{n})_{n=0}^{∞} and (t_{n})_{n=0}^{∞} defined by the same relation (1) with (s_{0}, s_{1}, s_{2}) = (0, 1, 0) and (t_{0}, t_{1}, t_{2}) = (0, 0, 1).

Lemma 3 ([10]). Let p be a prime. Suppose that for some integer m ≥ 2 we have s_{m}t_{2m} − s_{2m}t_{m} ≡ 0 (mod p). Then there exist a, b ∈ ℤ such that at least one of a, b is not divisible by p and s_{km}a + t_{km}b ≡ 0 (mod p) for k = 0, 1, 2, . . ..

The next step is to find a set of pairs (p_{i}, m_{i}) satisfying Lemma 3 such that every integer belongs to at least one of the arithmetic progressions

A_{i} = m_{i}k + r_{i}, k ∈ ℤ, i = 1, 2, …, 11.  (2)

In this paper, the following values of p_{i} and m_{i} are used: (see Table 1).

Šiurys [10] used p = 79 with m = 40 instead of p = 239.

By Lemma 3, for every pair (p_{i}, m_{i}) we can choose (a_{i}, b_{i}) ∈ ℤ^{2} so that at least one of a_{i}, b_{i} is not divisible by p_{i} and i p_{i} m_{i}

|s_{m_{i}}t_{2m_{i}} − s_{2m_{i}}t_{m_{i}}|
1 2  2  2
2 29 5  29
3 17 6  2 · 17
4 7 8 2^{6} · 7
5 11 10  2 · 11 · 29
6 107 12  2^{3} · 17 · 107
7 8819 15  29 · 8819
8 19 20  2^{3} · 11 · 19 · 29 · 239
9 239 20  2^{3} · 11 · 19 · 29 · 239
10 1151 24  2^{6} · 7 · 17 · 107 · 1151
11 1621 30 2 · 11 · 17 · 29 · 1621 · 8819

Table 1: p_{i} and m_{i}.

s_{km_{i}}a_{i} + t_{km_{i}}b_{i} ≡ 0 (mod p_{i}) for k = 0, 1, 2, ….

Next, we construct a sequence (x_{n})_{n=0}^{∞} satisfying

x_{n} ≡ s_{m_{i}−r_{i}+n}a_{i} + t_{m_{i}−r_{i}+n}b_{i} (mod p_{i}),  i = 1, 2, …, 11,  for n = 0, 1, 2, ….

The initial values satisfy

x_{0} ≡ s_{m_{i}−r_{i}}a_{i} + t_{m_{i}−r_{i}}b_{i} (mod p_{i}), x_{1} ≡ s_{m_{i}−r_{i}+1}a_{i} + t_{m_{i}−r_{i}+1}b_{i} (mod p_{i}), x_{2} ≡ s_{m_{i}−r_{i}+2}a_{i} + t_{m_{i}−r_{i}+2}b_{i} (mod p_{i}), for i = 1, 2, …, 11.

We can find initial terms (x_{0}, x_{1}, x_{2}) by the Chinese reminder theorem. In the method described above there is some freedom in the choice of a_{i} and b_{i} (up to a

common factor). Šiurys [10] used all a_{i} equal to 1.

We show how to optimize the choice of a_{i} and b_{i}. Let P = ∏_{i=1}^{11} p_{i} . Let us consider the system:

x′_{0} ≡ Dx_{0} (mod P)
x′_{1} ≡ Dx_{1} (mod P)
x′_{2} ≡ Dx_{2} (mod P)

subject to the constraint

gcd(D, P) = 1.  (3)

The new triple (x′_{0}, x′_{1}, x′_{2}) also satisfies the above properties, i.e., each term of the sequence (1) with starting values (x′_{0}, x′_{1}, x′_{2}) is divisible by at least one of p_{1}, …, p_{11}.

For a moment, let us forget about condition (3). Then the problem can be formulated as follows: find the minimum vector of the form

D(x_{0}, x_{1}, x_{2}) + U_{1}(P, 0, 0) + U_{2}(0, P, 0) + U_{3}(0, 0, P),

i.e., the vector in the lattice generated by the vectors (x_{0}, x_{1}, x_{2}), (P, 0, 0), (0, P, 0), (0, 0, P). The smallest vector can be found by the LLL-algorithm [6].

For any admissible covering (2) with the above m_{i}’s we build the initial values (x_{0}, x_{1}, x_{2}) for the sequence (1) by using Šiurys’ method. Then using the LLL-algorithm we find the smallest lattice basis. Coordinates (x′_{0}, x′_{1}, x′_{2}) for each of the new three basis vectors will suit us, if the condition (3) is satisfied and (x′_{0}, x′_{1}, x′_{2}) are of the same sign (if all of them are negative, then replace (x′_{0}, x′_{1}, x′_{2}) by (−x′_{0}, −x′_{1}, −x′_{2})). Thus, searching through all possible coverings (the total amount is 23040) we find sets (p_{i}, m_{i}, r_{i}, a_{i}, b_{i}). Those listed in Table 2 give rise to the smallest initial triple x_{0} = 151646890045, x_{1} = 836564809606, x_{2} = 942785024683, as stated in Theorem 1.

i 1 2 3 4 5 6  7 8 9 10 11
m_{i} 2 5 6 8 10 12 15 20 20 24 30
p_{i} 2 29 17 7 11 107 8819 19 239 1151 1621
r_{i} 1 0 4 0 8 8  6 2 14 12 26
a_{i} 1 8 16 3 7 70 3246 12 202 1077 180
b_{i} 0 23 13 1 2 17 8805 8 103 964 291
Table 2: p_{i}, m_{i}, r_{i}, a_{i}, b_{i}.

If we allow non-positive terms in the sequence, the same method gives sets (p′_{i}, m′_{i}, r′_{i}, a′_{i}, b′_{i}), which give the sequence mentioned in the Remark 2: x_{0} = 730344594529, x_{1} = −45426674968, x_{2} = 151646890045 (see Table 3).

i 1 2 3 4 5 6  7 8 9 10 11
m_{i} 2 5 6 8 10 12 15 20 20 24 30
p_{i} 2 29 17 7 11 107 8819 19 239 1151 1621
r_{i} 1 2 0 2 0 10 8 4 16 14 28
a_{i} 1 8 7 3 7 70 3246 12 202 1077 180
b_{i} 0 23 11 1 2 17 8805 8 103 964 291
Table 3: p′_{i}, m′_{i}, r′_{i}, a′_{i}, b′_{i}.

It is worth noting that in the sequence mentioned in Remark 2 x_{2} = 151646890045, x_{3} = 836564809606, x_{4} = 942785024683, so this means that the sequence in Theorem 1 is a shift of the sequence in Remark 2.

Both sequences can be extended to the left. It can be shown that in both cases mentioned above these extended sequences also contain no primes. Since the sequences modulo P are periodic with period lcm(m_{1}, …, m_{11}) = 120, it is enough to check that x_{j} ≠ k modulo P, −8819 ≤ k ≤ 8819 = max(p_{i}), j = 0, …, 119.

References

[1] A. Dubickas, A. Novikas, and J. Šiurys, A binary linear recurrence sequence of composite numbers. J. Number Theory 130 (2010), 1737–1749.

[2] R. L. Graham, A Fibonacci-like sequence of composite numbers. Math. Mag. 37 (1964), 322–324.

[3] D. Ismailescu and J. Son, A new kind of Fibonacci-like sequence of composite numbers. J. Integer Sequences 17 (2014), Article 14.8.2.

[4] G. Jaeschke, On the smallest k such that all k2^{N} + 1 are composite. Math. Comp. 40 (1983), 381–384.

[5] D. E. Knuth, A Fibonacci-like sequence of composite numbers. Math. Mag. 63 (1990), 21–25.

[6] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515–534.

[7] J. W. Nicol, A Fibonacci-like sequence of composite numbers. Electron. J. Combin. 6 (1999), #R44.

[8] W. Sierpiński, Sur un problème concernant les nombres k2^{n} +1. Elem. Math. 15 (1960), 63–74.

[9] J. Šiurys, A linear recurrence sequence of composite numbers. LMS J. Comput. Math. 15 (2012), 360–373.

[10] J. Šiurys, A Tribonacci-like sequence of composite numbers. Fibonacci Quart. 49 (2011), 298–302.

[11] L. Somer, Second-order linear recurrences of composite numbers. Fibonacci Quart. 44 (2006), 358–361.

[12] M. Vsemirnov, A new Fibonacci-like sequence of composite numbers. J. Integer Sequences 7 (2004), Article 04.3.7.

[13] H. S. Wilf, Letters to the editor. Math. Mag. 63 (1990), 284.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B37. Keywords: Tribonacci-like recurrence, composite number.

(Concerned with \underline{A000045}, \underline{A000073}, and \underline{A056993}.)

Received November 20 2016; revised versions received November 25 2016; December 27 2016; January 3 2017. Published in Journal of Integer Sequences, January 3 2017.

Return to Journal of Integer Sequences home page.