\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}}} \def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}} \newcommand{\R}{{\mathbb R}} \newcommand{\Q}{{\mathbb Q}} \newcommand{\C}{{\mathbb C}} \newcommand{\N}{{\mathbb N}} \DeclareMathOperator{\Ker}{Ker} \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{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 Tribonacci Numbers and the \\ \vskip .11in Brocard-Ramanujan Equation } \vskip 1cm \large Vin\' icius Fac\' o and Diego Marques \\ Departamento de Matem\' atica\\ Universidade de Bras\' ilia\\ Bras\' ilia 70910-900 \\ Brazil\\ \href{mailto:vinicius@mat.unb.br}{\tt vinicius@mat.unb.br}\\ \href{mailto:diego@mat.unb.br}{\tt diego@mat.unb.br}\\ \end{center} \vskip .2 in \begin{abstract} Let $(T_n)_{n \geq 0}$ be the Tribonacci sequence defined by the recurrence $T_{n+2}=T_{n+1}+T_n+T_{n-1}$, with $T_0=0$ and $T_1=T_2=1$. In this short note, we prove that there are no integer solutions $(u,m)$ to the Brocard-Ramanujan equation $m!+1=u^2$ where $u$ is a Tribonacci number. \end{abstract} \section{Introduction} In the past few years, several authors have considered Diophantine equations involving factorial numbers. For instance, Erd\H{o}s and Selfridge \cite{erdos} proved that $n!$ is a perfect power only when $n=1$. However, the most famous among such equations was posed by Brocard \cite{broc} in 1876 and independently by Ramanujan (\cite{ram}, \cite[p.\ 327]{ram2}) in 1913. The Diophantine equation \begin{equation}\label{1} m!+1=u^2 \end{equation} is now known as {\it Brocard-Ramanujan Diophantine equation}. It is a simple matter to find the three known solutions, namely $m=4,\ 5$ and $7$. Recently, Berndt and Galway \cite{berndt} showed that there are no further solutions with $m \leq 10^9$. An interesting contribution to the problem is due to Overholt \cite{over}, who showed that the equation \eqref{1} has only finitely many solutions if we assume a weak version of the abc conjecture. However, the Brocard-Ramanujan equation is still an open problem. Let $(F_n)_{n\geq 0}$ be the \textit{Fibonacci sequence} (sequence \seqnum{A000045} in the OEIS \cite{oeis}) given by $F_0=0,\ F_1=1$ and $F_{n+2}=F_{n+1}+F_n$, for $n\geq 0$. A number of mathematicians have been interested in Diophantine equations that involve both factorial and Fibonacci numbers. For example, Grossman and Luca \cite{gross} showed that if $k$ is fixed, then there are only finitely many positive integers $n$ such that \[ F_n=m_1!+m_2!+\cdots +m_k! \] holds for some positive integers $m_1,\ldots,m_k$. Also, all the solutions for the case $k\leq 2$ were determined. Later, Bollman, Hern\' andez and Luca \cite{luca3} solved the case $k=3$. In a recent paper, Luca and Siksek \cite{siksek} found all factorials expressible as the sum of at least three Fibonacci numbers. In 1999, Luca \cite{luca} proved that $F_n$ is a product of factorials only when $n=1,2,3,6$ and $12$. Also, Luca and St\u anic\u a \cite{stanica} showed that the largest product of distinct Fibonacci numbers which is a product of factorials is $F_1F_2F_3F_4F_5F_6F_8F_{10}F_{12}=11!$. In 2012, Marques \cite{notes} proved that $(m,u)=(4,5)$ is the only solution of Eq.~(\ref{1}) where $u$ is a Fibonacci number. His proof depends on the primitive divisor theorem together with factorizations formulas for $F_n\pm 1$. Among the several generalizations of Fibonacci numbers, one of the best known is the {\it Tribonacci} sequence $(T_n)_{n \geq 0}$ (sequence \seqnum{A000073} in the OEIS). This is defined by the recurrence $T_{n+1}=T_{n}+T_{n-1}+T_{n-2}$, with initial values $T_0=0$ and $T_1=T_2=1$. The first few terms of this sequence are \[ 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705. \] Tribonacci numbers have a long history. They were first studied in 1914 by Agronomof \cite{rf1} and subsequently by many others. The name Tribonacci was coined in 1963 by Feinberg \cite{rf2}. Here, we are interested in solutions $(m,u)$ of the Brocard-Ramanujan equation where $u$ is a Tribonacci number. We point out that in this we have neither a primitive divisor theorem for $T_n$ nor a factorization formula for $T_n\pm 1$. More precisely, we shall prove the following theorem. \begin{theorem}\label{thm1} There is no solution $(m,u)$ for the Brocard-Ramanujan equation \eqref{1}, where $u$ is a Tribonacci number. \end{theorem} The idea behind the proof is as follows. The equation we are interested in solving is $m! = (T_n-1)(T_n+1)$. The $2$-adic valuation of $m!$ is $m + O(\log m)$. We show that the $2$-adic valuation of $(T_n-1)(T_n+1)$ is $\lessapprox 8 \log n/\log 2$. Thus $m \lessapprox 8 \log n/\log 2$. This forces $m!$ to be smaller than $(T_n-1)(T_n+1)$, for $m$ and $n$ sufficiently large, which allows us to complete the proof. \section{The proof of Theorem \ref{thm1}}\label{auxiliary} \subsection{A key lemma} The $p$-adic order, $\nu_p(r)$, of $r$ is the exponent of the highest power of a prime $p$ which divides $r$. The $p$-adic order of a Fibonacci number was completely characterized by Lengyel \cite{order}. Also, very recently the $2$-adic order of Tribonacci numbers was made explicit by Lengyel and Marques \cite{tamas}. Here, we shall prove the following key result which will play an important role in the proof of Theorem \ref{thm1}. \begin{lemma}\label{key} We have \begin{displaymath} \nu_2(T_n+1) = \begin{cases} 15, & \text{if $n=61$;}\\ 0, & \text{if $n\equiv \modd{0,3} {4}$;}\\ 1, & \text{if $n\equiv \modd{1, 2, 6} {8}$;}\\ 3, & \text{if $n\equiv \modd{5} {16}$;}\\ \nu_2((n+3)^2)-3, & \text{if $n\equiv \modd{13,29,45} {64}$;}\\ \nu_2((n-61)(n+3))-3, & \text{if $n > 61$ and $n\equiv \modd{61} {64}$}. \end{cases} \end{displaymath} and, for $n\geq 5$, \begin{displaymath} \nu_2(T_n-1) = \begin{cases} 0, & \text{if $n\equiv \modd{0,3} {4}$;}\\ 1, & \mbox{if $n\equiv \modd{5} {8}$;}\\ \nu_2(n+2)-1, & \text{if $n\equiv \modd{6} {8}$;}\\ \nu_2(n-2)-1, & \text{if $n\equiv \modd{2} {8}$;}\\ \nu_2((n-1)(n+7))-3, & \text{if $n\equiv \modd{1} {8}$.} \end{cases} \end{displaymath} \end{lemma} \bigskip \noindent {\bf The case $T_n-1$:} First, note that Lengyel and Marques \cite{tamas} proved that $T_n - 1$ is odd for every $n \equiv 0,3$ (mod $4$), which proves the first case. Now, note that, in order to prove the second case, it suffices to prove that $T_n \equiv 3$ (mod $4$). In this case, we have $n= 8k + 5$, with $k \geq 0$. Then we proceed on induction on $k$. For $k=0$, it follows directly, since $T_5 - 1 = 7 - 1 = 6 = 2 \cdot 3$. So, we suppose that $T_{8k + 5} \equiv 3$ (mod $4$). Using the sum formula for $T_n$ (proved by Feng \cite{feng}), we have that \begin{eqnarray*} T_{8(k+1) + 5} & = & T_{(8k+5) + 8} \\ & = & T_6 T_{8k+5} + (T_6 + T_5) T_{8k+ 6} + T_7 T_{8k+7} \\ & = & 13 T_{8k+5} + 20 T_{8k+6} + 24 T_{8k+7} \\ & \equiv & 3 \pmod{4}. \end{eqnarray*} In the third case, for $t \geq 6$ and $ s \geq 1$ odd, we write $n = 2^{t-3}s + 2$. Now, by a Lengyel and Marques result \cite[Lemma 3.1]{tamas}, we have that \begin{eqnarray*} T_{2^{t-3}s + 2} & = & T_{2^{t-3}s + 1} + T_{2^{t-3}s } + T_{2^{t-3}s -1} \\ & \equiv & 1 + 2^{t-4} + 0 \pmod{2^{t-3}} \\ & \equiv & 1 + 2^{t-4} \pmod{2^{t-3}}. \end{eqnarray*} This yields $\nu_2(T_n - 1) = t-4 = \nu_2(2^{t-3}s) - 1 = \nu_2(n-2) - 1$. The fourth case follows by proceeding in the same way as the third one. For $ t \geq 6$ and $ s \geq 1$ odd, we write $ n = 2^{t-3}s - 2$. Then, by the Lengyel and Marques result \cite[Lemma 3.1]{tamas}, we have that \begin{eqnarray*} T_{2^{t-3}s - 2} & = & T_{2^{t-3}s + 1} - T_{2^{t-3}s } - T_{2^{t-3}s -1} \\ & \equiv & 1 - 2^{t-4} - 0 \pmod{2^{t-3}} \\ & \equiv & 1 + 2^{t-4} \pmod{2^{t-3}}. \end{eqnarray*} This yields $\nu_2(T_n - 1) = t-4 = \nu_2(2^{t-3}s) - 1 = \nu_2(n+2) - 1$. Now, for the last case, we know that $16$ divides exactly one among $n-1$ and $n+7$. Suppose that $16 | (n + a)$, for some $a \in \left\{-1, 7\right\}$. Then $\nu_2(n+b) = 3$ for $b \in \left\{ -1 , 7 \right\} \backslash \left\{a\right\}$. So, we desire to prove that \[ \nu_2(T_n-1) = \nu_2(n+a). \] For that, we write $n = 2^{t-2}s - a$, for $t \geq 5$ and $s \geq 1$ odd, and proceed as in Lengyel and Marques \cite[Lemma 3.1]{tamas} to prove that \[ T_{2^{t-2}s - a}-1 \equiv 2^{t-2} \pmod{2^{t-1}}. \] Therefore \[ \nu_2(T_n - 1) = t-2 = \nu_2(n+a) + 1, \] and this completes the proof. \qed \bigskip \noindent {\bf The case $T_n+1$:} The first two cases are trivial. The third and the fourth cases follow in the same way. Note that, in order to prove them, it suffices to show that $T_n \equiv 1$ (mod $4$) when $ n \equiv 1, 2, 6$ (mod $8$) and to show that $T_n = 7 \pmod{16}$ when $ n \equiv 5$ (mod $16$). In order to avoid unnecessary repetitions, we shall prove only one of these cases. So, let us write $n = 8k + 6$ and apply induction on $k \geq 0$. For $k=0$, it follows directly, since $T_6 + 1 = 13 + 1 = 14 = 2 \cdot 7$. Now, suppose that $T_{8k+6}\equiv 1$ (mod $4$). Then, we have that \begin{eqnarray*} T_{8(k+1) +6} & = & T_{(8k+6) + 8} \\ & = & T_6 T_{8k+6} + (T_6 + T_5)T_{8k+7} + T_7 T_{8k+8} \\ & = & 13 T_{8k+6} + 20 T_{8k+7} + 24 T_{8k+8} \\ & \equiv & 1 \pmod 4. \end{eqnarray*} Now, for the the fifth case, note that, if $n=64k+13$, \begin{eqnarray*} \nu_2((n+3)^2) - 3 & = & 2\nu_2(n+3) - 3 \\ &= & 2\nu_2(64k + 13 + 3) - 3 = 2\nu_2(16(4k+1)) - 3 = 2 \cdot 4 - 3 \\ & = & 5. \end{eqnarray*} So, it suffices to prove that $T_n \equiv 31$ (mod $64$). Again, we proceed on induction. First, observe that $T_{13} = 927 \equiv 31$ (mod $64$). Now, we have that \begin{eqnarray*} T_{64(k+1) +13} & = & T_{(64k+13) + 64} \\ & = & T_{62} T_{64k+13} + (T_{62} + T_{61})T_{64k+14} + T_{63} T_{64k+15} \\ & \equiv & -1 + 32T_{64k+14} \pmod{64}. \end{eqnarray*} But, from the previous case, we have that $T_{64k+14} \equiv 1$ (mod $4$). Then, \begin{eqnarray*} T_{64(k+1) +13} & \equiv & -1 + 32T_{64k+14} \pmod{64} \\ & \equiv & 32 - 1 \pmod{64} \\ & \equiv & 31 \pmod{64}. \end{eqnarray*} When $n \equiv 29, 45$ (mod $64$), we proceed in the same way. For the last case, we proceed as for the last case of the previous theorem. Note that $128$ divides exactly one among $n-61$ and $n+3$. Suppose that $128 | (n + a)$, for some $a \in \left\{-61, 3\right\}$. Then $\nu_2(n+b) = 6$ for $b \in \left\{ -61 , 3 \right\} \backslash \left\{a\right\}$. So, we desire to prove that \[ \nu_2(T_n+1) = \nu_2(n+a)+3. \] For that, we write $ n = 2^{t-2}s - a$, for $t \geq 8$ and $s \geq 1$ odd, and proceed as in Lengyel and Marques \cite[Lemma 3.1]{tamas} to prove that \[ T_{2^{t-2}s - a}+1 \equiv 2^{t+1} \pmod{2^{t+2}}. \] Therefore \[ \nu_2(T_n + 1) = t+1 = \nu_2(n+a) + 3. \] This completes the proof. \qed Now, we are ready to deal with the proof of the main theorem. \subsection{The proof}\label{proof} If $n\leq 61$, a straightforward search shows that there are no solutions. So we shall suppose that $n>61$. Then $m\geq 30$. Next we use the fact that $\nu_2(m!)\geq m-\left\lfloor \log m/\log 2\right\rfloor-1$ (which is a consequence of the De Polignac's formula) together with Lemma \ref{key}. Then \begin{eqnarray*} m-\left\lfloor \frac{\log m}{\log 2}\right\rfloor-1 &\leq & \nu_2(m!)=\nu_2(T_n-1)+\nu_2(T_n+1)\\ & < & \nu_2((n+2)(n-2)(n-1)(n+7)(n+3)^3(n-61))+5\\ & \leq & 8\nu_2(n+\omega)+5, \end{eqnarray*} for some $\omega\in \{-61,-2,-1,2,3,7\}$. Thus $\nu_2(n+\omega)\geq (m-\left\lfloor \log m/\log 2\right\rfloor-6)/8$. Therefore, $2^{\lfloor (m-\left\lfloor \log m/\log 2\right\rfloor-6)/8\rfloor}\mid (n+\omega)$. In particular, $2^{\lfloor (m-\left\lfloor \log m/\log 2\right\rfloor-6)/8\rfloor}\leq |n+\omega|\leq n+61$ (here we used that $n+\omega\neq 0$). By applying the $\log$ function, we obtain \begin{equation}\label{I} \left\lfloor \frac{1}{8}\left(m-\left\lfloor \frac{\log m}{\log 2}\right\rfloor-6\right) \right\rfloor\leq \dfrac{\log (n+61)}{\log 2}. \end{equation} On the other hand, $(1.83)^{2n-4}