TOPICS
Search

Göbel's Sequence


Consider the recurrence relation

 x_n=(1+x_0^2+x_1^2+...+x_(n-1)^2)/n,
(1)

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

 x_n approx (n+2-n^(-1)+4n^(-2)-21n^(-3)+138n^(-4)-1091n^(-5)+...)C^(2^n)
(2)

(OEIS A116603; correcting Finch 2003, p. 446), where

 C=1.04783144757641122955990946274313755459...
(3)

(OEIS A115632; Finch 2003, p. 446; Zagier).

It is more convenient to work with the transformed sequence

 s_n=2+x_1^2+x_2^2+...+x_(n-1)^2=nx_n,
(4)

which gives the new recurrence

 s_(n+1)=s_n+(s_n^2)/(n^2)
(5)

with initial condition s_1=2. The first few terms of this sequence are 2, 6, 15, 40, 140, 924, 24640, ... (OEIS A061322). Now, s_(n+1) will be nonintegral iff ns_n. The smallest prime number p for which s_p≢0 (mod p) therefore gives the smallest nonintegral s_(p+1). In addition, since ps_p, x_p=s_p/p will also be the smallest nonintegral x_p.

For example, the first few sequences {s_n (mod p)}_(n=1)^p are summarized in the following table. (Note that congruences applied to fractions yield integer values.)

p{s_n (mod p)}_(n=1)^p
20, 0
32, 0, 0
52, 1, 0, 0, 0
72, 6, 1, 5, 0, 0, 0
112, 6, 4, 7, 8, 0, 0, 0, 0, 0, 0
132, 6, 2, 1, 10, 1, 5, 1, 0, 0, 0, 0, 0
172, 6, 15, 6, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 0

While s_n (and therefore their values modulo p) can be computed explicitly for small values of n and p, the fractions quickly grow too large to represent exactly. However, computing terms modulo p directly avoids term growth, and testing values of p in this way shows that the first nonintegral x_p is x_(43). As expected, direct verification of this fact is impossible since

 x_(43) approx 5.4093×10^(178485291567)
(6)

(calculated using the asymptotic formula) is much too large to be computed and stored explicitly. The first few values of p for which x_p are not integers are 43, 61, 67, 83, 103, 107, 109, 157, ....

A sequence even more striking for assuming integer values only for finitely many terms is the 3-Göbel sequence

 x_n=(1+x_0^3+x_1^3+...+x_(n-1)^3)/n.
(7)

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

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

 x_n=(1+x_0^k+x_1^k+...+x_(n-1)^k)/n.
(8)

See also

Somos Sequence

Explore with Wolfram|Alpha

References

Finch, S. R. Mathematical Constants. Cambridge, England: Cambridge University Press, p. 446, 2003.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, A005166/M1551, A061322, A115632, and A116603 in "The On-Line Encyclopedia of Integer Sequences."Stone, A. "The Astonishing Behavior of Recursive Sequences." Quanta. Nov. 16, 2023. https://www.quantamagazine.org/the-astonishing-behavior-of-recursive-sequences-20231116.Zaiger, D. "Solution: Day 5, Problem 3." http://www-groups.dcs.st-and.ac.uk/~john/Zagier/Solution5.3.html.

Referenced on Wolfram|Alpha

Göbel's Sequence

Cite this as:

Weisstein, Eric W. "Göbel's Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GoebelsSequence.html

Subject classifications