\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}}} \DeclareMathOperator{\lcm}{lcm} \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} \newtheorem{identity}{Identity} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A Tribonacci-Like Sequence of \\ \vskip .1in Composite Numbers } \vskip 1cm \large Ivan Lunev \\ Department of Mathematics and Mechanics \\ Saint-Petersburg State University \\ 28 Universitetsky Prospect \\ St.~Petersburg, 198504 \\ Russia \\ \href{mailto: lun-vano@yandex.ru}{\tt lun-vano@yandex.ru} \end{center} \vskip .2 in \begin{abstract} We find a new Tribonacci-like sequence of positive integers $\langle x_0,x_1,x_2,\ldots\rangle$ given by $x_n=x_{n-1}+x_{n-2}+x_{n-3}$ , $n\ge 3$, and $\gcd(x_0,x_1,x_2)=1$ that contains no prime numbers. We show that the sequence with initial values $x_0=151646890045$, $x_1=836564809606$, $x_2=942785024683$ is the current record in terms of the number of digits. \end{abstract} \section{Introduction} \v{S}iurys \cite{Siurys} found initial values \begin{align*} x_0 &=99202581681909167232 \\ x_1 &=67600144946390082339 \\ x_2 &=139344212815127987596, \end{align*} satisfying $\gcd(x_0,x_1,x_2)=1$, such that the Tribonacci-like sequence given by \begin{align} \label{a1} x_n=x_{n-1}+x_{n-2}+x_{n-3} \text{ for } n\ge 3 \end{align} contains no prime numbers. Similar problems were considered for Fibonacci-like sequences given by $x_n=x_{n-1}+x_{n-2}$ for $n\ge 2$ (Graham \cite{Graham}; Knuth \cite{Knuth}; Wilf \cite{Wilf}; Nicol \cite{Nicol}; Vsemirnov \cite{Vsemirnov}; Ismailescu and Son \cite{Ismailescu}), sequences given by $a_n=k 2^n+1$ (Sierpi\'{n}ski \cite{Sierpinski}; Jaeschke \cite{Jaeschke}), binary linear recurrent sequences ( Dubickas, Novikas, and \v{S}iurys \cite{Dubickas}; Somer \cite{Somer}) and some linear recurrent sequences of higher orders (\v{S}iurys \cite{Siurys1}). The main result of this note is as follows. \section{The main results} \begin{theorem} \label{Thm:MainResult} Let $\langle x_0,x_1,x_2,\ldots\rangle$ be defined by~\eqref{a1} and $\gcd(x_0,x_1,x_2)=1$ with the following initial values: \begin{equation*} x_0=151646890045,\quad x_1=836564809606,\quad x_2=942785024683. \end{equation*} Then $\langle x_0,x_1,x_2,\ldots\rangle$ contains no prime numbers. \end{theorem} \begin{remark} \label{rem:Rem} If we allow non-positive values, we can find a slightly smaller (in absolute value) initial triple, namely \begin{equation*} x_0= 730344594529,\quad x_1= -45426674968,\quad x_2= 151646890045. \end{equation*} \end{remark} \section{Proof of Theorem~\ref{Thm:MainResult}} In this section we complete the proof of Theorem~\ref{Thm:MainResult}. \begin{proof}[Proof of Theorem~\ref{Thm:MainResult}] First, recall \v{S}iurys' idea \cite{Siurys}. Consider the additional sequences $(s_n)_{n=0}^\infty$ and $(t_n)_{n=0}^\infty$ defined by the same relation~\eqref{a1} with $(s_0, s_1, s_2)=(0,1,0)$ and $(t_0, t_1, t_2) = (0,0,1)$. \begin{lemma}[\cite{Siurys}] \label{lem:Technical} Let $p$ be a prime. Suppose that for some integer $m\ge 2$ we have $s_mt_{2m}-s_{2m}t_m\equiv 0 \pmod{p}$. Then there exist $a$, $b\in\mathbb{Z}$ such that at least one of $a$, $b$ is not divisible by $p$ and $s_{km}a+t_{km}b\equiv 0 \pmod{p}$ for $k=0,1,2,\ldots$. \end{lemma} The next step is to find a set of pairs $(p_i, m_i)$ satisfying Lemma \ref{lem:Technical} such that every integer belongs to at least one of the arithmetic progressions \begin{align} \label{a2} A_i = m_ik + r_i, k \in \mathbb{Z} , i = 1,2,\ldots ,11 . \end{align} In this paper, the following values of $p_i$ and $m_i$ are used: (see Table \ref{tab:InformativeTable}). \begin{table}[!ht] \begin{center} \begin{tabular}{|c|c|c|c|} \hline $\mathbf{i}$ & $\mathbf{p_i}$ & $\mathbf{m_i}$ & $\mathbf{|s_{m_i}t_{2m_i}-s_{2m_i}t_{m_i}|}$ \\ \hline $1$ & $2$ & $2$ & $\textbf2$ \\ \hline $2$ & $29$ & $5$ & $\textbf{29}$ \\ \hline $3$ & $17$ & $6$ & $2\cdot\textbf{17}$ \\ \hline $4$ & $7$ & $8$ & $2^6\cdot\textbf7$ \\ \hline $5$ & $11$ & $10$ & $2\cdot\textbf{11}\cdot29$ \\ \hline $6$ & $107$ & $12$ & $2^3\cdot17\cdot\textbf{107}$ \\ \hline $7$ & $8819$ & $15$ & $29\cdot\textbf{8819}$ \\ \hline $8$ & $19$ & $20$ & $2^3\cdot11\cdot\textbf{19}\cdot29\cdot\textbf{239}$ \\ \hline $9$ & $239$ & $20$ & $2^3\cdot11\cdot\textbf{19}\cdot29\cdot\textbf{239}$ \\ \hline $10$ & $1151$ & $24$ & $2^6\cdot7\cdot17\cdot107\cdot\textbf{1151}$ \\ \hline $11$ & $1621$ & $30$ & $2\cdot11\cdot17\cdot29\cdot\textbf{1621}\cdot8819$ \\ \hline \end{tabular} \end{center} \caption{\label{tab:InformativeTable} $p_i$ and $m_i$.} \end{table} \v{S}iurys \cite{Siurys} used $p = 79$ with $m = 40$ instead of $p = 239$. By Lemma \ref{lem:Technical}, for every pair $(p_i, m_i)$ we can choose $(a_i,b_i)\in \mathbb{Z}^2$ so that at least one of $a_i$, $b_i$ is not divisible by $p_i$ and \begin{equation*} s_{km_i}a_i+t_{km_i}b_i\equiv 0 \pmod{p_i} \text{ for } k=0,1,2,\ldots . \end{equation*} Next, we construct a sequence $(x_n)_{n=0}^\infty$ satisfying \begin{equation*} x_n\equiv s_{m_i-r_i+n}a_i+t_{m_i-r_i+n}b_i \pmod{p_i},\qquad i=1,2,\ldots ,11,\qquad \text{ for } n=0,1,2,\ldots . \end{equation*} The initial values satisfy $$ \begin{aligned} & x_0\equiv s_{m_i-r_i}a_i+t_{m_i-r_i}b_i \pmod{p_i}, \qquad x_1\equiv s_{m_i-r_i+1}a_i+t_{m_i-r_i+1}b_i \pmod{p_i},\\ & x_2\equiv s_{m_i-r_i+2}a_i+t_{m_i-r_i+2}b_i \pmod{p_i},\qquad \text{ for } i=1,2,\ldots ,11. \\ \end{aligned} $$ We can find initial terms $(x_0,x_1,x_2)$ by the Chinese reminder theorem. In the method described above there is some freedom in the choice of $a_i$ and $b_i$ (up to a common factor). \v{S}iurys \cite{Siurys} used all $a_i$ equal to $1$. We show how to optimize the choice of $a_i$ and $b_i$. Let $P=\prod_{i=1}^{11}p_i$ . Let us consider the system: \begin{equation*} \begin{cases} x_0'\equiv Dx_0 \pmod{P}\\ x_1'\equiv Dx_1 \pmod{P}\\ x_2'\equiv Dx_2 \pmod{P} \end{cases} \end{equation*} subject to the constraint \begin{equation} \label{a3} \gcd(D,P)=1. \end{equation} The new triple $(x_0', x_1', x_2')$ also satisfies the above properties, i.e., each term of the sequence~\eqref{a1} with starting values $(x_0', x_1', x_2')$ is divisible by at least one of $p_1,\ldots,p_{11}$. For a moment, let us forget about condition~\eqref{a3}. Then the problem can be formulated as follows: find the minimum vector of the form \begin{equation*} D(x_0,x_1,x_2)+U_1(P,0,0)+U_2(0,P,0)+U_3(0,0,P), \end{equation*} i.e., the vector in the lattice generated by the vectors $(x_0,x_1,x_2)$, $(P,0,0)$, $(0,P,0)$, $(0,0,P)$. The smallest vector can be found by the LLL-algorithm \cite{Lenstra}. For any admissible covering~\eqref{a2} with the above $m_i$'s we build the initial values $(x_0,x_1,x_2)$ for the sequence~\eqref{a1} by using \v{S}iurys' method. Then using the LLL-algorithm we find the smallest lattice basis. Coordinates $(x_0', x_1', x_2')$ for each of the new three basis vectors will suit us, if the condition~\eqref{a3} is satisfied and $(x_0', x_1', x_2')$ are of the same sign (if all of them are negative, then replace $(x_0', x_1', x_2')$ by $(-x_0',-x_1',-x_2')$). Thus, searching through all possible coverings (the total amount is 23040) we find sets $(p_i, m_i, r_i, a_i, b_i)$. Those listed in Table \ref{tab:InformativeTable1} give rise to the smallest initial triple $x_0= 151646890045$, $x_1= 836564809606$, $x_2= 942785024683$, as stated in Theorem \ref{Thm:MainResult}. \begin{table}[!ht] \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline $\mathbf{i}$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ \\ \hline $\mathbf{m_i}$ & $2$ & $5$ & $6$ & $8$ & $10$ & $12$ & $15$ & $20$ & $20$ & $24$ & $30$\\ \hline $\mathbf{p_i}$ & $2$ & $29$ & $17$ & $7$ & $11$ & $107$ & $8819$ & $19$ & $239$ & $1151$ & $1621$\\ \hline $\mathbf{r_i}$ & $1$ & $0$ & $4$ & $0$ & $8$ & $8$ & $6$ & $2$ & $14$ & $12$ & $26$\\ \hline $\mathbf{a_i}$ & $1$ & $8$ & $16$ & $3$ & $7$ & $70$ & $3246$ & $12$ & $202$ & $1077$ & $180$\\ \hline $\mathbf{b_i}$ & $0$ & $23$ & $13$ & $1$ & $2$ & $17$ & $8805$ & $8$ & $103$ & $ 964$ & $291$\\ \hline \end{tabular} \end{center} \caption{\label{tab:InformativeTable1} $p_i, m_i, r_i, a_i, b_i$.} \end{table} If we allow non-positive terms in the sequence, the same method gives sets $(p_i', m_i', r_i', a_i', b_i')$, which give the sequence mentioned in the Remark \ref{rem:Rem}: $x_0= 730344594529$, $x_1= -45426674968$, $x_2= 151646890045$ (see Table \ref{tab:InformativeTable2}). \begin{table}[!ht] \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline $\mathbf{i}$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ \\ \hline $\mathbf{m_i}$ & $2$ & $5$ & $6$ & $8$ & $10$ & $12$ & $15$ & $20$ & $20$ & $24$ & $30$\\ \hline $\mathbf{p_i}$ & $2$ & $29$ & $17$ & $7$ & $11$ & $107$ & $8819$ & $19$ & $239$ & $1151$ & $1621$\\ \hline $\mathbf{r_i}$ & $1$ & $2$ & $0$ & $2$ & $0$ & $10$ & $8$ & $4$ & $16$ & $14$ & $28$\\ \hline $\mathbf{a_i}$ & $1$ & $8$ & $7$ & $3$ & $7$ & $70$ & $3246$ & $12$ & $202$ & $1077$ & $180$\\ \hline $\mathbf{b_i}$ & $0$ & $23$ & $11$ & $1$ & $2$ & $17$ & $8805$ & $8$ & $103$ & $964$ & $291$\\ \hline \end{tabular} \end{center} \caption{\label{tab:InformativeTable2} $p_i', m_i', r_i', a_i', b_i'$.} \end{table} It is worth noting that in the sequence mentioned in Remark \ref{rem:Rem} $x_2= 151646890045$, $x_3= 836564809606$, $x_4= 942785024683$, so this means that the sequence in Theorem \ref{Thm:MainResult} is a shift of the sequence in Remark \ref{rem:Rem}. \end{proof} Both sequences can be extended to the left. It can be shown that in both cases mentioned above these extended sequences also contain no primes. Since the sequences modulo $P$ are periodic with period $\lcm(m_1,\ldots,m_{11})=120$, it is enough to check that $x_j\neq k$ modulo $P$, $-8819\leq k\leq 8819=\max(p_i)$, $j=0,\ldots,119$. \begin{thebibliography}{13} \bibitem{Dubickas} A.~Dubickas, A.~Novikas, and J.~\v{S}iurys, \newblock A binary linear recurrence sequence of composite numbers. \newblock {\em J. Number Theory} \textbf{130} (2010), 1737--1749. \bibitem{Graham} R.~L. Graham, \newblock A Fibonacci-like sequence of composite numbers. \newblock {\em Math. Mag.} \textbf{37} (1964), 322--324. \bibitem{Ismailescu} D.~Ismailescu and J.~Son, \newblock A new kind of Fibonacci-like sequence of composite numbers. \newblock {\em J. Integer Sequences} \textbf{17} (2014), \href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Ismailescu/ism8.html}{Article 14.8.2}. \bibitem{Jaeschke} G.~Jaeschke, \newblock On the smallest $k$ such that all $k2^N + 1$ are composite. \newblock {\em Math. Comp.} \textbf{40} (1983), 381--384. \bibitem{Knuth} D.~E. Knuth, \newblock A Fibonacci-like sequence of composite numbers. \newblock {\em Math. Mag. } \textbf{63} (1990), 21--25. \bibitem{Lenstra} A.~K. Lenstra, H.~W. Lenstra, Jr., and L. ~Lov\'{a}sz, \newblock Factoring polynomials with rational coefficients. \newblock {\em Math. Ann.} \textbf{261} (1982), 515--534. \bibitem{Nicol} J.~W. Nicol, \newblock A Fibonacci-like sequence of composite numbers. \newblock {\em Electron. J. Combin.} \textbf{6} (1999), \#R44. \bibitem{Sierpinski} W.~Sierpi\'{n}ski, \newblock Sur un probl\`{e}me concernant les nombres $k2^n+1$. \newblock {\em Elem. Math.} \textbf{15} (1960), 63--74. \bibitem{Siurys1} J.~\v{S}iurys, \newblock A linear recurrence sequence of composite numbers. \newblock {\em LMS J. Comput. Math.} \textbf{15} (2012), 360--373. \bibitem{Siurys} J.~\v{S}iurys, \newblock A Tribonacci-like sequence of composite numbers. \newblock {\em Fibonacci Quart.} \textbf{49} (2011), 298--302. \bibitem{Somer} L.~Somer, \newblock Second-order linear recurrences of composite numbers. \newblock {\em Fibonacci Quart.} \textbf{44} (2006), 358--361. \bibitem{Vsemirnov} M.~Vsemirnov, \newblock A new Fibonacci-like sequence of composite numbers. \newblock {\em J. Integer Sequences} \textbf{7} (2004), \href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Ismailescu/ism8.html}{Article 04.3.7}. \bibitem{Wilf} H.~S. Wilf, \newblock Letters to the editor. \newblock {\em Math. Mag. } \textbf{63} (1990), 284. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B39; Secondary 11B37. \noindent \emph{Keywords: } Tribonacci-like recurrence, composite number. \bigskip \hrule \bigskip \noindent (Concerned with \seqnum{A000045}, \seqnum{A000073}, and \seqnum{A056993}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 20 2016; revised versions received November 25 2016; December 27 2016; January 3 2017. Published in {\it Journal of Integer Sequences}, January 3 2017. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}