Define the sequences a_{n}, b_{n}, c_{n} as follows. a_{0} = k, b_{0} = 4, c_{0} = 1. If a_{n} is even then a_{n+1} = a_{n}/2, b_{n+1} = 2b_{n}, c_{n+1} = c_{n}. If a_{n} is odd, then a_{n+1} = a_{n} - b_{n}/2 - c_{n}, b_{n+1} = b_{n}, c_{n+1} = b_{n} + c_{n}. Find the number of positive integers k < 1995 such that some a_{n} = 0.

**Solution**

Answer: 31.

We call (y, z) a *vanishing pair* iff (1) y, z are positive integers, (2) y is a power of 2 greater than 2, (3) z < y, and (4) z = 1 mod 4. We show that there is a bijection between vanishing pairs and a_{0} such that a_{n-1} > 0, a_{n} = 0 for some positive integer n.

Note that b_{n} is always a power of 2 and is at least 4. (It starts as 4 and at each step either remains unchanged or doubles.) So c_{n} must be 1 mod 4 (it starts as 1 and always increases by multiples of 4).

We cannot have both a_{n-1} and a_{n} odd. For if a_{n-1} is odd, then a_{n} = a_{n-1} - b_{n-1}/2 - c_{n-1} = odd - even - odd = even. We claim that if a_{n} is even, then b_{n+1} > c_{n+1} and if a_{n} is odd, then 2b_{n+1} > c_{n+1}. We use induction. If a_{0} is odd, then b_{1} = 4, c_{1} = 5 and 8 > 5. If a_{0} is even, then b_{1} = 8, c_{1} = 1 and 8 > 1. So it is true for n = 0. Suppose it is true for n-1. If a_{n} is even, then b_{n+1} = 2b_{n} > c_{n} = c_{n+1}. If a_{n} is odd, then a_{n-1} is even (shown above), so 2b_{n+1} = b_{n} + b_{n} > b_{n} + c_{n} = c_{n+1}. So it is true for n, and hence for all n.

So suppose a_{0} leads to a_{n-1} > 0, a_{n} = 0 for some n. We claim that (b_{n-1}, c_{n-1}) is a vanishing pair. If n = 1, then this is trivial, because the term following (3, 4, 1) is (0, 4, 5). So assume n ≥ 2. We have already established conditions (1), (2) and (4) of the definition. a_{n-1} cannot be even, for then a_{n} = a_{n-1}/2 > 0. So a_{n-1} is odd. Hence a_{n-2} is even. Hence b_{n-1} > c_{n-1}, which establishes (3). So (b_{n-1}, c_{n-1}) is a vanishing pair as claimed.

Conversely, suppose (y, z) is a vanishing pair. If (y, z) = (4, 1), then the corresponding x_{0} is 3, and the term following (3, 4, 1) is (0, 4, 5). So suppose (y, z) is not (4, 1). We show that we can work backwards to get a term (x_{0}, 4, 1). We put x = y/2 + z to give the triple (x, y, z). The previous triple must be (2x, y/2, z) = (x', y', z'). Now if y' > z', then the previous triple (x", y", z") must have had x" even, otherwise we would have z' = y" + z" > y" = y'. So we take x" = 2x', y" = y'/2, z" = z'. If y' < z' (they cannot be equal, since one is even and the other odd), then we take x" = x' - y'/2+ z', y" = y', z" = z' - y'. Note that all terms (u, v, w) have v a power of 2 and w = 1 mod 4. Also either y or z is reduced as we go back and y is reduced unless z is larger, so we must eventually get y = 4. Then (as we go further back) we must eventually get z < y and hence z = 1. x is increased at each step backwards. So we eventually get to (x_{0}, 4, 1).

For example, (128, 1) is a vanishing pair. The corresponding triple must be (65, 128, 1). Working back, we get (130, 64, 1), (260, 32, 1), (520, 16, 1), (1040, 8, 1), (2080, 4, 1). Similarly, (64, 61) is a vanishing pair. The corresponding triple is (93, 64, 61). Working back, we get (186, 32, 61), (231, 32, 29), (462, 16, 29), (483, 16, 13), (966, 8, 13), (975, 8, 5), (1950, 4, 5), (1953, 4, 1).

It is easy to see that the x_{0} corresponding to (y, z) is greater than the x_{0} corresponding to (y', z') if y > y' or if y = y' and z > z'. The two examples in the previous paragraph bracket 1994, so the vanishing pairs that give x_{0} ≤ 1994 are: the 1 + 2 + 4 + 8 + 16 = 31 pairs (4, 1), (8, 1), (8, 5), (16, 1), (16, 5), (16, 9), (16, 13), (32, 1), (32, 5), ... , (32, 29), (64, 1), (64, 5), ... , (64, 61).

© John Scholes

jscholes@kalva.demon.co.uk

18 Sep 2002