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

Candidate factorizations of 8820
(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 223 × 5 × 72y + x = 3 y 2.
1 < z2 | 2 × 3 × 5 × 72 z = 7.
Hence z2(z + y) 72 × 8.  Contradiction.
225 32 × 72y + x = 4 y 3.
1 < z2 | 32 × 72 z = 3, 7, or 21.  Then:
• z = 3 z2(z + y) 32 × 6.  Contradiction.
• z = 7 y = 2, x = 2.  Solution!
• z = 21 z + y = 21, and so y = 0.  Contradiction.
5 2 × 3 2 × 3 × 721 < z2 | 2 × 3 × 72 z = 7.
Hence z2(z + y) > 73.  Contradiction.
2 × 372 × 3 × 5 × 71 < z2 | 2 × 3 × 5 × 7 is impossible.
322 × 5 2 × 721 < z2 | 2 × 72 z = 7.
Hence z2(z + y) > 73.  Contradiction.
2 × 73 × 52 × 3 × 71 < z2 | 2 × 3 × 7 is impossible.
22 × 53 × 7 3 × 7 1 < z2 | 3 × 7 is impossible.
5 × 7 22 × 327 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