Skip to main content
4 of 4
added 244 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104