Göbel's Sequence

Consider the Recurrence Relation

$$x_n={1+{x_0}^2+{x_1}^2+\ldots+{x_{n-1}}^2\over n},$$ (1)

with $x_0=1$. The first few iterates of $x_n$ are 1, 2, 3, 5, 10, 28, 154, ... (Sloane's A003504). The terms grow extremely rapidly, but are given by the asymptotic formula

$$x_n\approx(n^2+2n-1+4n^{-1}-21n^{-2}+137n^{-3}-\ldots)C^{2^n},$$ (2)

where

$$C = 1.04783144757641122955990946274313755459\ldots$$ (3)

(Zagier). It is more convenient to work with the transformed sequence

$$s_n = 2+{x_1}^2+{x_2}^2+\ldots+{x_{n-1}}^2=n x_n,$$ (4)

which gives the new recurrence

$$s_{n+1}=s_n+{{s_n}^2\over n^2}$$ (5)

with initial condition $s_1=2$. Now, $s_{n+1}$ will be nonintegral Iff $n\notdiv s_n$. The smallest $p$ for which $s_p\not\equiv 0$ (mod $p$) therefore gives the smallest nonintegral $s_{p+1}$. In addition, since $p\notdiv s_p$, $x_p=s_p/p$ is also the smallest nonintegral $x_p$.

For example, we have the sequences $\{s_n{\rm\ (mod\ }k)\}_{n=1}^k$:

$$2, 6\equiv 2, {\textstyle{5\over 4}}\equiv 0, 0, 0 \hfill({\rm mod\ }5)$$ (6)

$$2, 6, 15\equiv 1, {\textstyle{5\over 4}}\equiv 0, 0, 0, 0 \hfill ({\rm mod\ }7)$$ (7)

$$2, 6, 15\equiv 4, {\textstyle{52\over 9}}\equiv 7, {\textsty... ...tyle{264\over 5}}\equiv 0, 0, \ldots, 0\hfill ({\rm mod\ }11).$$ (8)

Testing values of $k$ shows that the first nonintegral $x_n$ is $x_{43}$. Note that a direct verification of this fact is impossible since

$$x_{43} \approx 5.4093\times 10^{178485291567}$$ (9)

(calculated using the asymptotic formula) is much too large to be computed and stored explicitly.

A sequence even more striking for remaining integral over many terms is the 3-Göbel sequence

$$x_n={1+{x_0}^3+{x_1}^3+\ldots+{x_{n-1}}^3\over n}.$$ (10)

The first few terms of this sequence are 1, 2, 5, 45, 22815, ... (Sloane's A005166).

The Göbel sequences can be generalized to $k$ powers by

$$x_n={1+{x_0}^k+{x_1}^k+\ldots+{x_{n-1}}^k\over n}.$$ (11)

See also Somos Sequence

References

Guy, R. K. ``The Strong Law of Small Numbers.'' Amer. Math. Monthly 95, 697-712, 1988.

Guy, R. K. ``A Recursion of Göbel.'' §E15 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 214-215, 1994.

Sloane, N. J. A. Sequences A003504/M0728 and A005166/M1551 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Zaiger, D. ``Solution: Day 5, Problem 3.'' http://www-groups.dcs.st-and.ac.uk/~john/Zagier/Solution5.3.html.