# Is A276175 integer-only?

The terms of the sequence A276123, defined by $a_0=a_1=a_2=1$ and $$a_n=\dfrac{(a_{n-1}+1)(a_{n-2}+1)}{a_{n-3}}\;,$$ are all integers (it's easy to prove that for all $n\geq2$, $a_n=\frac{9-3(-1)^n}{2}a_{n-1}-a_{n-2}-1$).

But is it also true for the sequence A276175 defined by $a_0=a_1=a_2=a_3=1$ and $$a_n=\dfrac{(a_{n-1}+1)(a_{n-2}+1)(a_{n-3}+1)}{a_{n-4}} \;\;?$$

Update : I crossposted to MO.

• If you see what they've written under "comments" in your OEIS link, it is clear that it is not known. It has been checked by computer for the first $40$ terms. – Arthur Aug 27 '16 at 7:13
• Yes Arthur, I read it. This sequence has been entered recently in the OEIS... Perhaps a member of this forum will have an idea to solve the problem ? – uvdose Aug 27 '16 at 7:32
• That's strange for me. The sequence does not seem to be hardly to calculate. So why has it only been checked till $n=40$? – S. M. Roch Aug 27 '16 at 13:53
• @S.M.Roch my guess is that it grows doubly exponentially ($a_n$ grows like $b^{c^n}$ for some constants $b,c$) – mercio Aug 27 '16 at 14:33
• @S.M.Roch. I made a program : the decimal expansion of $a_{40}$ contains $321865971$ digits. – uvdose Aug 27 '16 at 15:19

Yes, $(a_n)$ is a sequence of integers.

To prove this we first need to study some auxiliary sequences that satisfy a polynomial recurrence relation (unlike $(a_n)$ which has a rational fraction as its recurrence).

Consider the sequences $(b_n)$ of positive reals satisfying the recurrence relation $b_nb_{n+4} = b_{n+1}b_{n+2}b_{n+3} + 1$.

It turns out we can express $b_{n+8}$ as a polynomial in $b_n, \ldots, b_{n+7}$ :

Since $b_{n+1}b_{n+5} \equiv b_{n+2}b_{n+6} \equiv b_{n+3}b_{n+7} \equiv 1 \pmod {b_{n+4}}$ and $b_{n+1}b_{n+2}b_{n+3} \equiv -1 \pmod {b_{n+4}}$, we have $b_{n+5}b_{n+6}b_{n+7} \equiv -1 \pmod {b_{n+4}}$, which suggests the existence of a formula for $b_{n+8}$.

With this roadmap, we can write

$(b_{n+1}b_{n+2}b_{n+3})(b_{n+5}b_{n+6}b_{n+7}+1) \\ = (b_{n+1}b_{n+5})(b_{n+2}b_{n+6})(b_{n+3}b_{n+7}) + (b_{n+1}b_{n+2}b_{n+3}) \\ = (b_{n+2}b_{n+3}b_{n+4}+1)(b_{n+3}b_{n+4}b_{n+5}+1)(b_{n+4}b_{n+5}b_{n+6}+1)+(b_nb_{n+4}-1) \\ = b_{n+4}.F(b_{n+i})$

where $F$ is some big polynomial. And finally,

$(b_{n+5}b_{n+6}b_{n+7}+1) = (b_{n+5}b_{n+6}b_{n+7}+1)(b_nb_{n+4} - b_{n+1}b_{n+2}b_{n+3}) \\ = b_{n+4}(b_nb_{n+5}b_{n+6}b_{n+7}+b_n - F(b_{n+i})) = b_{n+4} G(b_{n+i})$.

And so, $b_{n+8} = G(b_{n+i})$. This means that if $b_0, \ldots, b_7 \in R$ for some subring $R$ of $\Bbb R$, then the whole sequence is in $R$.

Now to link back to the original sequence.

Given such a sequence $(b_n)$, we define a sequence $(a_n)$ by $a_n = b_nb_{n+1}b_{n+2}$.

This sequence satisfies $a_na_{n+4} = (b_n b_{n+1}b_{n+2})(b_{n+4}b_{n+5}b_{n+6}) \\ = (b_n b_{n+4})(b_{n+1} b_{n+5})(b_{n+2} b_{n+6}) = (b_{n+1}b_{n+2}b_{n+3}+1)(b_{n+2}b_{n+3}b_{n+4}+1)(b_{n+3}b_{n+4}b_{n+5}+1) \\ = (a_{n+1}+1)(a_{n+2}+1)(a_{n+3}+1)$.

Finally, taking $b_0 \ldots b_7 = \frac 12, 4, \frac 12, \frac 12, 4, \frac 12, 4, 18$, we obtain a sequence $(b_n)$ with terms in $\Bbb Z[\frac 12]$, with the corresponding $(a_n)$ sequence $1,1,1,1,8,36, \ldots$

Since the recurrence relation is symmetric, it can go backwards as well as forward, hence the ring $R_n = \Bbb Z[b_n, \ldots, b_{n+7}]$ is independant of $n$. There is no hope of finding $8$ consecutive integer values in our sequence $b_n$.

If we look at the sequence $(b_n)$ modulo $8$, from our first octuplet and by applying the polynomial transformation, we can get to $17225$ different octuplets mod $8$, and none of those correspond to any noninteger $a_n$. This computation proves that $a_n$ is an integer forall $n$ (be careful, one step can go from one octuplet to several octuplets, because precision can be lost sometimes).

Note that using this definition,

$a_na_{n+2}/a_{n+1}(a_{n+1}+1) = b_nb_{n+2}b_{n+4}/(b_{n+1}b_{n+2}b_{n+3}+1) = b_{n+2}$,

and so to go in the other direction you have to define $(b_n)$ from $(a_n)$ with $b_n = a_{n-2}a_n/a_{n-1}(a_{n-1}+1)$. Then, once again the recurrence relation of $(b_n)$ follows from that of $(a_n)$.

This shows that for any such rational sequence $(a_n)$, there is a corresponding rational sequence $(b_n)$, and so $(a_n)$ is in a finitely generated subring of $\Bbb Q$.

• one might wonder if there is an integer $m$ such that $a_{n+m}$ is a polynomial in the $a_{n+i}$ for $0 \le i < m$. If so, then $m > 55$ because the subsequence $(1,2,1,2)$ is in the middle of a sequence of integers of length $55$ but bordered with nonintegers on both sides. I wouldn't expect such an $m$ to exist. – mercio Aug 29 '16 at 14:58
• I don't understand why the $a_i$ are integers (as opposed to just $2$-integers). Could you be more precise there? Thanks! – darij grinberg Feb 22 '19 at 22:17
• In order to have $a_n$ integer, one would need to demonstrate that the sum of the $2$-adic valuations of three consecutive $b_j$ is non-negative. If it can be shown that $v_2(b_n)$ is periodic (period $11$ apparently), then we are done, because, it would suffice to check the $11$ first sums. – René Gy Feb 24 '19 at 21:39
• @darijgrinberg It seems that this "detail" is hidden in the paragraph about the $17725$ octuples modul 8. I read from this that mercio performed an exhaustive (computer) search during which, among others, $v_2(b_n)$ turned out to remain bounded and $a_n=b_nb_{n+1}b_{n+2}$ an integer. – Hagen von Eitzen Feb 28 '19 at 4:33
• @mercio: What do you mean by "octuplets"? The $b_n$ not being integers, it is strange to look at them mod $8$; are you considering their remainders (maybe upon mutliplication by $32$ or something) or their $2$-adic valuations? And you are saying that $8$ consecutive remainders (or valuations) always uniquely determine the next one? – darij grinberg Feb 28 '19 at 15:53