info prev up next book cdrom email home

Göbel's Sequence

Consider the Recurrence Relation

x_n={1+{x_0}^2+{x_1}^2+\ldots+{x_{n-1}}^2\over n},
\end{displaymath} (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
\end{displaymath} (2)

C = 1.04783144757641122955990946274313755459\ldots
\end{displaymath} (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,
\end{displaymath} (4)

which gives the new recurrence
s_{n+1}=s_n+{{s_n}^2\over n^2}
\end{displaymath} (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)
\end{displaymath} (6)

2, 6, 15\equiv 1, {\textstyle{5\over 4}}\equiv 0, 0, 0, 0 \hfill ({\rm mod\ }7)
\end{displaymath} (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).
\end{displaymath} (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}
\end{displaymath} (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}.
\end{displaymath} (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}.
\end{displaymath} (11)

See also Somos Sequence


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.'' 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.''

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein