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(2*3^6+2*3^5+2*3^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 (2*3^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(2*3^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(2*729+554) = S(554) + 2 = S(2*243+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