Define the sequences an, bn, cn as follows. a0 = k, b0 = 4, c0 = 1. If an is even then an+1 = an/2, bn+1 = 2bn, cn+1 = cn. If an is odd, then an+1 = an - bn/2 - cn, bn+1 = bn, cn+1 = bn + cn. Find the number of positive integers k < 1995 such that some an = 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 a0 such that an-1 > 0, an = 0 for some positive integer n.
Note that bn 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 cn must be 1 mod 4 (it starts as 1 and always increases by multiples of 4).
We cannot have both an-1 and an odd. For if an-1 is odd, then an = an-1 - bn-1/2 - cn-1 = odd - even - odd = even. We claim that if an is even, then bn+1 > cn+1 and if an is odd, then 2bn+1 > cn+1. We use induction. If a0 is odd, then b1 = 4, c1 = 5 and 8 > 5. If a0 is even, then b1 = 8, c1 = 1 and 8 > 1. So it is true for n = 0. Suppose it is true for n-1. If an is even, then bn+1 = 2bn > cn = cn+1. If an is odd, then an-1 is even (shown above), so 2bn+1 = bn + bn > bn + cn = cn+1. So it is true for n, and hence for all n.
So suppose a0 leads to an-1 > 0, an = 0 for some n. We claim that (bn-1, cn-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. an-1 cannot be even, for then an = an-1/2 > 0. So an-1 is odd. Hence an-2 is even. Hence bn-1 > cn-1, which establishes (3). So (bn-1, cn-1) is a vanishing pair as claimed.
Conversely, suppose (y, z) is a vanishing pair. If (y, z) = (4, 1), then the corresponding x0 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 (x0, 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 (x0, 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 x0 corresponding to (y, z) is greater than the x0 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 x0 ≤ 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