18
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ See also, this MO answer: mathoverflow.net/a/217894/25028 with a link to the OEIS: oeis.org/A003504 $\endgroup$
    – Sam Hopkins
    Commented Sep 27, 2017 at 14:41
  • 5
    $\begingroup$ Some information can be found in H. Ibstedt, Some sequences of large integers, Fibonacci Quart. 28 (1990), 200-203. (Link) $\endgroup$
    – Fred Rohrer
    Commented Sep 27, 2017 at 19:04

1 Answer 1

Reset to default
27
$\begingroup$

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:

Improve this answer
$\endgroup$
9
  • 7
    $\begingroup$ 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? $\endgroup$
    – Ilya Bogdanov
    Commented Sep 27, 2017 at 15:17
  • 1
    $\begingroup$ @IlyaBogdanov: Good question! I don't have an immediate answer. It may be worth to ask it at MO separately. $\endgroup$
    – Max Alekseyev
    Commented Sep 27, 2017 at 15:22
  • $\begingroup$ OK, let me do it. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 27, 2017 at 15:25
  • $\begingroup$ @MaxAlekseyev: the recursion only holds for $n\geq2$, right? $\endgroup$
    – Sam Hopkins
    Commented Sep 27, 2017 at 16:21
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Max Alekseyev
    Commented Sep 27, 2017 at 21:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .