5, 2, 16, 3580, O que vem a seguir?

51

Considere as potências inteiras positivas de cinco em decimal. Aqui estão os 25 primeiros, alinhados à direita:

 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

Observe que a coluna mais à direita dos poderes é todos 5. A segunda coluna da direita é toda 2. A terceira coluna da direita, leia de cima para baixo, os suplentes 1, 6, 1, 6, etc. Os começos próxima coluna 3, 5, 8, 0e, em seguida ciclos.

De fato, toda coluna (se descermos o suficiente) tem uma sequência de dígitos com um ciclo cujo comprimento é duas vezes maior que o do ciclo anterior, exceto os ciclos inicial 5e final 2.

Chamando N o número da coluna, começando com N = 1 à direita, os primeiros ciclos são:

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

Desafio

Dado um número inteiro positivo N, insira os dígitos decimais do ciclo na coluna N, conforme descrito acima. Por exemplo, a saída para N = 4 seria 3580.

Os dígitos podem ser impressos como uma lista, como [3, 5, 8, 0]em outro formato razoável, desde que:

  • Os dígitos estão em ordem, conforme lidos de cima para baixo nas colunas de energia. por exemplo, 0853é inválido.
  • O ciclo começa com o número superior em sua coluna de potência. por exemplo, 5803é inválido, pois a quarta coluna começa com 3não 5.
  • Exatamente um ciclo é produzido. por exemplo, 358ou 35803ou 35803580todos seriam inválidos.

Seu código deve funcionar para pelo menos N = 1 a 30.

Se desejar, você pode assumir que as colunas são indexadas em 0 em vez de indexadas em 1. Então N = 0 dá 5, N = 1 dá 2, N = 2 dá 16, N = 3 dá 3580, etc.

O código mais curto em bytes vence .

Agradecimentos a Downgoat e DJ pelo suporte ao desafio.

Passatempos de Calvin
fonte
A ordem torna isso bastante complicado.
Dennis
9
A duração do ciclo é sempre, 2^(N-2)excetoN = 1
JungHwan Min 25/02
11
As aproximações podem ser usadas? A saída é válida até N = 72 , que teoricamente imprimiria 2,36E + 21 dígitos.
JungHwan Min
Essa sequência está no OEIS?
StarWeaver 26/02
@StarWeaver Não.
Mego

Respostas:

26

Python 2, 62 61 58 bytes

Baseado em zero. Presumo que os sufixos L sejam aceitáveis.

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

Resultado:

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]

Solução anterior:

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

Explicação:

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

A range(2**n/2)utiliza a observação de que cada ciclo tem comprimento r = 2 n-1 , excepto quando n = 0, por isso, apenas calcular os dígitos de ordem n para 5 m a 5 m + r - 1 .

O início do ciclo de 5 m é o primeiro número maior que 10 n . Resolver 5 m ≥ 10 n fornece m ≥ n / log 10 5. Aqui aproximamos o log 10 5 ≈ 0,7, que será quebrado quando n = 72. Poderíamos adicionar mais dígitos para aumentar a precisão:

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

O / 10**n % 10loop simplesmente extrai o dígito desejado. Outra solução alternativa usa manipulação de strings. Eu usei o truque~n == -n-1 aqui para remover 1 byte.

Como mencionado no comentário, a expressão 5**(m+i) / 10**npode ser ainda mais simplificada dessa maneira, o que fornece a resposta atual de 58 bytes.

insira a descrição da imagem aqui

(A divisão x/2**npode ser feita usando o deslocamento à direita bit a bit x>>n. Infelizmente, devido à precedência do operador do Python, isso não salva bytes.) A fração 3/7 também pode ser aprimorada em um mannar semelhante:

| 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 |
kennytm
fonte
11
(5**(n*3/7-~i)>>n)%10. Como você está usando um poder de 5 dividido por um poder (menor) de 10, pode reduzir o poder de 5 e alternar para a direita. n/.7 - nn*10/7 - nn*3/7. Em princípio, é extrair os dígitos da menor potência de 5 maior que 2ⁿ (com 3/7 uma aproximação para 1 / log₂ (5) ). Além disso, usar em range(2**n/2or 1)vez disso fornece uma saída consistente.
primo
11
@primo Obrigado, atualizado. (x>>n)%10não melhora, x/2**n%10então não uso o deslocamento de bits por enquanto, pois talvez haja uma maneira de fatorar o comum 2**n.
Kennytm
uma idéia interessante 2**n, mas parece um pouco mais longa: int(5**(-~i-n*log(2,5)%1))%10(simplifiquei int(n*log(2,5))-n*log(2,5)como -(n*log(2,5)%1)).
primo
@primo Interessante, mas o que quero dizer é o 2**nargumento aqui e o intervalo.
Kennytm
10

dc , 72 bytes

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

Indexação baseada em 0.

Isso usa aritmética inteira exata - sem aproximações de logaritmo. Ele funcionará até a capacidade de memória do computador.

Experimente o programa dc online!


O código dc pode ser transformado em uma solução Bash:

Utilitários Bash + GNU, 96 77 75 bytes

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

Experimente a versão online do Bash!

Mitchell Spector
fonte
9

Mathematica, 66 60 52 bytes

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

Função anônima, indexada em 0. Usa aproximação de log5 (10) (≈ 0,7)

Como funciona?

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

Utilize 2 ^ (entrada) / 2 e 1. Gere {1.. esse número}

...+#/.7

Adicionar entrada / .7

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

Eleve 5 à potência do resultado (gerando potências de 5), divida por 10 ^ de entrada (eliminando os dígitos à direita da coluna desejada)

Mod[ ...,10]

Aplique o módulo 10, utilizando o dígito da pessoa (a coluna desejada).

Versão exata, 58 bytes

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

JavaScript (ES7), 78 76 bytes

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 indexado, ou seja, f(0)2.

Snippet de teste

O snippet usa em Math.powvez de **para compatibilidade entre navegadores.

ETHproductions
fonte
4

CJam, 35

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

Experimente online

É eficiente em termos de espaço e não é extremamente lento, levou vários minutos para a entrada 30 no meu computador (usando o interpretador java).

aditsu
fonte
3

Geléia , 26 21 bytes

-2 bytes usando a ideia de aproximação de 0,7 do kennytm

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

Experimente online! (tempo limite excedido para n> 15 )

Retorna uma lista de números inteiros, os dígitos.
Baseado em zero. Teoricamente, trabalha para n <= 72 (substitua .7por 5l⁵¤, para obter precisão do ponto flutuante).

Quão?

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

Localmente: a memória do conjunto de trabalho para n = 17 subiu para cerca de 750 MB e subiu para cerca de 1 GB ; para n = 18 , alcançou lentamente 2,5 GB e aumentou para 5 GB .

Jonathan Allan
fonte
3

Perl 6 , 52 bytes

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

Funciona para entradas arbitrariamente altas, com memória suficiente (ou seja, sem aproximação do logaritmo) .
Retorna uma lista de dígitos.

Experimente online!

Como funciona

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

A parte "elemento pulando" funciona assim:

  • A indexação de uma lista em um índice ilegal retorna uma Falha , que conta como um valor "indefinido".
  • // é o operador "definido ou".
  • |()retorna um Slip vazio , que se dissolve na lista externa como 0 elementos, essencialmente garantindo que o elemento atual seja ignorado.

O caso de borda n=1funciona bem, porque 2**n/4se torna 0.5e ^(0.5)significa 0 ..^ 0.5aka "números inteiros entre 0 (inclusive) e 0,5 (não incluído)", ou seja, uma lista com o único elemento 0.

smls
fonte
2

J, 50 bytes

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

Nota: deve passar em número estendido

Uso:

   q =: (2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]
   q 1x
5
   q 2x
2
   q 4x
3580
ljeabmreosn
fonte
2
por que o voto negativo?
Ljeabmreosn
2

Haskell , 73 bytes

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

Experimente online! Usa indexação 0.

Explicação:

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
Laikoni
fonte
1

Lote, 294 bytes

@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

Produz cada dígito em sua própria linha. Funciona calculando as potências de 5 à mão, mas funciona apenas N=33devido ao uso de números inteiros de 32 bits para manter a contagem de quantos dígitos imprimir. scontém os últimos Ndígitos (invertidos) da potência atual de 5, enquanto tcontém xs usados ​​como preenchimento, embora os x=0façam avaliar como zero quando a próxima potência for calculada. Exemplo para 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)
Neil
fonte
1

JavaScript (ES6), 73 bytes

1 indexado. Um pouco mais curto que a resposta do ES7 , mas falha 3 etapas antes (em 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)

Demo

Arnauld
fonte
0

PHP> = 7.1, 104 bytes

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

Sandbox do PHP Online

Jörg Hülsermann
fonte