Ostatnie k cyfr Mocy 2

16

Dla dowolnej liczby całkowitej r istnieje potęga 2, z których każda z ostatnich cyfr r ma wartość 1 lub 2.

Biorąc pod uwagę r , znajdź najmniejszą x taką, że 2xmod10r składa się tylko z 1 lub 2.

Dla r=2 , x=9 , ponieważ 29=512
Dla r=3 , x=89 , ponieważ 289=618970019642690137449562112
Uwaga: dla r=4 , x wynosi =89 (ponownie)

Dane wejściowe: r100

Wyjście: x

Na przykład.

Wejście: 2
Ouput: 9

Wejście: 3
Ouput: 89

Program powinien działać w rozsądnym czasie.

EDYCJA: Sekwencja Oeis dla tego wyzwania to A147884 .

st0le
źródło
2
OEIS dla tego zadania to A147884
Quixotic
@Debanjan, tak prawda. @ S.Mark, potęgi 2, a nie 3.
st0le
Mam artykuł opisujący wydajny algorytm. opublikuję go, jeśli ktoś nie będzie mógł przejść z tym naprzód.
st0le
ah, ok, dzięki!
TY
@ st0le: Złożoność?
whacko__Cracko

Odpowiedzi:

4

Python, 166 znaków

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
TY
źródło
Świetna robota, Mark :) Myślę, że ją znalazłeś :)
st0le
Możesz zapisać kilka bajtów za pomocą średników: 161 bajtów
movatica
2

Wolfram Language (Mathematica) , 78 76 57 55 bajtów

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

Wypróbuj online!

IntegerDigits[a,10,r] generuje listę r ostatnich cyfr dziesiętnych z a. Odejmij 3/2 i sprawdź, czy wszystkie mają wartość -1/2 lub +1/2.

Kontrola czasu: 20 sekund w TIO na r = 1 .. 10 .

Wolfram Language (Mathematica) , 102 95 91 89 bajtów

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

Wypróbuj online!

To rozwiązanie jest znacznie dłuższe, ale znacznie szybsze. Wybierając ścieżkę sugerowaną w OEIS A147884, aby przejść przez OEIS A053312 , a także używając FindInstancemagii, TIO udaje się obliczyć r = 1 .. 12w mniej niż minutę.

rzymski
źródło
1

Rubin - 118 znaków

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
Dogbert
źródło
1

Haskell, 115 znaków

import List
main=readLn>>=print. \r->head$findIndices(all(`elem`"12").take r.(++cycle"0").reverse.show)$iterate(*2)1
Thomas Eding
źródło
1

05AB1E , 18 15 bajtów

∞.Δo©‹®I.£2X:`P

Wypróbuj online lub sprawdź pierwsze 8 przypadków testowych (więcej razy).

Wyjaśnienie:

2x>rr2x

∞.Δ            # 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)
Kevin Cruijssen
źródło
0

CSharp - 111 znaków

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;}
Obrabować
źródło
0

Julia 133 122 (51) bajtów

Zainspirowany odpowiedzią:

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)

Wypróbuj online!

Poniższe jest znacznie krótsze, ale zawiesza się dla r> 8, podobnie jak niektóre inne odpowiedzi:

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

Wypróbuj online!

użytkownik3263164
źródło