Solution to puzzle 121: Integer sequence
The terms of a sequence of positive integers satisfy an+3 = an+2(an+1 + an), for n = 1, 2, 3, ... .
If a6 = 8820, what is a7?
Letting a1 = x, a2 = y, and a3 = z, from the recurrence relation we obtain
a4 = z(y + x),
a5 = z(y + x)(z + y),
a6 = z(y + x)(z + y)[z(y + x) + z] = z2(y + x)(y + x + 1)(z + y).
Hence we have z2(y + x)(y + x + 1)(z + y) = 8820 = 22 × 32 × 5 × 72. A certain amount of trial and error is now required. The goal is to minimize the need for trial and error by applying mathematical constraints.
By the Fundamental Theorem of Arithmetic, the factors on the left-hand side are the same as those on the right-hand side of the equation. In particular, two of the factors on the left-hand side are consecutive integers, and therefore must be relatively prime. (Any divisor of n and n + 1 must divide n + 1 − n = 1.) This enables us to determine candidate values for (y + x) and (y + x + 1) -- by partitioning the prime factors 2, 3, 5, 7 -- more easily than if we had to obtain a complete list of the 54 factors of 8820.
Additionally, we note that if z = 1, then (y + 1)(y + x)(y + x + 1) = 8820, with y + 1 
y + x < y + x + 1, so that we must have y + x + 1 > 88201/3; that is, y + x 
20. This enables us to exclude the case z = 1 from many of the candidate factorizations below.
| (y + x) | (y + x + 1) | z2(z + y) | Deductions |
|---|---|---|---|
| 2 | 3 | 2 × 3 × 5 × 72 | y + x = 2  y = 1.1 < z2 | 2 × 3 × 5 × 72 z = 7.Hence z2(z + y) = 72 × 8. Contradiction. |
| 3 | 22 | 3 × 5 × 72 | y + x = 3 y 2. 1 < z2 | 2 × 3 × 5 × 72 z = 7.Hence z2(z + y) 72 × 8. Contradiction. |
| 22 | 5 | 32 × 72 | y + x = 4 y 3. 1 < z2 | 32 × 72 z = 3, 7, or 21. Then:
|
| 5 | 2 × 3 | 2 × 3 × 72 | 1 < z2 | 2 × 3 × 72 z = 7. Hence z2(z + y) > 73. Contradiction. |
| 2 × 3 | 7 | 2 × 3 × 5 × 7 | 1 < z2 | 2 × 3 × 5 × 7 is impossible. |
| 32 | 2 × 5 | 2 × 72 | 1 < z2 | 2 × 72 z = 7. Hence z2(z + y) > 73. Contradiction. |
| 2 × 7 | 3 × 5 | 2 × 3 × 7 | 1 < z2 | 2 × 3 × 7 is impossible. |
| 22 × 5 | 3 × 7 | 3 × 7 | 1 < z2 | 3 × 7 is impossible. |
| 5 × 7 | 22 × 32 | 7 | z2 | 7 z = 1, and y = 6, x = 29. Solution! |
Hence we have two solutions, (x, y, z) = (2, 2, 7) or (29, 6, 1). The two sequences are thus, respectively:
2, 2, 7, 28, 252, 8820, 2469600... , and
29, 6, 1, 35, 245, 8820, 2469600... .
Therefore, if a6 = 8820, a7 = 2469600.
Remarks
Curiously, although we are able to deduce the value of a7, we cannot uniquely determine a8.
Source: Adapted from More Mathematical Morsels (Olympiad Corner, 1986), by Ross Honsberger