A New Kind of Fibonacci-Like Sequence of Composite Numbers

Dan Ismailescu Department of Mathematics

Hofstra University 103 Hofstra University Hempstead, NY 11549

USA

dan.p.ismailescu@hofstra.edu

Jaesung Son Ridgewood High School 627 East Ridgewood Ave Ridgewood, NJ 07450

USA

sonjaesung@gmail.com

Abstract

An integer sequence (x_{n})_{n≥0} is said to be Fibonacci-like if it satisfies the binary recurrence relation

x_{n} = x_{n−1} + x_{n−2}, n ≥ 2.

We construct a new type of Fibonacci-like sequence of composite numbers.

1 The problem and previous results

In this paper we consider Fibonacci-like sequences, that is, sequences (x_{n})_{n=0}^{∞} satisfying the binary recurrence relation

x_{n} = x_{n−1} + x_{n−2}, n ≥ 2.  (1)

If x_{0} = 0 and x_{1} = 1 then x_{n} = F_{n}, the classical Fibonacci sequence. Similarly, when x_{0} = 2 and x_{1} = 1 then x_{n} = L_{n}, the Lucas sequence.

Graham [3] proved that there exist relatively prime positive integers x_{0} and x_{1} such that the sequence (x_{n})_{n=0}^{∞} defined by the recurrence above contains no prime numbers; x_{0} and x_{1} have 33 and 34 digits, respectively. Knuth [6] improved on Graham’s method and found a 17-digit pair. Soon after, Wilf [9] discovered a smaller 17-digit pair. Nicol [7] refined Knuth’s idea and found a 12-digit pair. Finally, Vsemirnov [8] found a smaller pair of 12 and 11 digits: x_{0} = 106276436867, x_{1} = 35256392432.

Let us describe the common idea used in proving these results. Start by looking for a finite set of quadruples (p_{i}, m_{i}, r_{i}, c_{i}), 1 ≤ i ≤ t with the following properties:

(a) each p_{i} is a prime;

(b) every p_{i} divides F_{m_{i}}, the m_{i}-th Fibonacci number;

(c) every positive integer n satisfies a congruence n ≡ r_{i} (mod m_{i}) for some i = 1, 2, …, t. In other words, {(r_{i}, m_{i})}_{i=0}^{i=t} is a covering system of the integers.

Next, define x_{0} and x_{1} as follows:

x_{0} ≡ c_{i}F_{m_{i}−r_{i}} (mod p_{i}) and x_{1} ≡ c_{i}F_{m_{i}−r_{i}+1} (mod p_{i}) for i = 1, 2, …, t. (2)

From the recurrence relation (1) it follows that in general, x_{n} ≡ c_{i}F_{n+m_{i}−r_{i}} (mod p_{i}). The divisibility property F_{m} | F_{sm} and condition (b) imply that p_{i} | x_{n} if n ≡ r_{i} (mod m_{i}).

Since x_{n} is an increasing sequence and all primes p_{i} are relatively small, condition (c) guarantees that (x_{n})_{n=0}^{∞} contains only composite numbers. The role of the parameters c_{i} is to minimize the solution corresponding to a given covering system.

As mentioned earlier, the current record is due to Vsemirnov whose construction is based on the following set of t = 17 quadruples (p_{i}, m_{i}, r_{i}, c_{i}):

\begin{matrix}p_{i} & 3 & 2 & 5 & 7 & 17 & 11 & 47 & 19 & 61 & 23 & 107 & 31 & 1103 & 181 & 41 & 541 & 2521 \\ m_{i} & 4 & 3 & 5 & 8 & 9 & 10 & 16 & 18 & 15 & 24 & 36 & 30 & 48 & 90 & 20 & 90 & 60 \\ r_{i} & 3 & 1 & 4 & 5 & 2 & 6 & 9 & 14 & 12 & 17 & 8 & 0 & 33 & 80 & 18 & 62 & 48 \\ c_{i} & 2 & 1 & 2 & 3 & 5 & 6 & 34 & 14 & 29 & 6 & 19 & 21 & 9 & 58 & 11 & 185 & 306 \end{matrix}

Table 1: Vsemirnov’s quadruples

Graham, Knuth and Wilf used similar covering systems except with primes 2207, 1087, 4481, 53, 109 and 5779 instead of 23, 1103, 107, 181 and 541. Nicol used primes 53, 109, 5779 instead of 107, 181, 541. A major factor in deciding the size of a solution is the product of the primes in the covering system: P = ∏_{i=1}^{t} p_{i}. The smaller the value of P, the greater the chance to find a smaller solution. Of all constructions mentioned above, Vsemirnov’s attains the smallest P. It is not known whether a better covering system can be found.

2 A new construction

We note that Izotov [5] was the first to propose an alternative approach to a different problem, namely that of construction of Sierpiński numbers, for which the only known solutions involved the use of covering systems. In fact, Erdős [4, Section F13] conjectured that Sierpiński numbers could only be constructed by the use of covering systems.

Similarly, all known examples of Fibonacci-like sequences of composite numbers are based on the existence of a finite covering set of primes {p_{1}, p_{2}, …, p_{t}}. In other words, all examples mentioned in the previous section have the property that for every positive integer n, there exists an i ∈ {1, 2, , …, t} with x_{n} ≡ 0 (mod p_{i}).

In this paper we construct a Fibonacci-like sequence of composite numbers for which such a covering set does not appear to exist. Our approach can be summarized as follows:

On one hand, we are going to choose two relatively prime positive integers x_{0} and x_{1}, such that for every nonnegative integer n, x_{2n+1} is equal to the product of two integers greater than 1, both of which can be written explicitly in terms of n, x_{0} and x_{1}.

On the other hand, we are going to find a finite set of prime numbers {p_{1}, p_{2}, …, p_{t}} such that for every nonnegative integer n, x_{2n} ≡ 0 (mod p_{i}) for some i ∈ {1, 2, …, t}.

We will thus obtain the desired Fibonacci-like sequence of composite numbers. Notice that there are different reasons why x_{n} is composite depending on the parity of n.

Theorem 1. Consider the sequence given by x_{0} = p^{2} + q^{2}, x_{1} = 2pq + q^{2}, x_{n} = x_{n−1} + x_{n−2} for all n ≥ 2, where p and q are integers. Then for every n ≥ 0 we have

x_{2n+1} = (pF_{n} + qF_{n+1})(pL_{n} + qL_{n+1}).  (3)

In particular, if p ≥ 1 and q ≥ 2, then x_{2n+1} is composite for all n ≥ 0.

Proof. It is known that the Fibonacci numbers can be written in matrix form as below

[\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{n−1} \end{matrix}] = [\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}]^{n} for all n ≥ 1.

Using the fact that A^{m+n} = A^{m}A^{n} with A = [ \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ] it follows that

[\begin{matrix}F_{m+n+1} & F_{m+n} \\ F_{m+n} & F_{m+n−1} \end{matrix}] = [\begin{matrix}F_{m+1} & F_{m} \\ F_{m} & F_{m−1} \end{matrix}] · [\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{n−1} \end{matrix}] from which

F_{m+n+1} = F_{m+1}F_{n+1} + F_{m}F_{n}.

In particular, taking m = n and m = n − 1 respectively, we obtain

F_{2n+1} = F_{n+1}^{2} + F_{n}^{2},  (4)
F_{2n} = 2F_{n}F_{n+1} − F_{n}^{2}.  (5)

It is easy to prove by induction that x_{n} = x_{0}F_{n−1} + x_{1}F_{n}. It follows that

x_{2n+1} = x_{0}F_{2n} + x_{1}F_{2n+1}

which after using equalities (4) and (5) gives

x_{2n+1} = x_{0}(2F_{n}F_{n+1} − F_{n}^{2}) + x_{1}(F_{n+1}^{2} + F_{n}^{2}) = (x_{1} − x_{0})F_{n}^{2} + 2x_{0}F_{n}F_{n+1} + x_{1}F_{n+1}^{2}. (6)

Regard the right hand term in the above equation as a quadratic form in the variables F_{n} and F_{n+1}. We want this quadratic form to be reducible over the integers for all n, which is equivalent to requiring the discriminant Δ = x_{0}^{2} − (x_{1} − x_{0})x_{1} to be a perfect square.

In other words we want to choose x_{0} and x_{1} as solutions of the diophantine equation

x_{0}^{2} + x_{0}x_{1} − x_{1}^{2} = k^{2}.  (7)

It is straightforward to check that x_{0} = p^{2} + q^{2}, x_{1} = 2pq + q^{2} is a solution of the above equation. Indeed, with the above choices for x_{0} and x_{1} we have

x_{0}^{2} + x_{0}x_{1} − x_{1}^{2} = (p^{2} + q^{2})^{2} + (p^{2} + q^{2})(2pq + q^{2}) − (2pq + q^{2})^{2} =
= p^{4} + 2p^{3}q − p^{2}q^{2} − 2pq^{3} + q^{4} = (p^{2} + pq − q^{2})^{2}.

This solution can be obtained by using the techniques for solving the general equation ax^{2} + bxy + cy^{2} = k^{2}; the interested reader may consult [1, Chapter XIII, pp. 404–409]. This explains our choices for x_{0} and x_{1}. Substituting now x_{0} = p^{2} + q^{2} and x_{1} = 2pq + q^{2} into (6) we obtain

x_{2n+1} = (2pq − p^{2})F_{n}^{2} + 2(p^{2} + q^{2})F_{n}F_{n+1} + (2pq + q^{2})F_{n+1}^{2} =
= p^{2}(2F_{n}F_{n+1} − F_{n}^{2}) + pq(2F_{n}^{2} + 2F_{n+1}^{2}) + q^{2}(2F_{n}F_{n+1} + F_{n+1}^{2}) =
= p^{2}F_{n}(2F_{n+1} − F_{n}) + 2pq(F_{n}^{2} + F_{n+1}^{2}) + q^{2}F_{n+1}(2F_{n} + F_{n+1}).

We use now some basic identities relating the Fibonacci and the Lucas numbers.

2F_{n+1} − F_{n} = F_{n+1} + (F_{n+1} − F_{n}) = F_{n+1} + F_{n−1} = L_{n}.
2F_{n} + F_{n+1} = F_{n} + (F_{n} + F_{n+1}) = F_{n} + F_{n+2} = L_{n+1}.
2(F_{n}^{2} + F_{n+1}^{2}) = F_{n}(2F_{n} + F_{n+1}) + F_{n+1}(2F_{n+1} − F_{n}) = F_{n}L_{n+1} + F_{n+1}L_{n}.

Substituting these into the last equality, we obtain

x_{2n+1} = p^{2}F_{n}L_{n} + pq(F_{n}L_{n+1} + F_{n+1}L_{n}) + q^{2}F_{n+1}L_{n+1} = (pF_{n} + qF_{n+1}) · (pL_{n} + qL_{n+1}).

Thus, equation (3) is satisfied. If p ≥ 1 and q ≥ 2 it follows that for all nonnegative integers n we have that pF_{n} + qF_{n+1} ≥ q ≥ 2 and pL_{n} + qL_{n+1} > p + q ≥ 3. It follows that x_{2n+1} is always composite. The proof is complete.

From Theorem 1 it follows that if one chooses x_{0} = p^{2} + q^{2} and x_{1} = 2pq + q^{2}, then for every n ≥ 0 we have that x_{2n+1} is composite. It remains to ensure that for every n ≥ 0, x_{2n} is also composite. In order to achieve this, we construct a finite partial covering set as described below.

We are looking for a collection of quadruples {(p_{i}, m_{i}, r_{i}, c_{i})}_{i=1}^{i=t} such that

(a) each p_{i} is a prime;

(b) every p_{i} divides F_{m_{i}}, the m_{i}-th Fibonacci number;

(c) every even positive integer 2n satisfies at least a congruence 2n ≡ r_{i} (mod m_{i}) for some i = 1, 2, …, t. In other words, {(r_{i}, m_{i})}_{i=0}^{i=t} is a partial covering system, as it covers all even integer values.

For every 1 ≤ i ≤ t, we have 1 ≤ c_{i} ≤ p_{i} − 1. These values are going to come into play later on, as we will require a certain system of congruences to be compatible.

Suppose we found such a set of quadruples. Choose x_{0} and x_{1} such that

x_{0} ≡ c_{i}F_{m_{i}−r_{i}} (mod p_{i}), x_{1} ≡ c_{i}F_{m_{i}−r_{i}+1} (mod p_{i}) for all 1 ≤ i ≤ t.  (8)

Let n ≥ 0 and let 1 ≤ i ≤ t be such that 2n ≡ r_{i} (mod m_{i}). The existence of such i is guaranteed by condition (b). From (2), we have

x_{2n} = x_{0}F_{2n−1} + x_{1}F_{2n} ≡ c_{i}(F_{m_{i}−r_{i}} · F_{2n−1} + F_{m_{i}−r_{i}+1} · F_{2n}) (mod p_{i})
≡ c_{i} F_{2n+m_{i}−r_{i}} (mod p_{i})
≡ c_{i} F_{sm_{i}} (mod p_{i})
≡ 0 (mod p_{i}).

Thus, x_{2n} ≡ 0 (mod p_{i}) and therefore composite. There is however one major difficulty in finding a partial covering system with the properties (a), (b) and (c) listed above, as every odd prime p_{i} has to satisfy the congruence p_{i} ≡ 1 (mod 4).

Let us explain why that is the case. First, we need the following simple result.

Lemma 2. For any positive odd integer m, the Fibonacci number F_{m} has no prime factors of the form 4l + 3.

Proof. Let m be odd and let p | F_{m}. From Cassini’s identity, we have F_{m+1}^{2} − F_{m}F_{m+2} = (−1)^{m}, which after reducing modulo p gives F_{m+1}^{2} ≡ −1 (mod p). This implies that −1 is a quadratic residue modulo p. By the quadratic reciprocity law this is true only when p ≡ 1 (mod 4).

Recall that in Theorem 1 we chose x_{0} and x_{1} such that x_{0}^{2} + x_{0}x_{1} − x_{1}^{2} = k^{2}. On the other hand, we selected x_{0} and x_{1} as in (8). It follows that for every 1 ≤ i ≤ t we have that

c_{i}^{2}(F_{m_{i}−r_{i}}^{2} + F_{m_{i}−r_{i}} · F_{m_{i}−r_{i}+1} − F_{m_{i}−r_{i}+1}^{2}) ≡ k^{2} (mod p_{i})  (9)

Using Cassini’s identity again, the above congruence can be simplified to c_{i}^{2}·(−1)^{m_{i}−r_{i}+1} ≡ k^{2} (mod p_{i}). In particular, (−1)^{m_{i}−r_{i}+1} is a quadratic residue modulo p_{i} for every 1 ≤ i ≤ t.

We want that for every n ≥ 0, the congruence 2n ≡ r_{i} (mod m_{i}) holds for some 1 ≤ i ≤ t. If m_{i} is even, then r_{i} is even as well, and therefore (−1)^{m_{i}−r_{i}+1} = −1, which is a quadratic residue modulo p_{i} if and only if p_{i} ≡ 1 (mod 4). If m_{i} is odd, then condition (b) states that p_{i} | F_{m_{i}}, and hence p_{i} ≡ 1 (mod 4) follows from Lemma 2.

Hence, none of the primes p_{i} in the partial covering system with properties (a), (b) and (c) can be of the form 4l + 3. Consider the set {(p_{i}, m_{i}, r_{i}, c_{i})}_{i=1}^{i=30} given in Table 2. It is straightforward to check that this system of quadruples has the desired properties.

\begin{matrix}p_{i} & m_{i} & r_{i} & c_{i} \\ 2 & 3 & 1 & 1 \\ 5 & 5 & 1 & 2 \\ 13 & 7 & 1 & 5 \\ 17 & 9 & 3 & 11 \\ 29 & 14 & 2 & 5 \\ 41 & 20 & 4 & 3 \\ 61 & 15 & 2 & 41 \\ 181 & 90 & 8 & 46 \\ 241 & 120 & 14 & 109 \\ 281 & 28 & 4 & 207 \\ 421 & 21 & 3 & 171 \\ 541 & 90 & 38 & 243 \\ 1009 & 126 & 90 & 294 \\ 1601 & 80 & 34 & 1259 \\ 2161 & 40 & 10 & 1706 \end{matrix}  \begin{matrix}p_{i} & m_{i} & r_{i} & c_{i} \\ 2521 & 60 & 20 & 636 \\ 3041 & 80 & 74 & 790 \\ 8641 & 360 & 18 & 4664 \\ 20641 & 120 & 110 & 1405 \\ 31249 & 126 & 42 & 901 \\ 103681 & 72 & 54 & 80856 \\ 109441 & 45 & 23 & 16635 \\ 141961 & 35 & 12 & 12156 \\ 721561 & 420 & 180 & 529617 \\ 1461601 & 252 & 186 & 970625 \\ 35239681 & 63 & 6 & 25860534 \\ 764940961 & 252 & 0 & 562105967 \\ 8288823481 & 105 & 33 & 83463210 \\ 10783342081 & 180 & 162 & 7785411056 \\ 571385160581761 & 504 & 222 & 49367403415248 \end{matrix}

Table 2: A finite partial covering system with no primes ≡ 3 (mod 4)

Let us notice that in order to check condition (c), it suffices to test the even numbers ≤ 5040. This is indeed the case since 5040 is the least common multiple of all the m_{i}, 1 ≤ i ≤ 30.

We are now in position to state the main result of this paper.

Theorem 3. Let p = 1 and q = 12951150255508108245872399074061259209531943793351− 2025195406541068394745828231264515958532145970461367703231950382110924410768870.

Define a sequence (x_{n})_{n≥0} by x_{0} = p^{2} +q^{2}, x_{1} = 2pq +q^{2}, x_{n} = x_{n−1} +x_{n−2}, for all n ≥ 2. Then gcd(x_{0}, x_{1}) = 1 and x_{n} is composite for all n ≥ 0.

Proof. By our choice of x_{0} and x_{1}, Theorem 1 immediately implies that x_{2n+1} is composite for every integer n ≥ 0.

We claim that for every n ≥ 1, x_{2n} has a factor in the set {p_{1}, p_{2}, …, p_{30}}, where the primes are those in Table 2. Indeed, let us first choose x_{0} and x_{1} according to (8)

x_{0} ≡ c_{i}F_{m_{i}−r_{i}} (mod p_{i}), x_{1} ≡ c_{i}F_{m_{i}−r_{i}+1} (mod p_{i}) for all 1 ≤ i ≤ 30,

where (p_{i}, m_{i}, r_{i}, c_{i}) are those given in Table 2. Since p = 1, x_{0} = p^{2} + q^{2} and x_{1} = 2pq + q^{2}, these congruences can be written as

1 + q^{2} ≡ c_{i}F_{m_{i}−r_{i}} (mod p_{i}), 2q + q^{2} ≡ c_{i}F_{m_{i}−r_{i}+1} (mod p_{i}) for all 1 ≤ i ≤ 30. (10)

\begin{matrix}p_{i} & q mod p_{i} \\ 2 & 0 \\ 5 & 0 \\ 13 & 0 \\ 17 & 11 \\ 29 & 20 \\ 41 & 34 \\ 61 & 55 \\ 181 & 149 \\ 241 & 134 \\ 281 & 45 \\ 421 & 140 \\ 541 & 307 \\ 1009 & 818 \\ 1601 & 1347 \\ 2161 & 799 \end{matrix}  \begin{matrix}p_{i} & q mod p_{i} \\ 2521 & 1934 \\ 3041 & 455 \\ 8641 & 1277 \\ 20641 & 13565 \\ 31249 & 24574 \\ 103681 & 22094 \\ 109441 & 43164 \\ 141961 & 112001 \\ 721561 & 170379 \\ 1461601 & 442479 \\ 35239681 & 5419606 \\ 764940961 & 483887978 \\ 8288823481 & 6095337569 \\ 10783342081 & 54018520 \\ 571385160581761 & 504780818763137 \end{matrix}

Table 3: Set of congruences satisfied by the solution of (10)

The choices of c_{i} ensure that this system has solutions: in particular, a solution is given by the set of congruences listed in Table 3.

The Chinese remainder theorem guarantees that there exists a q that satisfies all the above congruences. The smallest such value is the 129-digit number mentioned in the statement of Theorem 3.

It remains to argue why we believe this particular sequence (x_{n})_{n≥0} does not have a finite covering set of primes. Computer verifications show that there are 803 values of 0 ≤ n ≤ 200000 such that x_{n} has no prime factor ≤ 2 × 10^{6} or a prime factor among the primes p_{1}, p_{2}, …, p_{30} given in table 2. Moreover, any two such terms are mutually prime.

Also, it can be checked that for these choices for p and q, the numbers pF_{913} + qF_{914}, pL_{913} + qL_{914}, pF_{943} + qF_{944} and pL_{943} + qL_{944} are all primes of lengths 319, 320, 326 and 326, respectively. Since (3) gives that x_{1827} = (pF_{913} + qF_{914})(pL_{913} + qL_{914}) and x_{1887} = (pF_{943} + qF_{944})(pL_{943} + qL_{944}), it follows that x_{1827} and x_{1887} are both products of exactly two primes, with the least prime factor having lengths 319 and 326, respectively.

As a result, if a finite covering with primes would exist, it has to have at least 803 primes larger than 2 × 10^{6}, and among these, at least two primes of length 319 or greater. It seems difficult to prove that the least prime factor of x_{n} is unbounded as n tends to infinity. As already noticed by Filaseta, Finch and Kozek [2], this type of question is open even for much simpler sequences such as F_{n}, 5 · 2^{n} + 1 or 11 · 5^{n} − 1.

References

[1] L. E. Dickson, History of the Theory of Numbers, Vol. II: Diophantine Analysis, Chelsea Publishing Co., 1966.

[2] M. Filaseta, C. Finch and M. Kozek, On powers associated with Sierpiński numbers, Riesel numbers and Polignac’s conjecture, J. Number Theory 128 (2008), 1916–1940.

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

[4] R. K. Guy, Unsolved Problems in Number Theory (3rd ed.), Problem Books in Mathematics, Springer-Verlag, 2004.

[5] A. S. Izotov, A note on Sierpiński numbers, Fibonacci Quart. 33 (1995), 206–207.

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

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

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

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

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11A51, 11B37. Keywords: Fibonacci-like recurrence, composite numbers, system of covering congruences.

(Concerned with sequences \underline{A082411}, \underline{A083103}, \underline{A083104}, \underline{A083105}, \underline{A083216}, and \underline{A221286}.)

Received March 24 2014; revised version received July 8 2014; July 21 2014. Published in Journal of Integer Sequences, July 25 2014.

Return to Journal of Integer Sequences home page.