# 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.

• The OEIS for this task is A147884 – Quixotic Mar 26 '11 at 6:36
• @Debanjan, yes true. @S.Mark, powers of 2, not 3. – st0le Mar 26 '11 at 6:55
• I have a paper, which describes an efficient algorithm. i'll post it if someone can't get move forward with it. – st0le Mar 26 '11 at 6:58
• ah, ok, thanks! – YOU Mar 26 '11 at 7:09
• @st0le:Complexity? – whacko__Cracko Mar 26 '11 at 7:38

## 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<=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

• Great job, Mark :) I guess you found it :) – st0le Mar 26 '11 at 12:00
• You can save a few bytes using semicolons: 161 bytes – movatica Aug 7 '19 at 17:23

# Wolfram Language (Mathematica), 787657 55 bytes

(x=0;While[Max@Abs[2IntegerDigits[2^++x,10,#]-3]>1];x)&


Try it online!

IntegerDigits[a,10,r] generates a list of the r last decimal digits of a. Subtract 3/2 and check that they are all either -1/2 or +1/2.

Timing check: 20 seconds on TIO for r = 1 .. 10.

# Wolfram Language (Mathematica), 1029591 89 bytes

k/.FindInstance[Mod[n=0;Nest[#+10^n(2-Mod[#/2^n++,2])&,0,#]-2^k,5^#]==0,k,Integers][]&


Try it online!

This solution is much longer but much faster. By taking the path suggested in OEIS A147884 to go via OEIS A053312, as well as using FindInstance magic, TIO manages to compute r = 1 .. 12 in less than a minute.

# Ruby - 118 chars

k,f,g,m=1,4,16
i=j=2
m=10**(n=gets.to_i)
((k+=f;j=j*g%m)until j.to_s=~%r{{#{i}}$};i+=1;f*=5;g=g**5%m)until n<i p k  ## Haskell, 115 characters import List main=readLn>>=print. \r->head$findIndices(all(elem"12").take r.(++cycle"0").reverse.show)$iterate(*2)1  # Python 3, 63 bytes f=lambda i,c=2:f(i,c+1)if{*str(2**c)[-i:]}-{*'12'}else c**(i>1)  Try it online! # 05AB1E, 18 15 bytes ∞.Δo©‹®I.£2X:P  Try it online or verify the first 8 test cases (any more times out). Explanation: Uses the fact that $$\2^x > r\$$ for all possible results, to ensure we have enough digits to get the last $$\r\$$ digits of $$\2^x\$$. ∞.Δ # Find the first positive integer x which is truthy (==1) for: o # Take 2 to the power the integer: 2^x © # Store it in variable ® (without popping) ‹ # Check that it's larger than the (implicit) input: r < 2^x # (1 if truhy; 0 if falsey) ® # Push variable ® again: 2^x I.£ # Only leave the last input amount of digits 2X: # Replace all 2s with 1s  # Push all digits separated to the stack P # Take the product of all digits on the stack (including the earlier check) # (NOTE: Only 1 is truthy in 05AB1E)  ### CSharp - 111 chars int a(int r){int x=1;a:x++;foreach(var c in Math.Pow(2,x)%Math.Pow(10,r)+"")if(c!='1'&&c!='2')goto a;return x;}  # Perl 5-Mbigint -p, 33 bytes 1while($a=2**++$\)!~/{$_}\$/}{


Try it online!

# Julia133 122 (51) bytes

n->(k=1;f=4;g=big(16);i=j=2;m=10^n;while i<=n;while digits!(fill(0,i),j)⊈1:2;j,k=j*g%m,k+f;end;i,g,f=i+1,g^5%m,f*5end;k)

f(r,x=big(1))=digits!(fill(0,r),x)⊈1:2&&f(r,2x)+1