Todos nós estamos familiarizados com a sequência de Fibonacci :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
No entanto, em vez de, f(n) = f(n-1) + f(n-2)
tomaremos a soma digital das 2 entradas anteriores.
A sequência ainda deve começar 0, 1
, depois que as diferenças são rapidamente aparentes. Esta lista é indexada em 0; você também pode usar a indexação em 1, indicando o estado que usou.
f(0) = 0
f(1) = 1
f(2) = 1 # 0 + 1
f(3) = 2 # 1 + 1
f(4) = 3 # 1 + 2
f(5) = 5 # 2 + 3
f(6) = 8 # 3 + 5
f(7) = 13 # 8 + 5
f(8) = 12 # 8 + 1 + 3
f(9) = 7 # 1 + 3 + 1 + 2
f(10) = 10 # 1 + 2 + 7
f(11) = 8 # 7 + 1 + 0
f(12) = 9 # 1 + 0 + 8
f(13) = 17 # 8 + 9
f(14) = 17 # 9 + 1 + 7
f(15) = 16 # 1 + 7 + 1 + 7
f(16) = 15 # 1 + 7 + 1 + 6
f(17) = 13 # 1 + 6 + 1 + 5
f(18) = 10 # 1 + 5 + 1 + 3
f(19) = 5 # 1 + 3 + 1 + 0
f(20) = 6 # 1 + 0 + 5
f(21) = 11 # 5 + 6
f(22) = 8 # 6 + 1 + 1
f(23) = 10 # 1 + 1 + 8
f(24) = 9 # 8 + 1 + 0
f(25) = 10 # 1 + 0 + 9
f(26) = 10 # 9 + 1 + 0
f(27) = 2 # 1 + 0 + 1 + 0
(After this point it repeats at the 3rd term, 0-indexed)
Nota: Eu não notei a repetição até postar o desafio em si, e aqui estava pensando que seria impossível escrever outro novo desafio de Fibonacci.
Sua tarefa é, com um número n
, gerar o enésimo dígito dessa sequência.
3 primeiros dígitos: [0,1,1]
,
Padrão repetido de 24 dígitos: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]
Dica: você pode explorar essa repetição para sua vantagem.
Este é o código-golfe , o menor número de bytes é o vencedor.
BÔNUS: Se você usar a repetição em sua resposta, atribuirei à resposta de contagem de bytes mais baixa que aproveita a repetição na sequência uma recompensa de 100 pontos. Isso deve ser enviado como parte da sua resposta original, depois da resposta original. Veja este post como um exemplo do que estou falando: https://codegolf.stackexchange.com/a/108972/59376
Para se qualificar para esse bônus, seu código deve ser executado em tempo constante ( O(1)
) com uma explicação.
Vencedor do bônus: Dennis https://codegolf.stackexchange.com/a/108967/59376 <Dennis venceu.
Implementação mais exclusiva: https://codegolf.stackexchange.com/a/108970/59376
(Também receberá 100 pontos, finalizados após a escolha da resposta correta)
fonte
%24
a uma solução "normal"?O(1)
. Seu código deve estar em execução em tempo constante, se estiver realmente explorando a repetição.Respostas:
Oásis , 5 bytes
Código:
Experimente online!
Versão expandida:
Explicação:
fonte
JavaScript (ES6), 45 bytes
x
ey
não podem ser ambos9
, pois isso exigiria que o número anterior fosse0
, portanto, sua soma digital não pode exceder17
. Isso significa que a raiz digital para números maiores que9
é igual ao módulo restante9
.fonte
Python 2, 53 bytes
Função recursiva. Os casos básicos de
n=0
en=1
produzemn
números maiores calculam o valor chamandof(n-1)
ef(n-2)
convertendo cada um em uma seqüência de caracteres, concatenando as duas seqüências, convertendo cada caractere em um número inteiro usando amap
com aint
função e, em seguida, soma a lista resultante.Usando as informações do módulo 24, atualmente posso obter uma função sem nome não recursiva de 56 bytes:
fonte
JavaScript (ES6), 34 bytes
Pode congelar o navegador para entradas acima de 27 ou mais, mas funciona para todos os valores de entrada. Isso pode ser verificado com um cache simples:
Como apontado na brilhante resposta de Neil , a saída nunca pode exceder 17, portanto a soma digital de qualquer saída acima de 9 é igual a
n%9
. Isso também funciona com saídas abaixo de 9; podemos fazê-lo funcionar para 9, subtraindo 1 com~-
antes do módulo e adicionando novamente 1 depois.O melhor que eu poderia fazer com a codificação codificada é de 50 bytes:
fonte
Geléia , 8 bytes
Experimente online!
Como funciona
Solução alternativa, 19 bytes, tempo constante
Experimente online!
Como funciona
fonte
JavaScript (ES6),
52 4645 bytesUso
Saída
Explicação
Esta função verifica se a entrada é menor que 2 e, se houver, retorna a entrada. Caso contrário, ele cria uma matriz de dois valores que são anexados um ao outro como seqüências de caracteres. Esses dois valores são o resultado de chamar a função com
input - 1
einput - 2
.O
...
operador divide essa sequência em uma matriz de caracteres, que depois é convertida em uma sequência novamente, mas agora com+
es entre os valores. Essa sequência é então interpretada como código, portanto, a soma é calculada, que é retornada.Este é um algoritmo de dupla recursividade, o que o torna bastante ineficiente. Ele precisa de 2
n-2
chamadas de função para entradan
. Como tal, aqui está uma solução mais longa, mas mais rápida. Obrigado à ETHproductions por ter vindo com isso.fonte
[..._(--$)+[_(--$)]]
:-)05AB1E , 8 bytes
Experimente online!
Explicação
fonte
CJam,
2220 bytesEconomizou 2 bytes graças a Martin Ender
Algoritmo recursivo direto, nada extravagante. Indexado a 0.
Experimente online! ou teste de 0 a 50 (na verdade, é muito rápido).
Explicação
CJam, 42 bytes
Solução usando a repetição. Algoritmo semelhante à solução de Jonathan Allan.
Experimente online!
fonte
Perl 6 ,
4137 bytesTente
Tente
fonte
*.comb.sum+*.comb.sum
.MATL , 15 bytes
Experimente online!
fonte
Python 2 ,
5446 bytesMuito inspirado na resposta ES6 da @ETHproductions .
Experimente online!
fonte
C, 96 bytes
ou 61 bytes contando códigos de escape como 1 byte cada
0 indexado. Semelhante a algumas das outras respostas, estou indexando uma tabela de valores de pesquisa, mas a comprimi em pedaços de 4 bytes. Eu não me incomodei em investigar a versão mod 24 porque não achei tão interessante, pois os outros já o fizeram, mas vamos ser sinceros, C não vai ganhar de qualquer maneira.
explicação:
Experimente online!
fonte
Japonês ,
2725 bytesExperimente online!
Economizou 2 bytes graças ao ETHproductions.
fonte
´
no lugar de--
para salvar dois bytes.Haskell , 54 bytes
Experimente online! Uso:
(g!!) 12
fonte
Mathematica, 49 bytes
Definição recursiva direta. Fica bem lento depois de um tempo.
Mathematica,
7971 bytesCodificar o padrão periódico. Rápido como um raio e satisfatoriamente abusivo para o Mathematica :) Obrigado a JungHwan Min por economizar 8 bytes!
fonte
LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ"
é 8 bytes menor que43626804920391712116157158790~IntegerDigits~18
.LetterNumber
....Python 2 , 56 bytes
Solução iterativa simples.
Experimente online!
Usando
(a%9or a)+(b%9or b)
realmente acabou por ser mais curto do quesum(map(int(`a`+`b`)))
!fonte
sum(map(int,a+b))
(não consigo descobrir como usar `nos comentários)PowerShell , 79 bytes
Experimente online!
Solução iterativa longa e chata que faz cálculos diretos de soma de dígitos a cada
for
loop. No final do loop, o número que queremos é o$b
que fica no pipeline e a saída é implícita. Observe que, se a entrada for0
, o loop não entrará, pois o condicional é falso, e assim$b
permanece0
.fonte
Lote, 85 bytes
Eu queria saber como eu portaria minha resposta JavaScript em lote, mas a pista estava na solução Python do @ Dennis.
fonte
Pitão, 20 bytes
Um programa que recebe a entrada de um número inteiro indexado a zero e imprime o resultado.
Conjunto de testes (primeira parte para formatação)
Como funciona
[Explicação que vem depois]
fonte
Ruby, 58 bytes
A solução simples codificada.
fonte
empilhados , 40 bytes
Este lambda é equivalente ao seguinte lambda:
Experimente online!
fonte
Oitava, 148 bytes
fonte
Haskell, 151 bytes
Chame a função com
f 123456789012345678901234567890123456789012345678
, por exemplo.O código também funciona com índices muito grandes. Devido à funcionalidade implementada do módulo 24, é muito rápido.
O código não compactado:
fonte
R, 90 bytes
Uma solução horrivelmente longa, mas é melhor que as 108 que eu tinha originalmente. Suspeito que exista uma maneira muito melhor de fazer isso, mas não posso vê-lo no momento.
Esta é uma função sem nome que usa
gsub
escan(t=
para dividir os números no vetor em dígitos. A soma destes é adicionada ao vetor enquanto o primeiro item é descartado.repeat
é usado para percorrer osn
tempos de sequência e o resultado é o primeiro item do vetor.fonte
PHP, 80 bytes
Versão Online
fonte
Mathematica, 67 bytes
fonte