The sequence 0 ≤ a0 < a1 < a2 < ... is such that every non-negative integer can be uniquely expressed as ai + 2aj + 4ak (where i, j, k are not necessarily distinct). Find a1998.
Solution
Answer: So a1998 = 810 + 89 + 88 + 87 + 86 + 83 + 82 + 8 = 1227096648.
After a little experimentation we find that the first few terms are 0, 1, 8, 9, 64, 65. This suggests that each term is a sum of distinct powers of 8. If N is any positive integer, then N is a sum of distinct powers of 2: x = b0 + b12 + b222 + b322 + ... , where bi = 0 or 1. Grouping every third term, we get: N = (b0 + b38 + b682 + ... ) + 2(b1 + b48 + b782 + ... ) + 4(b2 + b58 + b882 + ... ) = a + 2b + 4c (*), where a, b, c are each sums of distinct powers of 8. But (*) is evidently unique, because we may write a, b, c as indicated as a sum of powers of 8 and then get the binary expression for N. That is unique, so (*) is unique.
Could there be a different sequence An with the same property? We obviously require A0 = 0, A1 = 1. Suppose An is not the same as an. Then take m to be the first n at which they disagree. Suppose am < Am. Then am must have an expression Ai + 2Aj + 4Ak with i, j and k all < m. But that means that am has two different expressions using the sequence an. Contradiction.
How do we order the sums of distinct powers of 8? Suppose C = c0 + c18 + c282 + ... + cn8n, and D = d0 + d18 + ... + dn8n, where all ci and di are 0 or 1. Then evidently C < D iff the binary number c0c1 ... cn < d0 ... dn. So to find the (n+1)th member of the sequence an we write n in binary and then read it back in base 8. We have 1998 = 1024 + 512 + 256 + 128 + 64 + 8 + 4 + 2. So a1998 = 810 + 89 + 88 + 87 + 86 + 83 + 82 + 8 = 1227096648.
© John Scholes
jscholes@kalva.demon.co.uk
30 Aug 2002