Rozważ dodatnie liczby całkowite równe pięciu w systemie dziesiętnym. Oto pierwsze 25, wyrównane do prawej:

 X                5^X
 1                  5
 2                 25
 3                125
 4                625
 5               3125
 6              15625
 7              78125
 8             390625
 9            1953125
10            9765625
11           48828125
12          244140625
13         1220703125
14         6103515625
15        30517578125
16       152587890625
17       762939453125
18      3814697265625
19     19073486328125
20     95367431640625
21    476837158203125
22   2384185791015625
23  11920928955078125
24  59604644775390625
25 298023223876953125

Zauważ, że prawa kolumna wszystkich praw znajduje się po prawej stronie 5. Druga kolumna po prawej to wszystko 2. Trzecia kolumna z prawej strony, czytane od góry do dołu, zastępców 1, 6, 1, 6, itd. Kolejna kolumna zaczyna 3, 5, 8, 0a następnie cykle.

W rzeczywistości każda kolumna (jeśli schodzimy wystarczająco daleko) ma sekwencję cykliczną cyfr, których długość jest dwa razy większa niż w poprzednim cyklu, z wyjątkiem cykli początkowych 5i 2cyklicznych.

Po wywołaniu N numeru kolumny, zaczynając od N = 1 po prawej stronie, pierwsze kilka cykli to:

N cycle at column N
1 5
2 2
3 16
4 3580
5 17956240
6 3978175584236200
7 19840377976181556439582242163600
8 4420183983595778219796176036355599756384380402237642416215818000

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą N, wypisz cyfry dziesiętne cyklu w kolumnie N, jak opisano powyżej. Na przykład wyjście dla N = 4 byłoby 3580.

Cyfry mogą być wyprowadzane jako lista taka jak [3, 5, 8, 0]lub w innym rozsądnym formacie, o ile:

• Cyfry są uporządkowane w kolejności od góry do dołu w kolumnach mocy. np. 0853jest nieprawidłowy.
• Cykl rozpoczyna się od najwyższej liczby w kolumnie mocy. np. 5803jest nieprawidłowy, ponieważ 4. kolumna zaczyna się od „ 3nie” 5.
• Dokładnie jeden cykl jest generowany. np. 358lub 35803lub 35803580wszystkie byłyby nieprawidłowe.

Twój kod musi działać przez co najmniej N = 1 do 30.

W razie potrzeby można założyć, że kolumny są indeksowane 0 zamiast 1 indeksowane. Więc N = 0 daje 5, N = 1 daje 2, N = 2 daje 16, N = 3 daje 3580itd.

Najkrótszy kod w bajtach wygrywa .

^{Dzięki Downgoat i DJ za wsparcie wyzwania.}

Python 2, 62 61 58 bajtów

Zero. Zakładam, że przyrostki L są dopuszczalne.

lambda n:[5**(n*3/7-~i)/2**n%10for i in range(2**n/2or 1)]

Wynik:

0 [5]
1 [2]
2 [1, 6]
3 [3, 5, 8, 0]
4 [1, 7, 9, 5, 6, 2, 4, 0]
5 [3, 9, 7, 8, 1, 7, 5, 5, 8, 4, 2, 3, 6, 2, 0, 0]
6 [1, 9, 8, 4, 0, 3, 7, 7, 9, 7, 6, 1, 8, 1, 5, 5, 6, 4, 3, 9, 5, 8, 2, 2, 4, 2L, 1L, 6L, 3
L, 6L, 0L, 0L]
7 [4, 4, 2, 0, 1, 8, 3, 9, 8, 3, 5, 9, 5, 7, 7, 8, 2, 1, 9, 7, 9, 6, 1, 7, 6L, 0L, 3L, 6L,
3L, 5L, 5L, 5L, 9L, 9L, 7L, 5L, 6L, 3L, 8L, 4L, 3L, 8L, 0L, 4L, 0L, 2L, 2L, 3L, 7L, 6L, 4L,
 2L, 4L, 1L, 6L, 2L, 1L, 5L, 8L, 1L, 8L, 0L, 0L, 0L]

Poprzednie rozwiązanie:

lambda n:[5**int(n/.7-~i)/10**n%10for i in range(2**n/2or 1)]
lambda n:[str(5**int(n/.7-~i))[~n]for i in range(2**n/2)]or 5

Wyjaśnienie:

def f(n):
    r = max(2**n / 2, 1)
    m = int(n/0.7 + 1)
    for i in range(r):
        yield (5**(m+i) / 10**n) % 10

range(2**n/2)Wykorzystuje spostrzeżenie, że każdy cykl ma długość r = 2 ^n-1 , z wyjątkiem, gdy n = 0, to po prostu obliczać cyfry n-tej do 5 ^m do 5 ^{m + n - 1} .

Początek cyklu 5 ^m jest pierwszą liczbą większą niż 10 ⁿ . Rozwiązanie 5 ^m ≥ 10 ⁿ daje m ≥ n / log ₁₀ 5. Tutaj przybliżamy log ₁₀ 5 ≈ 0,7, który rozkłada się, gdy n = 72. Możemy dodać więcej cyfr, aby zwiększyć dokładność:

| approximation             | valid until        | penalty   |
|---------------------------|--------------------|-----------|
| .7                        | n = 72             | +0 bytes  |
| .699                      | n = 137            | +2 bytes  |
| .69897                    | n = 9297           | +4 bytes  |
| .698970004                | n = 29384          | +8 bytes  |
| .6989700043               | n = 128326         | +9 bytes  |
| .6989700043360189         | too large to check | +15 bytes |
| import math;math.log10(5) | same as above      | +23 bytes |

W / 10**n % 10pętli po prostu wyodrębnij żądaną cyfrę. Inne alternatywne rozwiązanie wykorzystuje manipulację ciągiem. Użyłem tej sztuczki~n == -n-1 , aby usunąć 1 bajt.

Wspomniane w komentarzu wyrażenie 5**(m+i) / 10**nmożna jeszcze bardziej uprościć, co daje obecną 58-bajtową odpowiedź.

(Podziału x/2**nmożna dokonać za pomocą bitowego przesunięcia w prawo x>>n. Niestety, ze względu na pierwszeństwo operatora Pythona nie oszczędza to żadnych bajtów.) Ułamek 3/7 można również poprawić w podobnym mannar:

| approximation                   | valid until         | penalty   |
|---------------------------------|---------------------|-----------|
| n*3/7                           | n = 72              | +0 bytes  |
| n*31/72                         | n = 137             | +2 bytes  |
| n*59/137                        | n = 476             | +3 bytes  |
| n*351/815                       | n = 1154            | +4 bytes  |
| n*643/1493                      | n = 10790           | +5 bytes  |
| n*8651/20087                    | n = 49471           | +7 bytes  |
| int(n*.43067655807339306)       | too large to check  | +20 bytes |
| import math;int(n/math.log2(5)) | same as above       | +26 bytes |

dc , 72 bajty

[3Q]sq2?dsa^1+2/dsusk[Ola^/O%plk1-dsk1>q]sp1[d5r^dOla^<psz1+d4/lu>t]dstx

Indeksowanie na podstawie 0.

Wykorzystuje to dokładną arytmetykę liczb całkowitych - brak aproksymacji logarytmu. Będzie działać do pojemności pamięci komputera.

Wypróbuj program DC online!

Kod DC można przekształcić w rozwiązanie Bash:

Narzędzia Bash + GNU, 96 77 75 bajtów

u=$[(2**$1+1)/2]
dc -e "[O$1^/O%p]sp1[d5r^dO$1^<psz1+d4/$u>t]dstx"|head -$u

Wypróbuj wersję Bash online!

Mathematica, 66 60 52 bajtów

Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/.7]/10^#,10]&

Funkcja anonimowa, indeksowana 0. Wykorzystuje aproksymację log5 (10) (≈ 0,7)

Jak to działa?

Range@Max[2^#/2,1]

Weź większy z 2 ^ (dane wejściowe) / 2 i 1. Wygeneruj {1… ten numer}

...+#/.7

Dodaj wejście / .7

5^Floor[...]/10^#

Podnieś 5 do potęgi wyniku (moce generujące 5), podziel przez 10 ^ danych wejściowych (pozbywając się cyfr po prawej stronie żądanej kolumny)

Mod[ ...,10]

Zastosuj modulo 10, biorąc cyfrę jednej (żądaną kolumnę).

Dokładna wersja, 58 bajtów

Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/5~Log~10]/10^#,10]&

JavaScript (ES7), 78 76 bajtów

f=(N,z=5,s,X=2**N,q=z/10**N|0)=>s|q?X>0?q+f(N,z*5%10**-~N,1,X-2):"":f(N,z*5)

0-indeksowany, tzn . f(0)Daje 2.

Testowy fragment kodu

f=(N,z=5,s,X=1<<N,q=z/Math.pow(10,N)|0)=>s|q?X>0?q+f(N,z*5%Math.pow(10,-~N),1,X-2):"":f(N,z*5)

for (let i = 0; i < 10; i++) console.log(`f(${i}):`, f(i));

Fragment używa Math.powzamiast **kompatybilności z różnymi przeglądarkami.

CJam, 35

5ri(:N.7/i)#2N(#mo{_AN#/o5*AN)#%}*;

Wypróbuj online

Zajmuje mało miejsca i nie jest zbyt wolny, wejście danych 30 na moim komputerze zajęło kilka minut (używając interpretera Java).

Galaretka , 26 21 bajtów

-2 bajtów wykorzystujące kennytm za 0,7 aproksymacji pomysł

2*HĊR+÷.7$Ḟ*@5:⁵*⁸¤%⁵

Wypróbuj online! (przekroczony limit czasu dla n> 15 )

Zwraca listę liczb całkowitych, cyfr.
Zero oparty. Teoretycznie działa dla n <= 72 (zamiast .7z 5l⁵¤, aby uzyskać precyzję obliczeń zmiennoprzecinkowych).

W jaki sposób?

2*HĊR+÷.7$Ḟ*@5:⁵*⁸¤%⁵ - Main link: n
2*                    - 2 raised to the power of n
  H                   - halved: 2 raised to the power of n-1
   Ċ                  - ceiling: adjust 2**-1 = 0.5 up to 1 for the n=0 edge case
    R                 - range: [1,2,...,ceiling(2**(n-1))] - has length of the period
         $            - last two links as a monad:
      ÷.7             -     divide by 0.7 (approximation of log(5, 10), valid up to n=72)
     +                - add (vectorises)
          Ḟ           - floor (vectorises)
             5        - 5
           *@         - exponentiate (vectorises) with reversed @arguments
                  ¤   - nilad followed by link(s) as a nilad
               ⁵      -     10
                 ⁸    -     left argument, n
                *     -     exponentiate: 10 raised to the power of n
              :       - integer division: strips off last n digits
                   %⁵ - mod 10: extracts the last digit

Lokalnie: pamięć zestawu roboczego dla n = 17 wzrosła do około 750 MB, a następnie do około 1 GB ; dla n = 18 powoli osiągnął 2,5 GB, a następnie zwiększył się do około 5 GB .

Perl 6 , 52 bajtów

->\n{(map {.comb[*-n]//|()},(5 X**1..*))[^(2**n/4)]}

Działa dla dowolnie wysokich danych wejściowych, przy wystarczającej pamięci (tzn. Bez aproksymacji logarytmu) .
Zwraca listę cyfr.

Wypróbuj online!

Jak to działa

->\n{                                              }  # A lambda with argument n.
                            (5 X**1..*)               # The sequence 5, 25, 125, 625...
      map {               },                          # Transform each element as such:
           .comb[*-n]                                 #   Extract the n'th last digit,
                     //|()                            #   or skip it if that doesn't exist.
     (                                 )[^(2**n/4)]   # Return the first 2^(n-2) elements.

Część „pomijanie elementów” działa w następujący sposób:

• Indeksowanie listy pod niedozwolonym indeksem zwraca błąd , który liczy się jako „niezdefiniowana” wartość.
• // jest operatorem „zdefiniowanym lub”.
• |()zwraca pusty Slip , który rozpuszcza się na liście zewnętrznej jako 0 elementów, zasadniczo upewniając się, że bieżący element zostanie pominięty.

Przypadek brzegowy n=1działa dobrze, ponieważ 2**n/4staje się 0.5i ^(0.5)oznacza 0 ..^ 0.5aka „liczby całkowite od 0 (włącznie) do 0,5 (nie włącznie)”, tj. Lista z pojedynczym elementem 0.

J, 50 bajtów

(2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]

Uwaga: musi przejść w rozszerzonej liczbie

Stosowanie:

   q =: (2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]
   q 1x
5
   q 2x
2
   q 4x
3580

Haskell , 73 bajty

f 0="5"
f n=take(2^(n-1))[reverse x!!n|x<-show<$>iterate(*5)1,length x>n]

Wypróbuj online! Wykorzystuje indeksowanie 0.

Wyjaśnienie:

f 0="5"              -- if the input is 0, return "5"
f n=                 -- otherwise for input n
  take(2^(n-1))      -- return the first 2^(n-1) elements of the list
    [reverse x!!n    -- of the nth column of x
      |x<-show<$>    --    where x is the string representation
        iterate(*5)1 --    of the elements of the infinite list [5,25,125,...]
      ,length x>n    -- if x has at least n+1 columns
    ]                -- this yields a list of characters, which is equivalent to a string

Partia, 294 bajty

@echo off
if %1==1 echo 5
set/a"l=1<<%1-2,x=0,s=1
set t=
for /l %%i in (2,1,%1)do call set t=%%t%%x
:l
if %l%==0 exit/b
set t=%s%%t%
set s=
set c=
:d
set/ac+=%t:~,1%*5,r=c%%10,c/=10
set s=%s%%r%
set t=%t:~1%
if "%t%"=="" echo %r%&set/al-=1&goto l
if %c%%t:~,1%==0x goto l
goto d

Wysyła każdą cyfrę we własnym wierszu. Działa, obliczając moce 5 długodystansowych, ale działa tylko z N=33powodu 32-bitowych liczb całkowitych, aby śledzić liczbę cyfr do wydrukowania. szawiera (odwrócone) ostatnie Ncyfry bieżącej mocy 5, podczas gdy tzawiera xs używane jako wypełnienie, chociaż x=0powoduje, że obliczają je jako zero przy obliczaniu następnej mocy. Przykład dla N=4:

s   t
1   xxx (initial values before the first power of 5 is calculated)
5   xxx
52  xx
521 x
526 x
5213    (print 3)
5265    (print 5)
5218    (print 8)
5260    (print 0)

JavaScript (ES6), 73 bajty

1-indeksowany. Nieco krótszy niż odpowiedź ES7 , ale zawodzi 3 kroki wcześniej (przy N = 13).

n=>(g=x=>k>>n?'':(s=''+x*5%1e15)[n-1]?s.substr(-n,1)+g(s,k+=4):g(s))(k=1)

Próbny

let f =

n=>(g=x=>k>>n?'':(s=''+x*5%1e15)[n-1]?s.substr(-n,1)+g(s,k+=4):g(s))(k=1)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(4))
console.log(f(5))
console.log(f(6))
console.log(f(7))
console.log(f(8))

PHP> = 7,1, 104 bajtów

for($s=1;$i++<2**(-1+$a=$argn);)~($s=bcmul($s,5))[-$a]?$g.=$s[-$a]:0;echo substr($g,0,max(2**($a-2),1));

PHP Sandbox Online