Consider the recurrence relation
(1)
|
with . The first few iterates of are 1, 2, 3, 5, 10, 28, 154, ... (OEIS A003504). The terms grow extremely rapidly, but are given by the asymptotic formula
(2)
|
(OEIS A116603; correcting Finch 2003, p. 446), where
(3)
|
(OEIS A115632; Finch 2003, p. 446; Zagier).
It is more convenient to work with the transformed sequence
(4)
|
which gives the new recurrence
(5)
|
with initial condition . The first few terms of this sequence are 2, 6, 15, 40, 140, 924, 24640, ... (OEIS A061322). Now, will be nonintegral iff . The smallest prime number for which (mod ) therefore gives the smallest nonintegral . In addition, since , will also be the smallest nonintegral .
For example, the first few sequences are summarized in the following table. (Note that congruences applied to fractions yield integer values.)
2 | 0, 0 |
3 | 2, 0, 0 |
5 | 2, 1, 0, 0, 0 |
7 | 2, 6, 1, 5, 0, 0, 0 |
11 | 2, 6, 4, 7, 8, 0, 0, 0, 0, 0, 0 |
13 | 2, 6, 2, 1, 10, 1, 5, 1, 0, 0, 0, 0, 0 |
17 | 2, 6, 15, 6, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 0 |
While (and therefore their values modulo ) can be computed explicitly for small values of and , the fractions quickly grow too large to represent exactly. However, computing terms modulo directly avoids term growth, and testing values of in this way shows that the first nonintegral is . As expected, direct verification of this fact is impossible since
(6)
|
(calculated using the asymptotic formula) is much too large to be computed and stored explicitly. The first few values of for which 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
(7)
|
The first few terms of this sequence are 1, 2, 5, 45, 22815, ... (OEIS A005166).
The Göbel sequences can be generalized to powers by
(8)
|