Digital Sum Fibonacci

30

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

Urna de polvo mágico
fonte
2
Podemos usar a indexação baseada em 1 ou precisa ser baseada em 0?
Business Cat
1
@BusinessCat sim, claro, que se dane.
Magic Octopus Urn
1
Como você define tira proveito da repetição ? Ele precisa ser codificado ou apenas adiciono um %24a uma solução "normal"?
Dennis
1
@Dennis Defino aproveitar a repetição para significar O(1). Seu código deve estar em execução em tempo constante, se estiver realmente explorando a repetição.
Magic Octopus Urn
1
@Dennis tecnicamente% 24 na entrada o faria com limite superior em 27 iterações; enquanto, não é interessante, definitivamente conta.
Magic Octopus Urn

Respostas:

7

Oásis , 5 bytes

Código:

ScS+T

Experimente online!

Versão expandida:

ScS+10

Explicação:

ScS+   = a(n)
     0 = a(0)
    1  = a(1)
S      # Sum of digits on a(n-1)
 c     # Compute a(n-2)
  S    # Sum of digits
   +   # Add together
Adnan
fonte
Oh cara ... eu vou começar a aprender oásis também.
Magic Octopus Urn
28

JavaScript (ES6), 45 bytes

f=(n,x=0,y=1)=>n?f(n-1,y,(x%9||x)+(y%9||y)):x
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

xe ynão podem ser ambos 9, pois isso exigiria que o número anterior fosse 0, portanto, sua soma digital não pode exceder 17. Isso significa que a raiz digital para números maiores que 9é igual ao módulo restante 9.

Neil
fonte
6
Isso também terá uma recompensa equivalente ao líder da repetição ... Essa é uma visão matemática impressionante.
Magic Octopus Urn
13

Python 2, 53 bytes

f=lambda n:n>1and sum(map(int,`f(n-1)`+`f(n-2)`))or n

Função recursiva. Os casos básicos de n=0e n=1produzem nnúmeros maiores calculam o valor chamando f(n-1)e f(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 a mapcom a intfunçã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:

lambda n:int(('011'+'2358dc7a89hhgfda56b8a9aa'*n)[n],18)
Jonathan Allan
fonte
1
Sim! Tanto +1! Uma resposta de repetição :). Adicionei uma seção de bônus em sua homenagem, senhor, agora você é o líder em um concurso de recompensa de 100 pontos!
Magic Octopus Urn
11

JavaScript (ES6), 34 bytes

f=n=>n<2?n:~-f(--n)%9+~-f(--n)%9+2

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:

c=[];f=n=>n<2?n:c[n]=c[n]||~-f(--n)%9+~-f(--n)%9+2
<input type=number value=0 min=0 step=1 oninput="O.value=f(this.value)"> <input id=O value=0 disabled>

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:

n=>"0x"+"7880136ba5867ffedb834968"[n%24]-(n<3)*9+2
ETHproductions
fonte
6

Geléia , 8 bytes

;DFS
ç¡1

Experimente online!

Como funciona

ç¡1   Main link. No arguments. Implicit left argument: 0

  1   Set the right argument to 1.
ç¡    Repeatedly execute the helper link n times – where n is an integer read from
      STDIN – updating the left argument with the return value and the right
      argument with the previous value of the left argument. Yield the last result.


;DFS  Helper link. Arguments: a, b

;     Concatenate; yield [a, b].
 D    Decimal; convert both a and b to their base-10 digit arrays.
  F   Flatten the result.
   S  Compute the sum of the digits.

Solução alternativa, 19 bytes, tempo constante

;DFS
9⁵ç23С⁸ịµṠ>?2

Experimente online!

Como funciona

9⁵ç23С⁸ịµṠ>?2  Main link. Argument: n

9               Set the return value to 9
 ⁵              Yield 10.
  ç23С         Execute the helper link 23 times, with initial left argument 10
                and initial right argument 9, updating the arguments as before.
                Yield all intermediate results, returning
                [10,10,2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9].
   ⁸ị           Extract the element at index n. Indexing is 1-based and modular.
     µ          Combine all links to the left into a chain.
       >?2      If n > 2, execute the chain.
      Ṡ         Else, yield the sign if n.
Dennis
fonte
1
+1 para o chuzpe de "vamos calcular toda a seção repetida em tempo constante": D
Felix Dombek
4

JavaScript (ES6), 52 46 45 bytes

_=$=>$<2?$:eval([..._(--$)+[_(--$)]].join`+`)

Uso

_=$=>$<2?$:eval([..._(--$)+[_(--$)]].join`+`)
_(7)

Saída

13

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 - 1e input - 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-2chamadas de função para entrada n. Como tal, aqui está uma solução mais longa, mas mais rápida. Obrigado à ETHproductions por ter vindo com isso.

f=($,p=1,c=0)=>$?f($-1,c,eval([...p+[c]].join`+`)):c
Luke
fonte
Isso não funciona para grandes valores como 27, congela o navegador (pelo menos para mim)
Kritixi Lithos
Demora algum tempo, mas chegará lá ... eventualmente. Vou investigar, mas o desempenho não é importante para este desafio ...
Luke
Bem, Jesus, não é tão intenso computacionalmente, seu programa deve trabalhar para valores acima de 27 ... Mas se funcionar para 1-28, isso tecnicamente prova que funciona para valores mais altos.
Magic Octopus Urn
1
@KritixiLithos É a recursão que é o problema. Calculando a n th número na sequência requer cerca de 2 ^ (N-2) chamadas de função, que acumula-se bastante rapidamente.
ETHproduções
Você pode salvar um byte com [..._(--$)+[_(--$)]]:-)
ETHproductions
4

05AB1E , 8 bytes

XÎF‚¤sSO

Experimente online!

Explicação

XÎ        # push 1,0,input
  F       # input_no times do:
   ‚      # pair the top 2 elements of the stack
    ¤     # push a copy of the 2nd element to the stack
     s    # swap the pair to the top of the stack
      S   # convert to list of digits
       O  # sum
Emigna
fonte
3

CJam, 22 20 bytes

Economizou 2 bytes graças a Martin Ender

ri2,{(_(jAb\jAb+:+}j

Algoritmo recursivo direto, nada extravagante. Indexado a 0.

Experimente online! ou teste de 0 a 50 (na verdade, é muito rápido).

Explicação

ri                    Read an integer from input
  2,                  Push the array [0 1]
    {             }j  Recursive block, let's call it j(n), using the input as n and [0 1] as base cases
     (                 Decrement (n-1)
      _(               Duplicate and decrement again (n-2)
        jAb            Get the list digits of j(n-2)
           \           Swap the top two elements
            jAb        Get the list of digits of j(n-1)
               +       Concatenate the lists of digits
                :+     Sum the digits

CJam, 42 bytes

Solução usando a repetição. Algoritmo semelhante à solução de Jonathan Allan.

ri_2,1+"[2358DC7A89HHGFDA56B8A9AA]"S*~@*+=

Experimente online!

Gato de negócios
fonte
3

Perl 6 ,  41  37 bytes

{(0,1,{[+] |$^a.comb,|$^b.comb}...*)[$_]}

Tente

{(0,1,*.comb.sum+*.comb.sum...*)[$_]}

Tente

{ # bare block lambda with implicit parameter 「$_」
  (

    0, 1,           # first two values

    # WhateverCode lambda with two parameters ( the two 「*」 )
    *.comb.sum      # digital sum of first parameter
    +
    *.comb.sum      # digital sum of second parameter

    ...            # keep using that code object to generate new values until:

    *              # never stop

  )[ $_ ]          # index into the sequence
}
Brad Gilbert b2gills
fonte
1
Você pode escrever a lambda interna como *.comb.sum+*.comb.sum.
SMLS
2

MATL , 15 bytes

lOi:"yyhFYAss]&

Experimente online!

lO       % Push 1, then 0. So the next generated terms will be 1, 1, 2,... 
i        % Input n
:"       % Repeat that many times
  yy     %   Duplicate top two elements in the stack
  h      %   Concatenate into length-2 horizontal vector
  FYA    %   Convert to decimal digits. Gives a 2-row matrix
  ss     %   Sum of all matrix entries
]        % End
&        % Specify that next function (display) will take only 1 input
         % Implicit display
Luis Mendo
fonte
2

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.

#define a(n) n<3?!!n:2+(15&"\x1\x36\xba\x58\x67\xff\xed\xb8\x34\x96\x87\x88"[(n-3)/2%12]>>n%2*4)

explicação:

#define a(n)                                                                                     // using a preprocessor macro is shorter than defining a function
             n<3?!!n:                                                                            // when n is less than 3 !!n will give the series 0,1,1,1..., otherwise..
                                                                             (n-3)/2%12          // condition the input to correctly index the string...
                           "\x1\x36\xba\x58\x67\xff\xed\xb8\x34\x96\x87\x88"                     // which has the repeating part of the series encoded into 4 bits each number
                                                                                                 // these are encoded 2 less than what we want as all numbers in the series after the third are 2 <= a(n>2) <= 17 which conforms to 0 <= a(n>2) - 2 <= 15
                                                                                        >>n%2*4  // ensure the data is in the lower 4 bits by shifting it down, n%2 will give either 0 or 1, which is then multiplied by 4
                        15&                                                                      // mask those bits off
                     2+                                                                          // finally, add 2 to correct the numbers pulled from the string

Experimente online!

Ahemone
fonte
Eu conto os códigos de escape como 1 byte cada! Excelente trabalho
Albert Renshaw
2

Japonês , 27 25 bytes

U<2?U:~-ß´U %9+~-ß´U %9+2

Experimente online!

Economizou 2 bytes graças ao ETHproductions.

Tom
fonte
Ei, obrigado por usar o Japt :-) Você pode usar ´no lugar de --para salvar dois bytes.
ETHproductions
2

Haskell , 54 bytes

a!b=sum$read.pure<$>([a,b]>>=show)
g=0:scanl(!)1g
(g!!)

Experimente online! Uso:(g!!) 12

Laikoni
fonte
2

Mathematica, 49 bytes

If[#<2,#,Tr[Join@@IntegerDigits[#0/@{#-1,#-2}]]]&

Definição recursiva direta. Fica bem lento depois de um tempo.

Mathematica, 79 71 bytes

If[#<3,Sign@#,(9@@LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ")[[#~Mod~24]]]&

Codificar o padrão periódico. Rápido como um raio e satisfatoriamente abusivo para o Mathematica :) Obrigado a JungHwan Min por economizar 8 bytes!

Greg Martin
fonte
Para o seu segundo código, LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ"é 8 bytes menor que 43626804920391712116157158790~IntegerDigits~18.
JungHwan
você está certo! Um dia desses eu vou me lembrar LetterNumber....
Greg Martin
1

Python 2 , 56 bytes

Solução iterativa simples.

a,b=0,1
exec'a,b=b,(a%9or a)+(b%9or b);'*input()
print a

Experimente online!

Usando (a%9or a)+(b%9or b)realmente acabou por ser mais curto do que sum(map(int(`a`+`b`)))!

FlipTack
fonte
Eu acho que você quer dizer sum(map(int,a+b))(não consigo descobrir como usar `nos comentários)
1

PowerShell , 79 bytes

$b,$c=0,1;for($a=$args[0];$a;$a--){$z=[char[]]"$b$c"-join'+'|iex;$b=$c;$c=$z}$b

Experimente online!

Solução iterativa longa e chata que faz cálculos diretos de soma de dígitos a cada forloop. No final do loop, o número que queremos é o $bque fica no pipeline e a saída é implícita. Observe que, se a entrada for 0, o loop não entrará, pois o condicional é falso, e assim $bpermanece 0.

AdmBorkBork
fonte
1

Lote, 85 bytes

@set/ax=0,y=1
@for /l %%i in (1,1,%1)do @set/az=x-x/10*9+y-y/10*9,x=y,y=z
@echo %x%

Eu queria saber como eu portaria minha resposta JavaScript em lote, mas a pista estava na solução Python do @ Dennis.

Neil
fonte
1

Pitão, 20 bytes

J,01VQ=+JssjRT>2J)@J

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]

TheBikingViking
fonte
1

Ruby, 58 bytes

->n{n<3?n<=>0:"9aa2358dc7a89hhgfda56b8a"[n%24].to_i(18)}

A solução simples codificada.

GB
fonte
1

empilhados , 40 bytes

{!2:>[:$digitsflatmap sum\last\,]n*last}

Este lambda é equivalente ao seguinte lambda:

{n : 2:>[:$digitsflatmap sum\last\,]n*last}

Experimente online!

Conor O'Brien
fonte
1

Oitava, 148 bytes

function f = fib(n)
  if (n <= 1)
    f = n;
  else
    f = sum(int2str((fib(n - 1)))-48) + sum(int2str((fib(n - 2)))-48);
  endif
endfunction
Pitagora
fonte
Bem-vindo ao ppcg! Bom primeiro post!
Rɪᴋᴇʀ
1

Haskell, 151 bytes

import Numeric
import Data.Char
s i=foldr(\c i->i+digitToInt c)0$showInt i""
d a b=a:d b(s a+s b)
f 0=0
f 1=1
f 2=1
f i=d 2 3!!fromIntegral(mod(i-3)24)

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:

-- FibonacciDigital
-- Gerhard
-- 13 February 2017

module FibonacciDigital () where

import Numeric
import Data.Char

-- sum of digits
digitSum :: Int -> Int 
digitSum i = foldr (\c i -> i + digitToInt c) 0 $ showInt i ""

-- fibonacci digital sequence function with arbitrary starting values
fibonacciDigitals :: Int -> Int -> [Int]
fibonacciDigitals a b = a : fibonacciDigitals b (digitSum a + digitSum b)

-- index -> fibonacci digital value
f :: Integer -> Int 
f 0 = 0 
f 1 = 1 
f 2 = 1 
f i = fibonacciDigitals 2 3 !! fromIntegral (mod (i-3) 24) 

-- End
Gerhard
fonte
0

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.

function(n,x=0:1){repeat`if`(n,{x=c(x,sum(scan(t=gsub('',' ',x))))[-1];n=n-1},break);x[1]}

Esta é uma função sem nome que usa gsube scan(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 os ntempos de sequência e o resultado é o primeiro item do vetor.

MickyT
fonte
0

PHP, 80 bytes

for($r=[0,1];$i<$argn;)$r[]=array_sum(str_split($r[$i].$r[++$i]));echo$r[$argn];

Versão Online

Jörg Hülsermann
fonte
0

Mathematica, 67 bytes

r=IntegerDigits;f@0=0;f@1=1;f[x_]:=f@x=Tr@r@f[x-1]+Tr@r@f[x-2];f@#&
J42161217
fonte