16
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ Great job, Mark :) I guess you found it :) \$\endgroup\$ – st0le Mar 26 '11 at 12:00
  • \$\begingroup\$ You can save a few bytes using semicolons: 161 bytes \$\endgroup\$ – movatica Aug 7 at 17:23
2
\$\begingroup\$

Wolfram Language (Mathematica), 78 76 57 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), 102 95 91 89 bytes

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

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.

\$\endgroup\$
1
\$\begingroup\$

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{[12]{#{i}}$};i+=1;f*=5;g=g**5%m)until n<i
p k
\$\endgroup\$
1
\$\begingroup\$

Haskell, 115 characters

import List
main=readLn>>=print. \r->head$findIndices(all(`elem`"12").take r.(++cycle"0").reverse.show)$iterate(*2)1
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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;}
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -Mbigint -p, 33 bytes

1while($a=2**++$\)!~/[12]{$_}$/}{

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Julia 133 122 (51) bytes

Inspired by YOU's answer:

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)

Try it online!

The following is much shorter, but it crashes for r > 8, like some of the other answers:

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.