It is a classic dp problem. Define dp(x,y,i) as the number of ways to get a number, which ends in ...xy and has i digits i.e. its last two digits are x and y, with the properties you said. Now, you can easily get the answer. For example, dp(1,2,n) = dp(1,1,n — 1) + dp(2, 1, n — 1). (Think about it, it is not that hard). Finally, the answer will be sum of dp(x,y,n) where x and y are numbers from 1 to 3.