# Can these sequences stay integer-valued as many times as we want and then fail?

Edit:

Suppose that we choose some integer $d$ and some natural number $c=c_2$. Then if we plug those values into $$c_{n+1}=\frac{c_n(c_n+n+d)}n$$ and observe the behavior of this recursively defined sequence ($n \geq 2$) then it can happen that it will produce integers up to some point and then fail. If we observe the space of tuples $(c_2,d) \in \mathbb N \times \mathbb Z$ then we can partition that set in the following way:

In $A_1$ go tuples for which only $c=c_2$ is an integer and $c_3$ is not, in $A_2$ go tuples for which $c_2$ and $c_3$ are integers and $c_4$ is not, ..., in $A_m$ go tuples for which $c_2,c_3,...c_{m+1}$ are integers and $c_{m+2}$ is not, ... , in $A_{\infty}$ go tuples for which every $c_n$ is an integer.

The question is: Is $A_m$ non-empty for every $m \in \mathbb N$?

Below is the question that I originally asked, and it is not the thing that I wanted to ask, I just wrongly formulated my thoughts. I will leave it as for the record, if someone knows how to cross it with some lines then I allow that to be done. Thank you.

Is it true that for every $m \in \mathbb N$ there exists integer $d$ and sequence $i \to c_i$ of positive integers which satisfies reccurence relation $$c_{n+1}=\frac{c_n(c_n+n+d)}n$$ in a way that the the first $m$ values of the sequence $c_i$ are integers and $(m+1)$-st value is not an integer?

Here are some related questions:

1

2

• The question is not rigorously formulated, but I guess it is asked in the context of my answer mathoverflow.net/a/282154/17581 – Max Alekseyev Sep 28 '17 at 0:46
• @MaxAlekseyev What shuold be added to ensure rigor? – user114642 Sep 28 '17 at 0:52
• E.g., see answer of Kevin O'Bryant exploiting a loophole in your formulation -- I suspect this is not what you want. – Max Alekseyev Sep 28 '17 at 1:31
• Again, $m=1$ does not seem to work since $c_2$ is always integer in this formulation. Also, you may have better luck with $m$ being prime - e.g., see oeis.org/A292996 – Max Alekseyev Sep 28 '17 at 2:01
• What you might want to ask is which $m$ are such that ...? – Aaron Meyerowitz Sep 28 '17 at 8:19

No, for trivial reasons. Such a sequence has two parameters: $d$ and $c_0$. The first three terms are $c_0$, $c_0(c_0+d)$, $\frac{1}{2} c_0 (c_0+d) \left(c_0^2+c_0 d+d+1\right)$. If the zeroth term is an integer, then so is the first term. Moreover, so is the second term!

• I made an edit and tried to formulate more clearly what I wanted to ask. – user114642 Sep 28 '17 at 3:01
• There are similar counterexamples to the new statement. If $c_2$ is arbitrary and $d$ is odd, then $c_3=c_2(c_2+2+d)/2$ is an integer so that $A_1$ is empty. – Philipp Lampe Sep 28 '17 at 9:07

A better question might be for which $m$ is there a sequence which fails at $c_{m+1}=\frac{c_m(c_m+m+d)}{m}.$

$2,3,12$ are possible but I don't think any other numbers $2^i3^j$ are. All primes up to $100$ are possible. Also $25,39,55,120,125$ Those are the only ones I found, but I didn't look hard at primes bigger than $5.$ What follows is mainly descriptive with some theory.

The approach I will outline might produce very large $c_0,d.$ Note too that, of course, the $c_i$ grow extremely rapidly.

If a failure happens at $c_m,$ then there a prime $p$ such that $p$ divides $m$ more times than it divides $c_m(c_m+m+d).$ As pointed out below, it is easier to work with the primes $p$ and see for which $m$ they can produce a failure by computing mod $p^i$ for a reasonably large $i.$

For sequences which can be seen to terminate due to a prime $p,$ it seems that the most usual behavior is that after a while $c_n =-d \bmod p.$ Then in $c_{n+1}=\frac{c_n(c_n+d+n)}{n}$ , $(c_n+d+n)=n \mod p.$ This means that the numerator can't accumulate powers of $p$ unless the denominator does so that termination due to $p$ can only happen at these $n$.

If $c_n+d+n$ is (very) naively assumed to be a random integer of the appropriate size then the expected power of $p$ dividing it is $\frac{1}{p}+\frac{2}{p^2}+\cdots+\frac{k}{p^k}$ where $k=\log_p c_n.$ While for $n$ it is $\frac{1}{p}+\frac{2}{p^2}+\cdots+\frac{j}{p^j}$ for the much smaller $j=\log_pn.$ This gives the numerator an advantage over the denominator. Once $n$ is extremely large this becomes less significant. The reasoning here is pretty vague so I won't pursue that.

Consider the $3^2$ choices for $(c_2,d)$ $\mod 3.$ Only $(2,0)$ leads to a problem at step $3.$ Looking at the $81^2$ choices $\mod 81,$ (computed say $\mod 3^{40}$) there are $729=3^6$ which are $(2,0) \mod 3$ and terminate after $3$ steps. Another $2\cdot 3^4$ are $(6,0) \mod 9$ and these (can) terminate in $12$ steps. A further $2^23^2$ are $(1,0),(9,0),(16,0)$ or $(24,0) \bmod 27$ and these (can) terminate (based on the prime $3$) after $39$ steps. Finally, $2^3$ can terminate after $120$ steps and these are $(c_2,0) \bmod 81$ for $c_2=27,33,34,37,42,45,46,52.$

I say can terminate since, for example $6,0 \mod 9$ includes the case $33,0 \mod 81$

There are obvious patterns which should be explainable. The numbers $3,12,39,120$ are each obtained by adding $1$ to the previous and tripling.

The behavior for $p=5$ seems more involved.

In fact taking $c_2,d=27,81$ which is claimed to lead to termination after $m=120$ due to the prime $3$ terminates at $m=7$ due to the prime $7.$ However take $N=2^{116}5^{28}7^{19}\cdots$ which is $\frac{120!}{3^58}.$ it is an integer and not a multiple of $3$. In fact it is $1 \bmod 3$ so $c_2,d=27N,81$ is such that no prime other than $3$ can cause a problem at or before $m=120.$ And the prime $3$ does terminate it at $m=120.$ There is sure to me a very much smaller (but still, perhaps, quite large) $M$ so that $c_2,d=27M,81$ has the same result.

• To investigate numerically you can compute the sequence mod various largish primes or powers of primes. It's not perfect but better than nothing. – Qiaochu Yuan Sep 28 '17 at 18:09