On Tribonacci Numbers that are Products of Factorials

Adel Alahmadi

Research Group in Algebraic Structures and Applications

King Abdulaziz University Jeddah Saudi Arabia

             analahmadi@kau.edu.sa

Florian Luca School of Mathematics University of the Witwatersrand 1 Jan Smuts Avenue Braamfontein 2050 Johannesburg South Africa and

Research Group in Algebraic Structures and Applications

King Abdulaziz University Jeddah Saudi Arabia and Centro de Ciencias Matemáticas UNAM Morelia México

            florian.luca@wits.ac.za

Abstract We determine all Tribonacci numbers of positive or negative indices that are prod-

ucts of factorials.

1 Introduction

The Tribonacci numbers {T_{n}}_{n≥0} are given by T_{0} = 0, T_{1} = T_{2} = 1 and T_{n+3} = T_{n+2} + T_{n+1} +T_{n} for n ≥ 0. In [5], Marques and Lengyel determined all Tribonacci numbers T_{n} that are factorials. They showed that if T_{n} = m! then n ∈ {1, 2, 3, 7}. Here we take this a couple of steps further.

Theorem 1. If n ≥ 1 and

T_{n} = m_{1}! m_{2}! ⋯ m_{k}!

for some positive integers m_{1} ≤ m_{2} ≤ ⋯ ≤ m_{k}, then n ∈ {1, 2, 3, 4, 7}.

Next, one can extend the sequence of Tribonacci numbers in the negative direction using the recurrence relation. Namely, since T_{0} = 0, T_{1} = T_{2} = 1, one computes that T_{−1} = 0, T_{−2} = 1 and for n ≥ 3, we have

T_{−n} = −T_{−(n−1)} − T_{−(n−2)} + T_{−(n−3)}.

The Tribonacci numbers with negative indices change signs infinitely often. Nevertheless, we can still ask what about the equation |T_{n}| = m_{1}! ⋯ m_{k}!. Here is our result.

Theorem 2. If n ∈ ℤ and |T_{n}| = m_{1}! m_{2}! ⋯ m_{k}! then

n ∈ {−9, −8, −7, −5, −3, −2, 1, 2, 3, 4, 7}.

Note the near miss T_{−32} = −2^{4} · 3 · 5^{2} · 7 = 7! · (5/3).

2 Preliminaries

The main ingredient is an exact formula for the exponent of 2 in T_{n}. Let ν_{p}(m) be the exponent of the prime p in the factorization of the integer m with convention that ν_{p}(0) = ∞. Here is Theorem 1 in [5].

Theorem 3. For n ≥ 1, we have

ν_{2}(T_{n}) = \begin{cases}0, & if n ≡ 1, 2 (mod 4); \\ 1, & if n ≡ 3, 11 (mod 16); \\ 2, & if n ≡ 4, 8 (mod 16); \\ ν_{2}(n) − 1, & if n ≡ 0 (mod 16); \\ ν_{2}(n + 4) − 1 & if n ≡ 12 (mod 16); \\ ν_{2}(n + 17) + 1 & if n ≡ 15 (mod 32); \\ ν_{2}(n + 1) + 1 & if n ≡ 31 (mod 32). \end{cases}

A similar theorem is proved for the prime p = 3 in [1].

Theorem 4. For n ≥ 1, we have

ν_{3}(T_{n}) = \begin{cases}0, & if n ≡ 1, 2, 3, 4, 5, 6, 8, 10, 11 (mod 13); \\ 1, & if n ≡ 7 (mod 13); \\ ν_{3}(n) + 2, & if n ≡ 0 (mod 13); \\ ν_{3}(n + 1) + 2, & if n ≡ 12 (mod 13); \\ 4, & if n ≡ 9 (mod 39); \\ ν_{3}(n + 17) + 4, & if n ≡ 22 (mod 39); \\ ν_{3}(n + 4) + 4, & if n ≡ 35 (mod 39). \end{cases}

2.1 The proof of Theorem 1

Assume k ≥ 1, n ≥ 3 and

T_{n} = m_{1}! ⋯ m_{k}!.

We may assume that 2 ≤ m_{1} ≤ ⋯ ≤ m_{k}. It is well-known that letting α be real root of x^{3} − x^{2} − x − 1 = 0, then α > 1.83 and T_{n} ≥ α^{n−2} holds for all n ≥ 1. Thus,

α^{n−2} ≤ T_{n} = m_{1}! ⋯ m_{k}! < m_{1}^{m_{1}} ⋯ m_{k}^{m_{k}},

so

n < 2 + \frac{m_{1} log m_{1} + ⋯ + m_{k} log m_{k}}{log(1.83)} .  (1)

Note that

ν_{2}(m!) = ⌊m/2⌋ + ⌊m/4⌋ + ⋯ ≥ m/2

holds for all m ≥ 2, except when m = 3, when ν_{2}(3!) = (3 − 1)/2 ≥ 3/3. Hence, the inequality ν_{2}(m!) ≥ m/3 holds for all m ≥ 2. Next, by Theorem 3, we see that

ν_{2}(T_{n}) ≤ max{2, ν_{2}(n) − 1, ν_{2}(n + 4) − 1, ν_{2}(n + 1) + 1, ν_{2}(n + 17) + 1}

≤ \frac{log(n + 17)}{log 2} + 1.

This gives

\frac{log(n + 17)}{log 2} + 1 ≥ ν_{2}(T_{n}) = ν_{2}(m_{1}!) + ⋯ + ν_{2}(m_{k}!).

Thus, putting

x := ν_{2}(m_{1}!) + ⋯ + ν_{2}(m_{k}!),

we have

n > 2^{x−1} − 17,  (2)

and since m_{i} ≤ 3ν_{2}(m_{i}!) for i = 1, …, k, we have

m_{1} log m_{1} + ⋯ + m_{k} log m_{k} < (m_{1} + ⋯ + m_{k}) log(m_{1} + ⋯ + m_{k})
≤ 3x log(3x),

so (1) yields

n < 2 + \frac{3x log(3x)}{log(1.83)}.  (3)

Combining (2) and (3), we get

2^{x−1} − 17 < 2 + \frac{3x log(3x)}{log(1.83)},

giving x ≤ 8. Since ν_{2}(11!) = 8, we conclude that either T_{n} = 11! and k = 1, or m_{k} ≤ 10, in which case P (T_{n}) ≤ 7, where P (m) is the largest prime factor of m. Since T_{n} = 11! is not possible, we conclude that P (T_{n}) ≤ 7. All Tribonacci numbers whose largest prime factor is at most 7 have been determined in [2] and they are T_{1} = T_{2} = 1, T_{2} = 2, T_{3} = 4, T_{5} = 7, T_{7} = 2^{3} ·3, T_{9} = 3^{4}, T_{12} = 2^{3} ·3^{2} ·7, T_{15} = 2^{6} ·7^{2}, and the only numbers from the previous list that are products of factorials correspond to n ∈ {1, 2, 3, 4, 7}.

3 The proof of Theorem 2

This is trickier, since the lower bounds on |T_{−n}| are quite weak. However, we can follow the arguments from [3] and [4]. Namely, we put Λ := {α, β, γ} for the set of roots of P (X) = X^{3} − X^{2} − X − 1. We assume β = α^{−1/2}e^{iθ} where θ ∈ (0, π) and γ = α^{−1/2}e^{−iθ}. So, β is the complex nonreal root of P (X) in the upper half-plane. Then

T_{n} = c_{α}α^{n} + c_{β}β^{n} + c_{γ}γ^{n} holds for all n ∈ ℤ.

Here

c_{λ} = \frac{λ}{P′(λ)} for λ ∈ Λ.

The Tribonacci sequence {T_{n}}_{n∈ℤ} is periodic modulo 2^{k} with period 2^{k+2} for all k ≥ 1. To see this, it is easier to work with

22T_{n} = (22c_{α})α^{n} + (22c_{β})β^{n} + (22c_{γ})γ^{n}.

The numbers c_{λ} are not algebraic integers, but 22c_{λ} are algebraic integers of minimal polynomial X^{3} − 22X − 242 for λ ∈ Λ. Since X^{3} − X^{2} − X − 1 divides X^{4} − 2X + 1, it follows that λ^{4} ≡ 1 (mod 2) for λ ∈ Λ. Here, for algebraic integers γ, δ and an integer m ≥ 1, we write γ ≡ δ (mod m) if (γ − δ)/m is an algebraic integer. By induction we get λ^{2^{k+1}} ≡ 1 (mod 2^{k}) for all k ≥ 1. In particular, for all n ∈ ℤ, we have

22T_{n+2^{k+1}} = ∑_{λ∈Λ}(22c_{λ})λ^{n+2^{k+1}} ≡ ∑_{λ∈Λ}(22c_{λ})λ^{n} ≡ 22T_{n} (mod 2^{k}).

The above congruence implies that T_{n+2^{k+1}} ≡ T_{n} (mod 2^{k−1}) holds for all k ≥ 2. Hence, {T_{n}}_{n∈ℤ} is periodic modulo 2^{k} with period 2^{k+2} for all k ≥ 1. In particular, the Marques– Lengyel formulas from Theorem 3 hold for all integers n, not only for the positive ones. Let us see why.

Assume n ≠ 0, 1, 4, 17, since for these values of b we have T_{−n} = 0, so the formula from Theorem 3 holds with both sides equal ∞. Let k be large (k ≥ n + 10). Then T_{−n} ≡ T_{2^{k}−n} (mod 2^{k−2}) and 2^{k} − n is positive. Unless −n ≡ 0, 1, 4, 17 (mod 16), the formulas from Theorem 3 show that ν_{2}(2^{k}−n) ∈ {0, 1, 2} and 16 | 2^{k}. It then follows that ν_{2}(T_{2^{k}−n}) = 0, 1, 2 and since T_{2^{k}−n} ≡ T_{−n} (mod 2^{k−2}), it follows that ν_{2}(T_{−n}) = ν_{2}(T_{2^{k}−n}). Hence, the formula from Theorem 3 holds for the residue classes for −n modulo 16 that are not one of 0, 1, 4, 17. For the rest of the residue classes, ν_{2}(T_{2^{k}−n}) = ν_{2}(2^{k} − n + a) + b for some a ∈ {0, 1, 4, 17} and b ∈ {−1, 1}. But

ν_{2}(2^{k} − n + a)) = ν_{2}(2^{k} − (n − a)) = ν_{2}(n − a) for large k since n − a ≠ 0.

Since T_{−n} ≡ T_{2^{k}−n} (mod 2^{k−2}) and ν_{2}(T_{−n}) = ν_{2}(T_{2^{k}−n}) = ν_{2}(−n + a) + b, the formula from Theorem 3 holds for −n that are congruent to one of {0, 1, 4, 17} modulo 16. Similar (and in fact easier) considerations modulo 13 · 3^{k} show that the sequence {T_{n}}_{n∈ℤ} is periodic modulo 3^{k+1} with period 13 · 3^{k} and that the formula from Theorem 4 holds for all integers n not only for the positive ones.

We next assume that n ≥ 18. Then [3, Inequality (2.3)] (also see [4, Inequality (4.2)]) shows that

T_{−n} > α^{n/2−1.2×10^{16} log n}.

The condition n ≥ 18 is needed since T_{−17} = 0. Thus, the analogue of inequality (1) when |T_{−n}| = m_{1}! ⋯ m_{k}! for n ≥ 18 is

n/2 − 1.2 × 10^{16} log n < \frac{m_{1} log m_{1} + ⋯ + m_{k} log m_{k}}{log(1.83)} .  (4)

Further, using that Theorem 3 holds for n ∈ ℤ, we get that

ν_{2}(T_{−n}) ≤ max{2, ν_{2}(n) − 1, ν_{2}(n − 4) − 1, ν_{2}(n − 1) + 3, ν_{2}(n − 17) + 3}

≤ \frac{log(n − 1)}{log 2} + 3,

so the analogue of inequality (2) is

n ≥ 2^{x−3} + 1.  (5)

The function y ↦ y/2 − 1.2 × 10^{16} log y is increasing for y > 2.4 × 10^{16}, so if x ≥ 58, then 2^{x−3} + 1 ≥ 2^{55} + 1 > 2.4 × 10^{16}, so

n/2 − 1.2 × 10^{16} log n ≥ 2^{x−4} + 0.5 − 1.2 × 10^{16}(x − 3) log 2.  (6)

We thus get

2^{x−4} + 0.5 − 1.2 × 10^{16}(x − 3) log 2 < \frac{3x log(3x)}{log(1.83)},

which gives x ≤ 62. Hence, x ≤ 62, so m_{1} + m_{2} + ⋯ + m_{k} ≤ 3x ≤ 186. Thus,

m_{1}! m_{2}! ⋯ m_{k}! | (m_{1} + ⋯ + m_{k})! | 186!.

Further, from (4) we get

n/2 − 1.2 × 10^{16} log n < \frac{3x log(3x)}{log(1.83)} < \frac{186 log 186}{log(1.83)},

so n < 10^{18}. We are ready to do some Baker-Davenport reduction. This has been explained and used in many places. For our application, we refer the reader to [4, Lemma 5.1] and [3, Eqs. (3.4), (3.5)]. We write

c_{β}β^{−n} + c_{γ}γ^{−n} = ±m_{1}! ⋯ m_{k}! − c_{α}α^{−n}.

Thus, assuming n > 6000, we get

|(−\frac{c_{γ}}{c_{β}} ) (\frac{β}{γ} )^{n} − 1| = \frac{| ± m_{1}! ⋯ m_{k}! − c_{α}α^{−n}|}{α^{n/2}} < \frac{186! + 1}{α^{n/2}} < \frac{1}{α^{n/4}} .

The last inequality holds for n > 6000. Writing β/γ = e^{2iθ} and also −c_{γ}/c_{β} = −e^{2iω} for some ω ∈ (0, 2π), we get

|e^{i(2nθ+π−2ω)} − 1| < \frac{1}{α^{n/4}} .

The argument from [3] ((3.2)–(3.4)) shows that if l := ⌊(2nθ +π −2ω)/π⌉, then the left-hand side above is at least

2 |n (\frac{2θ}{π}) − (l − 1) − \frac{2ω}{π} | .

Thus, we get

|n (\frac{2θ}{π}) − (l − 1) − \frac{2ω}{π} | < \frac{2}{α^{n/4}} .

The left-hand side above is nτ − m + μ, where τ = 2θ/π, μ = −2ω/π, m = l − 1 and the right-hand side above is of the form A/B^{k}, with the parameters A = 2, B = α, k = n/4. The continued fraction of τ starts as follows:

[1, 2, 1, 1, 2, 6, 1, 5, 1, 1, 1, 11, 25, 2, 21, 1, 2, 1, 5, 4, 60, 8, 2, 1, 2, 8, 2, 1, 1, 60,
1, 5, 3, 1, 4, 29, 2, 24, 19, 1, …]

We take M := 10^{18}, which is an upper bound on n. We take the 39th convergent p_{39}/q_{39} and with q := q_{39}, calculate ε := ∥qμ∥ − M∥qτ∥ > 0.4, and we get by the Baker–Davenport reduction method that

n/4 = k < \frac{log(Aq/ε)}{log B} < \frac{log(2q_{39}/0.4)}{log(1.83)},

which gives n ≤ 361, contradicting our assumption that n > 6000. So, n ≤ 6000.

Now inequality (5) gives x ≤ 16. Since ν_{2}(20!) = 17 > x, it follows that m_{k} ≤ 19. But we can do better. Assume that m_{k} ≥ 12. Then ν_{2}(T_{−n}) ≥ ν_{2}(12!) = 11 and ν_{3}(T_{−n}) ≥ ν_{3}(12!) ≥ 5. Theorems 3 and 4 show that n is congruent to one of 0, 1, 4, 17 modulo 2^{10} and also modulo 13 · 3. Solving the above 4^{2} possibilities with the Chinese remainder lemma we get that the only possibility for which n < 6000 is n ≡ 4096 (mod 2^{10} · 3 · 13), so n = 4096, but ν_{3}(T_{−4096}) = 4 (not 5). This shows that m_{k} ≤ 11.

Finally, let us note that ν_{3}(T_{−n}) ≤ 9. Indeed, if ν_{3}(T_{−n}) ≥ 10, then Theorem 4 shows that n ≡ 0, 1, 4, 17 (mod 13 · 3^{6}) and 13 · 3^{6} > 6000 (certainly n cannot be one of 0, 1, 4, 17 since then T_{−n} = 0). So,

m_{1}! ⋯ m_{k}! = 2^{a} · 3^{b} · 5^{c} · 7^{d} · 11^{e},

where a ≤ 16, b ≤ 9, c ≤ 5, d ≤ 4, e ≤ 2. To see the upper bounds on the exponents of the primes larger than 3 above, note that if c ≥ 6, then 5!^{6} | m_{1}! ⋯ m_{k}!, which makes ν_{2}(T_{−n}) ≥ 18, a contradiction. The rest are proved in the same way. We created the list of all the numbers of the above form and intersected it with the list of absolute values {|T_{−n}|}_{1≤n≤6000}, obtaining some values in the intersection with the largest index n = 33 for which |T_{−33}| = 2^{6} · 7^{2}. From here, we recovered the solutions n for which |T_{−n}| is a product of factorials namely T_{−2} = 1, T_{−3} = −1, T_{−5} = 2, T_{−7} = 1, T_{−8} = 2^{2}, T_{−9} = −2^{3}. This finishes the proof.

4 Acknowledgments

We thank the anonymous referee for a careful reading of the paper and for comments that improved the quality of our manuscript. F. L. worked on this paper during a visit to the Max Planck Institute for Software Systems in Saarbrücken, Germany in 2022. This author thanks Professor J. Ouaknine for the invitation and the MPI-SWS for hospitality and support.

References

[1] Y. Bilu, F. Luca, J. Nieuwveld, J. Ouaknine, and J. B. Worrell, On the p-adic zeros of the Tribonacci sequence, arxiv preprint arXiv:2210.16959 [math.NT], 2022. Available at

   https://arxiv.org/abs/2210.16959.

[2] J. J. Bravo and F. Luca, On the largest prime factor of the k-Fibonacci numbers, Int. J. Number Theory 9 (2013), 1351–1366.

[3] E. Bravo, C. A. Gómez, and F. Luca, Total multiplicity of the tribonacci sequence, Colloq. Math. 159 (2020), 71–76.

[4] E. Bravo, C. A. Gómez, B. Kafle, F. Luca, and A. Togbé, On a conjecture concerning the multiplicity of the tribonacci sequence, Colloq. Math. 159 (2020), 61–69.

[5] D. Marques and T. Lengyel, On the 2-adic order of Tribonacci numbers and the equation T_{n} = m!, J. Integer Sequences 17 (2014), Article 14.10.1.

2020 Mathematics Subject Classification: Primary 11B39; Secondary 11A07, 11B50, 11D61. Keywords: Tribonacci number, factorial, Baker–Davenport reduction method.

(Concerned with sequence \underline{A000073}.)

Received November 3 2022; revised versions received February 3 2023; February 18 2023. Published in Journal of Integer Sequences, February 18 2023.

Return to Journal of Integer Sequences home page.