# Simple recurrence that fails to be integer for the first time at the 44th term

The sequence defined by $a_0=a_1 =1$ and $$a_n = \frac{1}{n-1}\sum_{i=0}^{n-1}a_i^2, \quad n > 1$$ fails to be integer for the first time at $a_{44}$. Why??

You can verify the statement by computing the sequence mod 43 (see more commentary here (day 5, problem 3)). That's not a very satisfying answer though. Is there a good reason for this behavior?

Copying my explanation from https://mathoverflow.net/a/217894/25028

The recurrence formula can be rewritten as $$a_2=2,\qquad a_{n+1}=\frac{a_n\cdot (a_n+n-1)}n,\quad n\geq 2,$$ which somewhat justifies why $a_n$ remains integer for quite a while. It shows that $a_n$ accumulates most of the factors of the previous terms and gains some new ones. The division by $n$ happens to hit the existing factors up until $n=43$.

Another example of this kind is given by $$b_2=2,\qquad b_{n+1}=\frac{b_n\cdot (b_n+n+5)}n,\quad n\geq 2,$$ which remains integer for up to $n=59$.

ADDED. OEIS A292996 gives indices of first noninteger terms in similar sequences.

Some spin-off questions:

• Is there any positive sequence of this type ($c_{n+1}=c_n(c_n+n+\alpha)/n$ with integer $\alpha$ which remains integer forever? – Ilya Bogdanov Sep 27 '17 at 15:17
• @IlyaBogdanov: Good question! I don't have an immediate answer. It may be worth to ask it at MO separately. – Max Alekseyev Sep 27 '17 at 15:22
• OK, let me do it. – Ilya Bogdanov Sep 27 '17 at 15:25
• @MaxAlekseyev: the recursion only holds for $n\geq2$, right? – Sam Hopkins Sep 27 '17 at 16:21
• @AntoinedePaladin: There are many such examples with growing records. E.g., $c_2=2$ and $c_{n+1}=c_n(c_n+n+16)/n$ give integers when $n<73$. – Max Alekseyev Sep 27 '17 at 21:41