Fibonacci s-Cullen and s-Woodall Numbers

Diego Marques Departamento de Matemática Universidade de Brasília Brasília, Brazil

                   diego@mat.unb.br

Ana Paula Chaves Instituto de Matemática e Estatística Universidade Federal de Goiás Goiás, Brazil

                    apchaves@ufg.br

Abstract

The m-th Cullen number C_{m} is a number of the form m2^{m} + 1 and the m-th Woodall number W_{m} has the form m2^{m} − 1. In 2003, Luca and Stănică proved that the largest Fibonacci number in the Cullen sequence is F_{4} = 3 and that F_{1} = F_{2} = 1 are the largest Fibonacci numbers in the Woodall sequence. Very recently, the second author proved that, for any given s > 1, the equation F_{n} = ms^{m} ± 1 has only finitely many solutions, and they are effectively computable. In this note, we shall provide the explicit form of the possible solutions.

1 Introduction

A Cullen number is a number of the form m2^{m}+1 (denoted by C_{m}), where m is a nonnegative integer. This sequence was introduced in 1905 by Father J. Cullen [2] and it was mentioned in the well-known book of Guy [5, Section B20]. These numbers gained great interest in 1976, when Hooley [7] showed that almost all Cullen numbers are composite. However, despite being very scarce, it is still conjectured that there are infinitely many Cullen primes.

In a similar way, a Woodall number (also called Cullen number of the second kind) is a positive integer of the form m2^{m} − 1 (denoted by W_{m}). It is also known that almost all Woodall numbers are composite. However, it is also conjectured that the set of Woodall primes is infinite.

These numbers can be generalized to the s-Cullen and s-Woodall numbers which are numbers of the form

C_{m,s} = ms^{m} + 1 and W_{m,s} = ms^{m} − 1,

where m ≥ 1 and s ≥ 2. This family was introduced by Dubner [3]. A prime of the form C_{m,s} is C_{139948,151} an integer with 304949 digits.

Many authors have searched for special properties of Cullen and Woodall numbers and their generalizations. We refer the reader to [4, 6, 9, 10] for classical and recent results on this subject.

In 2003, Luca and Stănică [8, Theorem 3] proved that the largest Fibonacci number in the Cullen sequence is F_{4} = 3 = 1 · 2^{1} + 1 and that F_{1} = F_{2} = 1 = 1 · 2^{1} − 1 are the largest Fibonacci numbers in the Woodall sequence.

Recall that ν_{p}(r) denotes the p-adic order of r, which is the exponent of the highest power of a prime p which divides r. Also, the order (or rank) of appearance of n in the Fibonacci sequence, denoted by z(n), is defined as the smallest positive integer k, such that n | F_{k} (for results on this function, see [13] and references therein). Let p be a prime number and set e(p) := ν_{p}(F_{z(p)}).

Very recently, Marques [11] proved that if the equation

F_{n} = ms^{m} + ℓ  (1)

has solution, with m > 1 and ℓ ∈ {±1}, then m < (6.2 + 1.9e(p)) log(3.1 + e(p)), for some prime factor p of s. This together with the fact that e(p) = 1 for all prime p < 2.8 · 10^{16} (PrimeGrid, March 2014) implies that there is no Fibonacci number that is also a nontrivial (i.e., m > 1) s-Cullen number or s-Woodall number when the set of prime divisors of s is contained in {2, 3, 5, …, 27999999999999991}. This is the set of the first 759997990476073 prime numbers.

In particular, the previous result ensures that for any given s ≥ 2, there are only finitely many Fibonacci numbers which are also s-Cullen numbers or s-Woodall numbers and they are effectively computable.

In this note, we shall invoke the primitive divisor theorem to provide explicitly the possible values of m satisfying Eq. (1). More precisely,

Theorem 1. Let s > 1 be an integer. Let (n, m, ℓ) be a solution of the Diophantine equation (1) with n, m > 1 and ℓ ∈ {−1, 1}. Then m = e(p)/ν_{p}(s), for some prime factor p of s.

In particular, we have that m ≤ e(p) for some prime factor p of s. Also, we can deduce [11, Corollary 3] from the above theorem. In fact, for all p < 2.8 · 10^{16} we have e(p) = 1 and then if (n, m, ℓ) is a solution, with m > 1, we would have the contradiction that 1 < m = e(p)/ν_{p}(s) = 1/ν_{p}(s) for some p dividing s.

2 The proof

Suppose that n ≤ 27. Then max{2s^{2} − 1, m2^{m} − 1} ≤ ms^{m} + ℓ = F_{n} ≤ F_{27} = 196418 yields s ≤ 313 and m ≤ 13. For this, we prepare a simple Mathematica program which, in a few seconds, does not return any solution with m > 1.

So we may suppose that n ≥ 28. We rewrite Eq. (1) as F_{n} − ℓ = ms^{m}. It is well-known that F_{n} ± 1 = F_{a}L_{b}, where 2a, 2b ∈ {n ± 2, n ± 1}. (This factorization depends on the class of n modulo 4. See [12, (3)] for more details.) Then the main equation becomes

F_{a}L_{b} = ms^{m},

where 2a, 2b ∈ {n ± 2, n ± 1} and |a − b| ∈ {1, 2}. Since a − b ∈ {±1, ±2}, then gcd(a, b) ∈ {1, 2} and then gcd(F_{a}, L_{b}) = 1, 2 or 3. Therefore, we have F_{a} = m_{1}s_{1}^{m} and L_{b} = m_{2}s_{2}^{m}, where m_{1}m_{2} = m, s_{1}s_{2} = s and gcd(m_{1}, m_{2}), gcd(s_{1}, s_{2}) ∈ {1, 2, 3}. We claim that s_{1} > 1. Suppose, to get a contradiction, that s_{1} = 1, then F_{a} = m_{1} and L_{b} = m_{2}s^{m}. Since 2a − 4 ≥ n − 6 ≥ (n + 8)/2 ≥ b + 3, we arrive at the following contradiction:

m^{2} ≥ m_{1}^{2} = F_{a}^{2} ≥ α^{2a−4} ≥ α^{b+3} ≥ 2L_{b} = 2m_{2}s^{m} ≥ 2^{m+1} > m^{2},

where α = (1 + \sqrt{5})/2. Here, we used that F_{j} ≥ α^{j−2} and L_{j} ≤ α^{j+1}. Thus s_{1} > 1. Since a ≥ (n − 2)/2 ≥ 13, then by the primitive divisor theorem (see [1]), there exists a primitive divisor p of F_{a} (i.e., p | F_{a} and p ∤ F_{1} ⋯ F_{a−1}). We also have that p ≡ ±1 (mod a). In particular, p ≥ a − 1. Thus p | F_{a} = m_{1}s_{1}^{m}. Suppose that p | m_{1}. In this case, one has that a − 1 ≤ p ≤ m_{1} ≤ m. On the other hand, we get

2^{m} ≤ m_{1}s_{1}^{m} = F_{a} ≤ α^{a−1} < 2^{a−1}.

Thus m < a − 1 which gives a contradiction. Therefore p ∤ m_{1} and consequently p | s_{1}. This yields ν_{p}(F_{a}) = mν_{p}(s_{1}) = mν_{p}(s) (because p > 3, s = s_{1}s_{2} and gcd(s_{1}, s_{2}) ≤ 3). On the other hand, z(p) = a and so ν_{p}(F_{z(p)}) = ν_{p}(F_{a}) = mν_{p}(s) as desired.

3 Acknowledgements

The first author is grateful to FAP-DF and CNPq for financial support. The authors wish to thank the editor and the referee for their helpful comments.

References

[1] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n} ± β^{n}. Ann. of Math. 15 (1913), 30–70.

[2] J. Cullen, Question 15897. Educ. Times, 534 (1905).

[3] H. Dubner, Generalized Cullen numbers. J. Recreat. Math., 21 (1989), 190–194.

[4] J. M. Grau and A. M. Oller-Marcén, An Õ(log^{2}(N)) time primality test for generalized Cullen numbers. Math. Comp. 80 (2011), 2315–2323.

[5] R. Guy, Unsolved Problems in Number Theory. 2nd ed., Springer-Verlag, 1994.

[6] F. Heppner, Über Primzahlen der Form n2^{n} +1 bzw. p2^{p} +1. Monatsh. Math. 85 (1978), 99–103.

[7] C. Hooley, Applications of the Sieve Methods to the Theory of Numbers. Cambridge University Press, Cambridge, 1976.

[8] F. Luca and P. Stănică, Cullen numbers in binary recurrent sequences, in Applications of Fibonacci Numbers, vol. 10, Kluwer Academic Publishers, 2004, pp. 167–175.

[9] F. Luca, On the greatest common divisor of two Cullen numbers. Abh. Math. Sem. Univ. Hamburg 73 (2003), 253–270.

[10] F. Luca and I. Shparlinski, Pseudoprime Cullen and Woodall numbers. Colloq. Math. 107 (2007), 35–43.

[11] D. Marques, On generalized Cullen and Woodall numbers which are also Fibonacci numbers. J. Integer Sequences, 17 (2014), Article 14.9.4.

[12] D. Marques, The Fibonacci version of the Brocard-Ramanujan Diophantine equation. Port. Math. 68 (2011), 185–189.

[13] D. Marques, Sharper upper bounds for the order of appearance in the Fibonacci sequence. Fibonacci Quart. 50 (2013), 233–238.

2010 Mathematics Subject Classification: Primary 11B39. Keywords: Fibonacci number, Cullen number.

(Concerned with sequences \underline{A000045} and \underline{A002064}.)

Received October 11 2014; revised version received December 24 2015. Published in Journal of Integer Sequences, January 6 2015.

Return to Journal of Integer Sequences home page.