\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
On Generalized Cullen and Woodall Numbers \\
\vskip .12in
That are Also Fibonacci Numbers
}
\vskip 1cm
\large
Diego Marques\\
Departamento de Matem\' atica\\
Universidade de Bras\' ilia\\
Bras\' ilia 70910-900 \\
Brazil\\
\href{mailto:diego@mat.unb.br}{\tt diego@mat.unb.br}\\
\end{center}
\vskip .2 in
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\N}{{\mathbb N}}
\def\noi {\noindent}
\def\Ker {{\rm Ker}}
\def\Im {{\rm Im}}
\def\a {\alpha}
\def\m {\mu}
\def\g {\gamma}
\def\p {\phi}
\def\B {\mathcal{B}}
\def\O {\mathcal{O}}
\def\N {\mathbb{N}}
\def\Z {\mathbb{Z}}
\def\Q {\mathbb{Q}}
\def\R {\mathbb{R}}
\def\RR {\mathcal{R}}
\def\QQ {\overline{\Q}}
\def\QQQ {\QQ}
\def\C {\mathbb{C}}
\def\cF {\mathcal{F}}
\def\cR {\mathcal{R}}
\def\e {\epsilon}
\def\d {\delta}
\def\g {\gamma}
\def\l {\lambda}
\def\dfrac {\displaystyle\frac }
\def\k {\kappa}
\begin{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\u anic\u a 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. A generalization of these sequences is defined by $C_{m,s}=ms^m+1$ and $W_{m,s}=ms^m-1$, for $s>1$. In this paper, we search for Fibonacci numbers belonging to these generalized Cullen and Woodall sequences.
\end{abstract}
\section{Introduction}\label{sec1}
A {\it Cullen number} is a number of the form $m2^m+1$ (denoted by $C_m$), where $m$ is a nonnegative integer. The first few terms of this sequence are
\[
1, 3, 9, 25, 65, 161, 385, 897, 2049, 4609, 10241, 22529,\ldots
\]
which is the OEIS \cite{oeis} sequence
\seqnum{A002064}.
(This sequence was introduced in 1905 by Father Cullen \cite{cul} and it was mentioned in the well-known book of Guy \cite[Section {\bf B20}]{guy}.) These numbers gained great interest in 1976, when Hooley \cite{hoo} showed that almost all Cullen numbers are composite. However, despite their
being very scarce, it is still
conjectured that there are infinitely many \textit{Cullen primes}. For instance, $C_{6679881}$ is a prime number with more than 2 millions of digits (PrimeGrid, August 2009).
In a similar way, a \textit{Woodall number} (also called \textit{Cullen number of the second kind}) is a positive integer of the form $m2^m-1$ (denoted by $W_m$). The first few terms of this sequence are
\[
1, 7, 23, 63, 159, 383, 895, 2047, 4607, 10239,\ldots
\]
which is the OEIS sequence \seqnum{A003261}. In a personal communication to Keller \cite[p.\ 1739]{new}, Suyama asserted that Hooley's method can be reformulated to show that it works for any sequence of numbers of the form $m2^{m+a} + b$ where $a$ and $b$ are integers. In particular, Woodall numbers are almost all composites. However, it is conjectured that the set of {\it Woodall primes} is infinite. We remark that $W_{3752948}$ is a prime number (PrimeGrid, December 2007).
These numbers can be generalized to the \textit{generalized Cullen and Woodall numbers} which are numbers of the form
\begin{center}
$C_{m,s}=ms^m+1$ and $W_{m,s}=ms^m-1$,
\end{center}
where $m\geq 1$ and $s\geq 2$. Clearly, one has that $C_{m,2}=C_m$ and $W_{m,2}=W_m$, for all $m\geq 1$. For simplicity, we call $C_{m,s}$ and $W_{m,s}$ an \textit{$s$-Cullen number} and an \textit{$s$-Woodall number}, respectively. Also, an $s$-Cullen or $s$-Woodal number is said to be {\it trivial} if it has the form $s+1$ or $s-1$, respectively, or equivalently when its first index is equal to $1$. This family was introduced by Dubner \cite{dub} and is one of the main sources for prime number ``hunters". 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. In regards to these numbers, we refer to \cite{pt,uber,new} for primality results and \cite{mdc} for their greatest common divisor. The problem of finding Cullen and Woodall numbers belonging to other known sequences has attracted much attention in the last two decades. We cite \cite{pseudo} for pseudoprime Cullen and Woodall numbers, and \cite{bar} for Cullen numbers which are both Riesel and Sierpi\' nski numbers.
In 2003, Luca and St\u anic\u a \cite[Theorem 3]{LS} proved that the largest Fibonacci number in the Cullen sequence is $F_4=3=1\cdot 2^1+1$ and that $F_1=F_2=1=1\cdot 2^1-1$ are the largest Fibonacci numbers in the Woodall sequence.
Note that these numbers are trivial Cullen and Woodall numbers (in the previous sense, i.e., $m=1$).
In this paper, we search for Fibonacci numbers among $s$-Cullen numbers and $s$-Woodall numbers, for $s>1$. Our main result is the following
\begin{theorem}\label{main1}
Let $s$ be a positive integer. If $(m,n,\ell)$ is an integer solution of
\begin{equation}\label{Main}
F_n=ms^{m}+\ell,
\end{equation}
where $\ell\in \{-1,1\}$ and $m,n>0$, then
\begin{equation}\label{ine}
m<(6.2 + 1.9P(s))\log (3.1+P(s)),
\end{equation}
and
\[
n<\dfrac{\log ((6.2 + 1.9P(s))\log (3.1+P(s))s^{(6.2 + 1.9P(s))\log (3.1+P(s))}+1)}{\log \alpha}+2,
\]
where $P(s)$ denotes the largest prime factor of $s$ and $\alpha=(1+\sqrt{5})/2$.
\end{theorem}
In particular, the above theorem ensures that for any given $s\geq 2$, there are only finitely many Fibonacci numbers which are also $s$-Cullen numbers or $s$-Woodall numbers and they are effectively computable.
We should recall that $\nu_p(r)$ denotes the $p$-adic order (or valuation) of $r$ which is the exponent of the highest power of a prime $p$ which divides $r$. Also, the {\it order (\mbox{or} rank) of appearance} of $n$ in the Fibonacci sequence, denoted by $z(n)$, is defined to be the smallest positive integer $k$, such that $n\mid F_k$ (some authors call it \textit{order of apparition}, or \textit{Fibonacci entry point}). We refer the reader to \cite{lucas,d1,d20,d21,d22} for some results about this function. Let $p$ be a prime number and set $e(p):=\nu_p(F_{z(p)})$. By evaluating $e(p)$, for primes $p<30$, one can see that $e(p)=1$. In fact, $e(p)=1$ for all primes $p<2.8\cdot 10^{16}$ (PrimeGrid, March 2014). Moreover, the assertion $e(p)=1$ for all prime $p$ is equivalent to $z(p)\neq z(p^2)$, for all primes $p$ (this is related to Wall's question \cite{wall}). This question raised interest in 1992, when Sun and Sun \cite{SS} proved (in an equivalent form) that $e(p)=1$ for all primes $p$, implies the first case of
Fermat's ``last theorem''.
In view of the previous discussion, it seems reasonable to consider problems involving primes with $e(p)=1$ (because of their abundance). Our next result deals with this kind of primes.
\begin{theorem}\label{main2}
There is no integer solution $(m,n,s,\ell)$ for Eq.\ (\ref{Main}) with $n>0$, $m>1$, $\ell\in \{-1,1\}$ and $s>1$ such that $e(p)=1$ for all prime factor $p$ of $s$.
\end{theorem}
In particular, the only solutions of Eq.\ (\ref{Main}), with the previous conditions, occur when $m=1$ and have the form
\[
(m,n,s,\ell)=(1,n,F_n-\ell,\ell).
\]
An immediate consequence of Theorem \ref{main2} and the fact that $e(p)=1$ for all primes $p<2.8\cdot 10^{16}$ is the following
\begin{corollary}
There is no Fibonacci number that is also a nontrivial $s$-Cullen number or $s$-Woodall number when the set of prime divisors of $s$ is contained in
\[
\{2,3,5,7,11,\ldots,27999999999999971, 27999999999999991\}.
\]
This is the set of the first $759997990476073$ prime numbers.
\end{corollary}
Here is an outline of the paper. In Section \ref{aux}, we recall some facts which will be useful in the proofs of our theorems, such as the result concerning the $p$-adic order of $F_n$ and factorizations of the form $F_n\pm 1=F_aL_b$, with $|a-b|\leq 2$. In the last section, we combine these mentioned tools, the fact that a common divisor of $F_a$ and $L_b$ is small and a lower bound for Fibonacci and Lucas numbers, to get an inequality of the form $m16$ (however, for our purpose it suffices to consider $m>4$).
We rewrite Eq.\ (\ref{Main}) as $F_n-\ell=ms^{m}$. Since $\ell\in \{-1,1\}$, then Lemma \ref{l2} gives $F_aL_b=ms^{m}$, where $2a,2b\in \{n\pm 2,n\pm 1\}$ and $|a-b|\in \{1,2\}$. Observe that in this case $\gcd(F_a,L_b)=1$ or $3$ (Lemma \ref{l1} (a)).
\medskip
\indent
{\bf Case 1.} If $s\not\equiv 0\pmod 3$. Since $\gcd(F_a,L_b)=1$ or $3$ and $3\nmid s$, then, without loss of any generality, we can write $s=p_1^{a_1}\cdots p_k^{a_k}$, with $a_i\geq 0$, such that $p_1^{a_1}\cdots p_t^{a_t}$ divides $F_a$ and $p_{t+1}^{a_{t+1}}\cdots p_k^{a_k}$ divides $L_{b}$, where $p_1,\ldots,p_k$ are distinct primes. Thus $\nu_{p_i}(F_{a})\geq a_im$, for $i\in [1,t]$ and $\nu_{p_j}(L_b)\geq a_jm$, for $j\in [t+1,k]$, and on the other hand, Lemmas \ref{l3} and \ref{l4} imply
\[
\nu_{p_i}(F_{a})\leq \nu_{p_i}(a)+(1-\delta_{{p_i},5}+\delta_{p_i,2})e({p_i})
\]
and
\[
\nu_{p_j}(L_b)\leq \max\{\nu_{p_j}(b)+e(p_j),2\},
\]
where $\delta_{r,s}$ denotes the usual Kronecker delta. Since $1-\delta_{{p_i},5}+\delta_{p_i,2}\leq 2$ and $m>2$, then
\begin{center}
$\nu_{p_i}(F_{a})\leq \nu_{p_i}(a)+2e({p_i})$ and $\nu_{p_j}(L_{b})\leq \nu_{p_j}(b)+e({p_j})$.
\end{center}
Thus one obtains that $\nu_{p_i}(a)\geq a_im-2e({p_i})$, for all $i\in [1,t]$ and $\nu_{p_j}(b)\geq a_jm-e(p_j)$, for all $j\in [t+1,k]$. Since $p_1,\ldots,p_k$ are pairwise coprime, we have $a\geq p_1^{a_1m-2e(p_1)}\cdots p_k^{a_km-2e(p_t)}$ and $b\geq p_{t+1}^{a_{t+1}m-e(p_{t+1})}\cdots p_{k}^{a_{k}m-e(p_{k})}$. Hence $F_aL_b=ms^{m}$ together with the estimates in Lemma \ref{l1} (d) yields
\begin{eqnarray*}
mp_1^{ma_1}\cdots p_k^{ma_k} & \geq & \alpha^{a+b-3}\\
& > & \alpha^{\prod_{i=1}^t p_i^{ma_i-2e(p_i)}+\prod_{i=t+1}^k p_i^{ma_i-2e(p_i)}-3},
\end{eqnarray*}
where we used the inequality
$ma_i-e(p_i)>ma_i-2e(p_i)$.
Note that we may suppose that $ma_i>2e(p_i)$, for all $i\in [1,k]$ (otherwise, we would have $m\leq 2e(p_i)$, for some $i$ and Theorem \ref{main1} is proved). Also $p_i\geq 2$, for all $i\in [1,k]$ and then
\[
\displaystyle\prod_{i=1}^t p_i^{ma_i-2e(p_i)}+\displaystyle\prod_{i=t+1}^k p_i^{ma_i-2e(p_i)}\geq \displaystyle\sum_{i=1}^kp_i^{ma_i-2e(p_i)}.
\]
Thus we have
\[
4.3mp_1^{ma_1}\cdots p_k^{ma_k} > \alpha^{p_1^{ma_1-2e(p_1)}}\cdots \alpha^{p_k^{ma_k-2e(p_k)}},
\]
where we have used that $\alpha^3<4.3$. But for $m>4$, it holds that $4.3m<2^m\leq p_1^{m}$ and so
\[
p_1^{m(a_1+1)}\cdots p_k^{ma_k} > \alpha^{p_1^{ma_1-2e(p_1)}}\cdots \alpha^{p_k^{ma_k-2e(p_k)}}.
\]
If the inequality $p_i^{ma_i-2e(p_i)}>m(a_i+1)(\log p_i)/\log \alpha$ holds for all $i\in [1,k]$, we arrive at the following absurdity
\[
p_1^{m(a_1+1)}\cdots p_k^{ma_k}>\alpha^{p_1^{ma_1-2e(p_1)}}\cdots \alpha^{p_k^{ma_k-2e(p_k)}}>p_1^{m(a_1+1)}\cdots p_k^{m(a_k+1)}.
\]
Thus, there exists $i\in [1,k]$, such that $p_i^{ma_i-2e(p_i)}\leq m(a_i+1)(\log p_i)/\log \alpha$. Now, by applying the $\log$ function in the previous inequality together with a straightforward calculation, we obtain
\[
\dfrac{m}{\log m}\leq \dfrac{1}{\log p_i}+\dfrac{\log (a_i+1)}{a_i\log m\log p_i}+\dfrac{\log \left(\frac{\log p_i}{\log \alpha}\right)}{a_i\log m\log p_i}+\dfrac{2e(p_i)}{a_i\log m}.
\]
Note that $a_i\geq 1$, $\log p_i\geq \log 2>0.69$ and $\log m\geq \log 3>1.09$. Also, the functions $x\mapsto (\log(x+1))/x$ and $x\mapsto (\log(\log x/\log \alpha))/(\log x)$ are nonincreasing for $x\geq 1$ and $x\geq 4$, respectively, then $(\log (a_i+1))/a_i\leq \log 2$ and $(\log(\log p_i/\log \alpha))/(\log p_i)<0.77$. Therefore,
\[
\dfrac{m}{\log m}<3.1+1.9e(p_i).
\]
Since the function $x\mapsto x/\log x$ is increasing for $x>e$, it is a simple matter to prove that, for $A>e$,
\begin{equation}\label{tutu}
\dfrac{x}{\log x}e$, we have that
\begin{equation}\label{key}
m<(6.2+3.8e(p_i))\log (3.1+1.9e(p_i)).
\end{equation}
Since $p_i\leq P(s)$, then in order to get the desired inequality in (\ref{ine}), it suffices to prove that $e(p)\leq p/2$ for all primes $p$. Clearly, the inequality holds for $p=2$, so we may suppose $p\geq 3$. Since $p^{e(p)}\mid F_{z(p)}$, we have $p^{e(p)}\leq F_{z(p)}$. Suppose, towards a contradiction, that $e(p)> p/2$, then we use Lemma \ref{l1} (d) and (e) to obtain
\[
p^{p/2}< p^{e(p)}\leq F_{z(p)}\leq \alpha^{z(p)-1}\leq \alpha^p.
\]
This yields that $p< \alpha^2<2.619$ which is impossible, since $p\geq 3$. Thus $e(p)\leq p/2$ \footnote{In fact, the same proof gives the sharper bound $e(p)\leq (p\log \alpha)/\log p$. This bound together with the squeeze theorem
gives $\displaystyle\lim_{p\to \infty}e(p)/p=0.$}. Thus
\[
m<(6.2 + 1.9P(s))\log (3.1+P(s)),
\]
where we used that $P(s)\geq p_i$, for all $i\in [1,k]$.
Now, we use Lemma \ref{l1} (d) to get $\alpha^{n-2}\leq F_n\leq ms^{m}+1$ and a straightforward calculation yields
\[
n<\dfrac{\log ((6.2 + 1.9P(s))\log (3.1+P(s))s^{(6.2 + 1.9P(s))\log (3.1+P(s))}+1)}{\log \alpha}+2,
\]
where we used the upper bound for $m$ in terms of $s$.
\medskip
\indent
{\bf Case 2.} If $s\equiv 0\pmod 3$. We can proceed as before unless $\gcd(F_a,L_{b})=3$. In this case, for some suitable choice of $\e_1,\e_2\in \{0,1\}$, with $\e_1+\e_2=1$, we have
\[
\dfrac{F_a}{3^{\e_1}}\cdot \dfrac{L_b}{3^{\e_2}}=\dfrac{ms^m}{3}
\]
and $\gcd(F_a/3^{\e_1},L_b/3^{\e_2})=1$. From this point on the proof proceeds along the same lines as the proof of previous case. \qed
\subsection{The proof of Theorem \ref{main2}}
Let $(m,n,s,\ell)$ be a solution of Eq.\ (\ref{Main}) satisfying the conditions in the statement of Theorem \ref{main2} and suppose that $m\leq 16$. Note that $F_n=4s^4\pm 1$ can be rewritten as $F_n=(2s^2)^2\pm 1$, but Bugeaud et al. \cite[Theorem 2]{bugeaud} listed all solutions of the Diophantine equation $F_n\pm 1=y^t$. A quick inspection in their list gives $y=1,2$ or $3$, but none of these values have the form $2s^2$, for $s>1$. So, there is no solution for Eq.\ (\ref{Main}) when $m=4$.
So, we wish to solve the equation $F_n=ms^m\pm 1$, when $m\in [2,16]\backslash \{4\}$. As previously done, let us rewrite it as $F_aL_b=ms^m$. Note that $m$ has at most $2$ distinct prime factors and they belong to $\{2,3,5,7,11,13\}$. Since $\gcd(F_a,L_b)=1$ or $3$, we can deduce that
\begin{equation}\label{small}
F_a=p_1^{\a_1}p_2^{\a_2}p_3^{\a_3}(s_1^{r})^p,
\end{equation}
where $p_1,p_2,p_3,p$ are primes less than $17$, $\a_1,\a_2,\a_3\in \{0,1,2,3,4\},\ s_1\mid s$ and $m=pr$.
However, in 2007, by combining some deep tools in number theory, Bugeaud, Luca, Mignotte and Siksek \cite[Theorem 4 for $m=1$]{siksek}, found (in particular) all solutions of the Diophantine equation
\[
F_t=2^{x_1}\cdot 3^{x_2}\cdots 541^{x_{100}}y^p,
\]
where $x_i\geq 0$ and $p$ is a prime number. More precisely, they proved that in this case, one has
\begin{equation}\label{pos}
t\in [1,16]\cup [19,22]\cup \{24,26,27,28,30,36,42,44\}.
\end{equation}
In particular, $t\leq 44$.
Note that Eq.\ (\ref{small}) is a particular case already treated by Theorem 4 of \cite{siksek}. However, for convenience of the reader, we describe in a few words how these calculations can be performed. First, if $m=2$, then we have the equation $F_a=2^{\a_1}\cdot 3^{\a_2}s_1^2$ and after a quick inspection in (\ref{pos}), one can see that possible values for $a$ do not give any solution for Eq.\ (\ref{Main}). In the case of $m\geq 3$, we use that $a\leq 44$ together with $a\geq (n-2)/2$ to get $n\leq 90$ and so
\[
3s^3-1\leq ms^m+\ell=F_n\leq F_{90}=2880067194370816120.
\]
Therefore $s\leq 986492$. Now by using {\it Mathematica} \cite{math}, one deduces that the Diophantine equation $F_n=ms^m+\ell$, for $2\leq n\leq 90$, $3\leq m\leq 16$, $\ell\in \{-1,1\}$ and $2\leq s\leq 986492$, has no any solution.
Let us suppose that $m>16$. We remark that in order to get the inequality (\ref{key}) in the proof of Theorem \ref{main1}, we only assume that $m>4$. Thus, we have
\[
m<(6.2+3.8e(p_i))\log (3.1+1.9e(p_i)),
\]
where $p_i$ is a prime factor of $s$. However, by hypothesis, all prime factors $p$ of $s$ satisfy $e(p)=1$. In particular, $e(p_i)=1$ and so we have the following absurdity: $16