Last k digits of Powers of 2 For any integer \$r\$, there exists a
power of 2 each of whose last \$r\$ digits
are either 1 or 2.

Given \$r\$, find the smallest \$x\$ such that \$2^x\bmod{10^r}\$ consists of only 1 or 2.
For \$r=2\$, \$x=9\$, since \$2^9=5\color{blue}{\textrm{12}}\$
For \$r=3\$, \$x=89\$, since \$2^{89}=618970019642690137449562\color{blue}{\textrm{112}}\$
Note: for \$r=4\$, \$x\$ is \$=89\$ (again)
Input : \$r \leq 100\$
Output : \$x\$
Eg.

Input : 2
Ouput : 9
Input : 3
Ouput : 89

The program should run in a reasonable amount of time.
EDIT: The oeis sequence for this challenge is A147884.
Python, 166 chars

k,f,g=1,4,16
i=j=2
n=input()
m=10**n
a=lambda c:c('')-1-i or c('1')+c('2')-c('')+1
while i&lt;=n:
 while a(str(j)[-i:].count):j,k=j*g%m,k+f
 i,g,f=i+1,g**5%m,f*5
print k