Fermat Padovan And Perrin Numbers

Salah Eddine Rihane Department of Mathematics

Institute of Science and Technology

University Center of Mila

Algeria

salahrihane@hotmail.fr

Chèfiath Awero Adegbindin

Institut de Mathématiques et de Sciences Physiques Dangbo Bénin

adegbindinchefiath@gmail.com

Alain Togbé

Department of Mathematics, Statistics, and Computer Science

Purdue University Northwest 1401 S., U.S. 421 Westville, IN 46391

USA

  atogbe@pnw.edu

Abstract

In this paper, we determine all the Padovan and Perrin numbers that are also Fermat numbers.

1 Introduction

The Padovan sequence {P_{m}}_{m≥0} is defined by

P_{m+3} = P_{m+1} + P_{m},  (1)

for m ≥ 0, where P_{0} = P_{1} = P_{2} = 1. This is the sequence \underline{A000931} in the On-Line Encyclopedia of Integer Sequences (OEIS). A few terms of this sequence are

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, ⋯

Let {E_{m}}_{m≥0} be the Perrin sequence given by

E_{m+3} = E_{m+1} + E_{m},  (2)

for m ≥ 0, where E_{0} = 3, E_{1} = 0, and E_{2} = 2. Its first few terms are

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853, ⋯

It is the sequence \underline{A001608} in the OEIS.

Let us also recall that a Fermat number is a number of the form

F_{m} = 2^{2^{m}} + 1,

where m is a nonnegative integer. The first elements of its list are

3, 5, 17, 257, 65537, 4294967297, 18446744073709551617,
340282366920938463463374607431768211457,

115792089237316195423570985008687907853269984665640564039457584007913129639937, ...

This is the sequence \underline{A019434} in the OEIS.

In a recent paper, Bravo and Herrera [2] found all k-Fibonacci and k-Lucas numbers that are also Fermat numbers. So the aim of this paper is to find all the Padovan and Perrin numbers that are also Fermat numbers. The proofs of the results that we obtained are mainly based on linear forms in logarithms of algebraic numbers and a reduction algorithm originally introduced by Baker and Davenport in [1]. Here, we use a version due to de Weger [7]. So in Section 2, we will recall some results based on Baker’s method, the Baker-Davenport reduction method (de Weger’s version), and some properties of Padovand and Perrin numbers. They are very useful for the proofs of our main results. In the last section, we will determine all Padovan and Perrin numbers that are Fermat numbers and show that these numbers are the only.

2 The tools

2.1 Linear forms in logarithms

We need some results from the theory of lower bounds for nonzero linear forms in logarithms of algebraic numbers. We start by recalling [3, Theorem 9.4], which is a modified version of a result of Matveev [6]. Let 𝕃 be an algebraic number field of degree d_{𝕃}. Let η_{1}, η_{2}, …, η_{l} ∈ 𝕃 not 0 or 1 and d_{1}, …, d_{l} be nonzero integers. We put

D = max{|d_{1}|, …, |d_{l}|},

and

Γ = ∏_{i=1}^{l} η_{i}^{d_{i}} − 1.

Let A_{1}, …, A_{l} be positive integers such that

A_{j} ≥ h′(η_{j}) := max{d_{𝕃}h(η_{j}), | log η_{j}|, 0.16}, for j = 1, … l,

where for an algebraic number η of minimal polynomial

f(X) = a_{0}(X − η^{(1)}) ⋯ (X − η^{(k)}) ∈ ℤ[X]

over the integers with positive a_{0}. We write h(η) for its Weil height given by

h(η) = \frac{1}{k} (log a_{0} + ∑_{j=1}^{k} max\{0, log |η^{(j)}|\}) .

The following consequence of Matveev’s theorem is [3, Theorem 9.4].

Theorem 1. If Γ ≠ 0 and 𝕃 ⊆ ℝ, then

log |Γ| > −1.4 · 30^{l+3}l^{4.5}d_{𝕃}^{2}(1 + log d_{𝕃})(1 + log D)A_{1}A_{2} ⋯ A_{l}.

2.2 The Baker-Davenport reduction method

Here, we present a variant of the reduction method of Baker and Davenport due to de Weger [7].

Let ϑ_{1}, ϑ_{2}, β ∈ ℝ be given and let x_{1}, x_{2} ∈ ℤ be unknowns. Let

Λ = β + x_{1}ϑ_{1} + x_{2}ϑ_{2}.  (3)

Let c, δ be positive constants. Set X = max{|x_{1}|, |x_{2}|}. Let X_{0}, Y be positive. Assume that

|Λ| < c · exp(−δ · Y),  (4)

X ≤ X_{0}.  (5)

When β = 0 in (3), we get

Λ = x_{1}ϑ_{1} + x_{2}ϑ_{2}.

Put ϑ = −ϑ_{1}/ϑ_{2}. We assume that x_{1} and x_{2} are coprime. Let the continued fraction expansion of ϑ be given by

[a_{0}, a_{1}, a_{2}, …],

and let the kth convergent of ϑ be p_{k}/q_{k} for k = 0, 1, 2, . . .. We may assume without loss of generality that |ϑ_{1}| < |ϑ_{2}| and that x_{1} > 0. We have the following results.

Lemma 2. (See [7, Lemma 3.2]) Let

A = max_{0≤k≤Y_{0}} a_{k+1},

where

Y_{0} = −1 + \frac{log(\sqrt{5}X_{0} + 1)}{log (\frac{1+\sqrt{5}}{2})}.

If (4) and (5) hold for x_{1}, x_{2} and β = 0, then

Y < \frac{1}{δ} log (\frac{c(A + 2)X_{0}}{|ϑ_{2}|} ) .  (6)

When β ≠ 0 in (3), put ϑ = −ϑ_{1}/ϑ_{2} and ψ = β/ϑ_{2}. Then we have

\frac{Λ}{ϑ_{2}} = ψ − x_{1}ϑ + x_{2}.

Let p/q be a convergent of ϑ with q > X_{0}. For a real number x, we let ∥x∥ = min{|x−n|, n ∈ ℤ} be the distance from x to the nearest integer. We have the following result.

Lemma 3. (See [7, Lemma 3.3]) Suppose that

∥ qψ ∥> \frac{2X_{0}}{q} .

Then, the solutions of (4) and (5) satisfy

Y < \frac{1}{δ} log (\frac{q^{2}c}{|ϑ_{2}|X_{0}} ) .

2.3 Properties of Padovan and Perrin sequences

In this subsection we recall some facts and properties of the Padovan and the Perrin sequences that will be used later. For more details about the Padovan and Perrin sequences, see [8].

The characteristic equation

x^{3} − x − 1 = 0

has roots α, β, γ = \overline{β}, where

α = \frac{r_{1} + r_{2}}{6} , β = \frac{−r_{1} − r_{2} + i\sqrt{3}(r_{1} − r_{2})}{12}

and

r_{1} = \sqrt[3]{108 + 12\sqrt{69}} and r_{2} = \sqrt[3]{108 − 12\sqrt{69}}.

Let

c_{α} = \frac{(1 − β)(1 − γ)}{(α − β)(α − γ)} = \frac{1 + α}{−α^{2} + 3α + 1},
c_{β} = \frac{(1 − α)(1 − γ)}{(β − α)(β − γ)} = \frac{1 + β}{−β^{2} + 3β + 1},  (7)
c_{γ} = \frac{(1 − α)(1 − β)}{(γ − α)(γ − β)} = \frac{1 + γ}{−γ^{2} + 3γ + 1} = \overline{c_{β}}.

Binet’s formula for P_{n} is

P_{n} = c_{α}α^{n} + c_{β}β^{n} + c_{γ}γ^{n}, for all n ≥ 0,  (8)

and Binet’s formula for E_{n} is

E_{n} = α^{n} + β^{n} + γ^{n}, for all n ≥ 0.  (9)

Numerically, we have

1.32 < α < 1.33,
0.86 < |β| = |γ| < 0.87,
0.72 < c_{α} < 0.73,  (10)
0.24 < |c_{β}| = |c_{γ}| < 0.25.

It is easy to check that

|β| = |γ| = α^{−1/2}.

Further, using induction, one can prove that

α^{n−2} ≤ P_{n} ≤ α^{n−1}, holds for all n ≥ 4  (11)

and

α^{n−2} ≤ E_{n} ≤ α^{n+1}, holds for all n ≥ 2,  (12)

see [5].

3 Proofs of the main results

In this section, we set and prove the two main results of our paper.

3.1 Our first main result

We will prove our first main result in this subsection.

Theorem 4. The only Fermat numbers in the Padovan sequence are P_{5} = 3 and P_{7} = 5.

Proof. Let us consider the Diophantine equation

P_{n} = 2^{m} + 1.  (13)

A quick computation with Maple reveals that the solutions of the Diophantine equation (13) in the interval [0, 150] are P_{3}, P_{4}, P_{5}, P_{7}, P_{9}, and P_{16}. It is easy to see that the only Fermat numbers are P_{5} and P_{7}.

From now, we assume that n > 150. Then by (11), we have

α^{n−2} < P_{n} = 2^{m} + 1 < 2^{m+1}

and

2^{m} < 2^{m} + 1 = P_{n} < α^{n−1}.

Thus we get

(n − 2)c_{1} − 1 < m < (n − 1)c_{1}, where c_{1} := log α/ log 2.

In particular, we have m < n/2. So to solve equation (13), it suffices to get a good upper bound for n.

By (8), equation (13) can be expressed as

2^{m} − c_{α}α^{n} = c_{β}β^{n} + c_{γ}γ^{n} − 1,

which we rewrite as

|2^{m} − c_{α}α^{n}| = |c_{β}β^{n} + c_{γ}γ^{n} − 1| < \frac{3}{2}.

Multiplying through by c_{α}^{−1}α^{−n}, we obtain

|2^{m}c_{α}^{−1}α^{−n} − 1| < 2.1α^{−n}.  (14)

Now, we apply Matveev’s theorem by taking

Γ := 2^{m}c_{α}^{−1}α^{−n} − 1

and

η_{1} := 2, η_{2} := c_{α}, η_{3} := α, b_{1} := m, b_{2} := −1, b_{3} := −n.

The algebraic numbers η_{1}, η_{2} and η_{3} belong to 𝕃 = ℚ(α) for which d_{𝕃} = 3. Since m < n/2, therefore we can take D := n = max{1, m, n}. Furthermore, we have

h(η_{1}) = log 2 and h(η_{3}) = \frac{log α}{3}.

In this case we choose

max{3h(η_{1}), |log η_{1}| , 0.16} < 2.1 := A_{1}

and

max{3h(η_{3}), |log η_{3}| , 0.16} = log α := A_{3}.

On the other hand, the minimal polynomial of c_{α} is

23x^{3} − 23x^{2} + 6x − 1

and has roots c_{α}, c_{β} and c_{γ}. Since |c_{α}| < 1 and |c_{β}| = |c_{γ}| < 1, then we get

h(η_{2}) = \frac{log 23}{3}.

So we can take

max{3h(η_{2}), |log η_{2}| , 0.16} < 3.2 := A_{3}.

To apply Matveev’s theorem we will prove that Γ ≠ 0. Suppose the contrary i.e Γ = 0, so we get

2^{m} = c_{α}α^{n}.

Conjugating the above relation using the ℚ-automorphism of Galois σ defined by σ = (αβ) and taking the absolute value we obtain

1 < 2^{m} = |c_{β}| |β|^{n} < 1,

which is a contradiction. Thus one can see that Γ ≠ 0.

Using Matveev’s theorem, we get

log |Γ| > −1.4 · 30^{6} · 3^{4.5} · 3^{2}(1 + log 3)(1 + log n) · 2.1 · log α · 3.2
> −1.82 · 10^{13} · log α · (2 log n) = 3.64 · 10^{13} · log α · log n.

The last inequality together with (14) leads to

n < 3.65 · 10^{13} log n.

Thus we obtain

n < 1.3 · 10^{15}.  (15)

Now, we will use Lemma 3 to reduce the upper bound (15) of n.

Define

Λ := m log 2 − n log α + log(1/c_{α}).

Clearly, we have e^{Λ} − 1 = Γ. Since Γ ≠ 0, then Λ ≠ 0. If Λ > 0, then we get

0 < Λ < e^{Λ} − 1 = |e^{Λ} − 1| = |Γ| < 2.1α^{−n}.

If Λ < 0, then we have 1 − e^{Λ} = |e^{Λ} − 1| = |Γ| < 1/2, because n > 150. This implies that e^{|Λ|} < 2. Thus we have

0 < |Λ| < e^{|Λ|} − 1 = e^{|Λ|} |Γ| < 4.2α^{−n}.

From both cases, we deduce that

0 < |n(− log α) + m log 2 + log(1/c_{α})| < 4.2 exp(−n log α).

The inequality (15) implies that we take X_{0} := 1.3 · 10^{13}. Further, we choose

c := 4.2, δ := log α, ψ := \frac{log(1/c_{α})}{log 2}

ϑ := \frac{log α}{log 2}, ϑ_{1} := − log α, ϑ_{2} := log 2, β := log(1/c_{α}).

Using Maple, we see that

q_{41} = 2263631680285337

satisfies the hypotheses of Lemma 3. Furthermore, Lemma 3 implies that

n < \frac{1}{log α} log (\frac{2263631680285337^{2} · 4.2}{log 2 · 1.3 · 10^{13}}) ≤ 150.  (16)

This contradicts the assumption that n > 150. Therefore, the theorem is proved.

3.2 Our second main result

In this subsection we will prove the following result.

Theorem 5. The only Fermat numbers in the Perrin sequence are E_{0} = E_{3} = 3, E_{5} = E_{6} = 5, and E_{10} = 17.

Proof. Let us consider the Diophantine equation

E_{n} = 2^{m} + 1.  (17)

A quick computation in Maple reveals that the solutions of Diophantine equation (13) in the interval [0, 150] are E_{0}, E_{2}, E_{3}, E_{4}, E_{5}, E_{6} and E_{10}. It is easy to see that the only Fermat numbers are E_{0}, E_{3}, E_{5}, E_{6} and E_{10}.

From now, we assume that n > 150, then by (12) we have

α^{n−2} < E_{n} = 2^{m} + 1 < 2^{m+1}

and

2^{m} < 2^{m} + 1 = E_{n} < α^{n+1}.

Then, we get

(n − 2)c_{1} − 1 < m < (n + 1)c_{1}, where c_{1} := log α/ log 2.

In particularly we have m < n/2. To solve equation (17), it suffices to get a good upper bound for n.

By (9), equation (17) can be rewritten into the form

2^{m} − α^{n} = β^{n} + γ^{n} − 1.

So we deduce that

|2^{m} − α^{n}| = |β^{n} + γ^{n} − 1| < 2.8.

Dividing both sides by α^{−n}, we get

|2^{m}α^{−n} − 1| < 2.8α^{−n}.  (18)

Now, we apply Matveev’s theorem by taking

Γ′ := 2^{m}α^{−n} − 1

and

η_{1} := 2, η_{2} := α, b_{1} := m, b_{2} := −n.

The algebraic numbers η_{1} and η_{2} belong to 𝕃 := ℚ(α) for which d_{𝕃} = 3. Since m < n/2, therefore we take D := n = max{1, m, n}. As seen before, we choose

A_{1} := 2.1 and A_{2} := log α.

We can prove that Γ′ ≠ 0 using the same method as above to show that Γ ≠ 0. Matveev’s theorem gives

log |Γ′| > −1.4 · 30^{5} · 2^{4.5} · 3^{2}(1 + log 3)(1 + log n) · 2.1 · log α
> −3.06 · 10^{10} · log α · (2 log n) = −6.12 · 10^{10} · log α · log n.

Comparing the last inequality with (18) yields

n < 6.13 · 10^{10} log n.

Consequently, we obtain

n < 1.8 · 10^{12}.  (19)

Now, to reduce the upper bound (19) of n, we will use Lemma 2.

Consider

Λ′ := m log 2 − n log α.

Clearly, we have e^{Λ′} − 1 = Γ′. Since Γ′ ≠ 0, then Λ′ ≠ 0. If Λ′ > 0, then we get

0 < Λ′ < e^{Λ′} − 1 = |e^{Λ′} − 1| = |Γ′| < 2.8α^{−n}.

If Λ′ < 0, then we have 1 − e^{Λ′} = |e^{Λ′} − 1| = |Γ′| < 1/2, because n > 150. Thus e^{|Λ′|} < 2. Therefore, we obtain

0 < |Λ′| < e^{|Λ′|} − 1 = e^{|Λ′|} |Γ′| < 5.6α^{−n}.

In both cases we have

0 < |n(− log α) + m log 2| < 5.6 exp(− log α · n).

The inequality (15) implies that we can take X_{0} := 1.8 · 10^{12}, thus we get Y_{0} = 59.3134 . . .. Further, we choose

c := 5.6, δ := log α, ϑ := \frac{log α}{log 2}, ϑ_{1} := − log α, ϑ_{2} := log 2.

We use Maple to find that

A := max_{0≤k≤59} a_{k+1} = 80.

So Lemma 2 tells us

n < \frac{1}{log α} log (\frac{5.6 · (80 + 2) · 1.8 · 10^{12}}{log 2} ) ≤ 126.  (20)

This contradicts the assumption that n > 150. Therefore, the theorem is proved.

References

[1] A. Baker and H. Davenport, The equations 3x^{2} − 2 = y^{2} and 8x^{2} − 7 = z^{2}, Quart. J. Math. Oxford Ser. (2) 20 (1969), 129–137.

[2] J. J. Bravo and J. L. Herrera, Fermat k-Fibonacci and k-Lucas numbers, Math. Bohem. 145 (2020), 19–32.

[3] Y. Bugeaud, M. Maurice, and S. Siksek, Classical and modular approaches to exponential Diophantine equations I. Fibonacci and Lucas perfect powers, Ann. Math. 163 (2006), 969–1018.

[4] A. Dujella and A. Pethő, A generalization of a theorem of Baker and Davenport, Quart. J. Math. Oxford Ser. (2) 49 (1998), 291–306.

[5] A. C. G. Lomelí and S. H. Hernández, Repdigits as sums of two Padovan numbers, J. Integer Sequences 22 (2019), Article 19.2.3.

[6] E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers, II, Izv. Math. 64 (2000), 1217–1269.

[7] B. M. M. de Weger, Algorithms for Diophantine Equations, Stichting Mathematisch Centrum, 1989.

[8] B. M. M. de Weger, Padua and Pisa are exponentially far apart, Publ. Sec. Mat. Univ. Autònoma Barcelona 41 (1997), 631–651.

2010 Mathematics Subject Classification: Primary 11J86; Secondary 11B39. Keywords: Padovan number, Perrin number, Fermat number, linear form in logarithms, reduction method.

(Concerned with sequences \underline{A000931}, \underline{A001608}, and \underline{A019434}.)

Received October 19 2019; revised versions received May 5 2020; May 6 2020; June 3 2020. Published in Journal of Integer Sequences, June 9 2020.

Return to Journal of Integer Sequences home page.