Terry has invented a new way to extend lists of numbers. To “Terryfy” a list such as [1, 8] he creates two lists [2, 9] and [3, 10], where each term is one more than the correponding term in the previous list, and then join the three lists together to give [1, 8, 2, 9, 3, 10]. If he starts with a list containing one number [0] and repeatedly “Terryfies” it he creates the list [0, 1, 2, 1, 2, 3, 2, 3, 4, 1, 2, 3, 2, 3, 4, 3, 4, 5, 2, 3, 4, …]. What is the 2012th number in this “Terryfic” list?
Let’s call the first term the 0th term and so on. Let L be the original list and L(k) be the kth term of L. So we are to seek L(2011) = L(23^6+23^5+23^3+3^2+3+1) or L(2202111_3). The number 2202111_3 stands for 2202111 in base 3. Notice that the the sublist starting from the (3^k)th term and ending before the (23^k)th terms can be obtained from the sublist of the first 3^k terms of L by adding 1 to each number. Similarly, the sublist starting from the 2(3^k)th term and ending before the [3^(k+1)]th term can be obtained from the sublist of the first 3^k terms of L by adding 2 to each number. In others words, L(3^k+d) = 1+L(d) and L(23^k+d) + 2+L(d),
where 0 <= d < 3^k. It follows that
L(2202111_3)
= 2+L(202111_3)
= 2+2+L(2111_3)
= 2+2+2+L(111_3)
= 2+2+2+1+L(11_3)
= 2+2+2+1+1+L(1_3)
= 2+2+2+1+1+1+L(0)
= 2+2+2+1+1+1+0
= 9.
Thanks to Computing Wisdom Solution.
Given the sequence S with n terms, the terryfied sequence increases to 3n terms with the terms defined by
S(n+k) = S(k)+1, S(2n+k) = S(k)+2 for 1 <= k <= n.
Note that the sequence first has length 1 with S(1) = 0,
and after each terryfication, its length is multiplied by 3.
So each terryfication defines a number of terms which is a power of 3.
So the 2012th term appears when the sequence grows from 729 terms to 2187.
So S(2012) = S(2729+554) = S(554) + 2 = S(2243+68) + 2 = S(68) + 2 + 2
= S(2*27+14) + 4 = S(14) + 2 + 4
= S(9+5) + 6 = S(5) + 1 + 6
= S(3+2) + 7 = S(2) + 8
= S(1+1) + 8 = S(1) + 1 + 8
= S(1) + 9 = 0 + 9 = 9
Thanks to Christopher Duff
