1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The question is not rigorously formulated, but I guess it is asked in the context of my answer mathoverflow.net/a/282154/17581 $\endgroup$ – Max Alekseyev Sep 28 '17 at 0:46
  • $\begingroup$ @MaxAlekseyev What shuold be added to ensure rigor? $\endgroup$ – user114642 Sep 28 '17 at 0:52
  • 2
    $\begingroup$ E.g., see answer of Kevin O'Bryant exploiting a loophole in your formulation -- I suspect this is not what you want. $\endgroup$ – Max Alekseyev Sep 28 '17 at 1:31
  • 1
    $\begingroup$ 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 $\endgroup$ – Max Alekseyev Sep 28 '17 at 2:01
  • 2
    $\begingroup$ What you might want to ask is which $m$ are such that ...? $\endgroup$ – Aaron Meyerowitz Sep 28 '17 at 8:19
4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I made an edit and tried to formulate more clearly what I wanted to ask. $\endgroup$ – user114642 Sep 28 '17 at 3:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Philipp Lampe Sep 28 '17 at 9:07
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy