Рассмотрим положительные целые числа пяти в десятичной дроби. Вот первые 25, выровненные по правому краю:

 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

Обратите внимание, что самый правый столбец полномочий - это все 5. Во втором столбце справа все 2. Третий столбец справа, считываться сверху вниз, чередуется 1, 6, 1, 6и т.д. начинается следующий столбец 3, 5, 8, 0а затем циклы.

Фактически, каждый столбец (если мы зайдем достаточно далеко) имеет циклическую последовательность цифр, длина которой в два раза больше, чем в предыдущем цикле, за исключением начальных циклов 5s и 2s.

При вызове N номера столбца, начиная с N = 1 справа, первые несколько циклов:

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

Вызов

Учитывая положительное целое число N, выведите десятичные цифры цикла в столбце N, как описано выше. Например, вывод для N = 4 будет 3580.

Цифры могут быть выведены в виде списка, такого как [3, 5, 8, 0]или в другом приемлемом формате, если:

• Цифры расположены по порядку, как показано сверху вниз в столбцах питания. например 0853, неверно.
• Цикл начинается с верхнего числа в столбце мощности. Например 5803, недействительно, поскольку 4-й столбец начинается с 3not 5.
• Ровно один цикл выводится. например 358или 35803или 35803580все будут недействительными.

Ваш код должен работать как минимум от N = 1 до 30.

При желании вы можете предположить, что столбцы имеют индекс 0 вместо 1. Таким образом, N = 0 дает 5, N = 1 дает 2, N = 2 дает 16, N = 3 дает 3580и т.д.

Самый короткий код в байтах побеждает .

^{Спасибо Downgoat и DJ за поддержку в соревнованиях.}

Python 2, 62 61 58 байт

Нулевой основе. Я предполагаю, что суффиксы L приемлемы.

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

Выход:

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]

Предыдущее решение:

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

Объяснение:

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)Использует наблюдение , что каждый цикл имеет длину г = 2 ^п-1 , за исключением , когда п = 0, так что мы просто вычислить п-й цифру в течение 5 ^м до 5 ^{м + т - 1} .

Начало цикла 5 ^м - это первое число больше 10 ^н . Решение 5 ^m ≥ 10 ⁿ дает m ≥ n / log ₁₀ 5. Здесь мы приближаемся к log ₁₀ 5 ≈ 0,7, который сломается при n = 72. Мы могли бы добавить больше цифр для повышения точности:

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

В / 10**n % 10цикле просто извлечь нужную цифру. Другое альтернативное решение использует манипуляции со строками. Я использовал этот трюк,~n == -n-1 чтобы удалить 1 байт.

Упомянутое в комментарии, выражение 5**(m+i) / 10**nможет быть дополнительно упрощено таким образом, что дает текущий 58-байтовый ответ.

(Деление x/2**nможет быть выполнено с использованием побитового сдвига вправо x>>n. К сожалению, из-за приоритета оператора Python это не сохраняет никаких байтов.) Дробь 3/7 также может быть улучшена в аналогичном маннаре:

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

постоянный ток , 72 байта

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

Индексирование на основе 0.

При этом используется точная целочисленная арифметика - без логарифмических приближений. Это будет работать до объема памяти компьютера.

Попробуйте программу DC онлайн!

Код постоянного тока можно превратить в решение Bash:

Утилиты Bash + GNU, 96 77 75 байт

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

Попробуйте версию Bash онлайн!

Mathematica, 66 60 52 байта

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

Анонимная функция, 0-индексированная. Использует приближение log5 (10) (≈ 0,7)

Как это устроено?

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

Возьмите больше 2 ^ (вход) / 2 и 1. Сгенерируйте {1..that}

...+#/.7

Добавить вход / .7

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

Поднимите 5 до степени результата (генерируя степени 5), разделите на 10 ^ вход (избавляясь от цифр справа от нужного столбца)

Mod[ ...,10]

Применить по модулю 10, взяв одну цифру (нужный столбец).

Точная версия, 58 байт

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

JavaScript (ES7), 78 76 байт

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-индексируется, т.е. f(0)дает 2.

Тестовый фрагмент

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));

Фрагмент использует Math.powвместо **кросс-браузерной совместимости.

CJam, 35

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

Попробуйте онлайн

Он занимает мало места и не очень медленный, на ввод 30 на моем компьютере потребовалось несколько минут (с использованием интерпретатора Java).

Желе , 26 21 байт

-2 байта, используя идею приближения Кеннимма 0,7

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

Попробуйте онлайн! (время ожидания для n> 15 )

Возвращает список целых чисел, цифр.
Нулевой Теоретически работает при n <= 72 (замените .7на 5l⁵¤, чтобы получить точность с плавающей запятой).

Как?

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

Локально: память рабочего набора для n = 17 возросла до 750 МБ, а затем выросла до 1 ГБ ; для n = 18 он медленно достигал 2,5 ГБ, а затем достигал 5 ГБ .

Perl 6 , 52 байта

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

Работает для произвольно высоких входов, учитывая достаточную память (то есть без приближения логарифма) .
Возвращает список цифр.

Попробуйте онлайн!

Как это устроено

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

Часть "пропуск элемента" работает так:

• Индексирование списка по недопустимому индексу возвращает сбой , который считается как «неопределенное» значение.
• // является «определенным или» оператором.
• |()возвращает пустой Slip , который растворяется во внешнем списке в виде 0 элементов, по существу, гарантируя, что текущий элемент пропущен.

Крайний регистр n=1работает нормально, потому что 2**n/4становится 0.5и ^(0.5)означает 0 ..^ 0.5«целые числа от 0 (включительно) до 0,5 (не включительно)», то есть список с единственным элементом 0.

J, 50 байт

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

Примечание: должен пройти в расширенном номере

Использование:

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

Haskell , 73 байта

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

Попробуйте онлайн! Использует 0-индексацию.

Объяснение:

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

Пакетный, 294 байта

@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

Выводит каждую цифру в отдельной строке. Работает путем вычисления степеней 5 longhand, но работает только N=33из-за использования 32-разрядных целых чисел, чтобы вести подсчет количества цифр для печати. sсодержит (перевернутые) последние Nцифры текущей мощности 5, в то время как tсодержит xs, используемые в качестве дополнения, хотя x=0они заставляют их оценивать как ноль при расчете следующей мощности. Пример для 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 байта

1-индексироваться. Немного короче, чем ответ ES7 , но проваливается на 3 шага раньше (при 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)

демонстрация

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 байта

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