Suma digital de Fibonacci

30

Todos estamos familiarizados con la secuencia de Fibonacci :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

Sin embargo, en lugar de, f(n) = f(n-1) + f(n-2)tomaremos la suma digital de las 2 entradas anteriores.


La secuencia aún debe comenzar 0, 1, después de eso, las diferencias son rápidamente aparentes. Esta lista está indexada a 0, puede usar también indexada a 1, estado que utilizó.

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: No noté la repetición hasta que publiqué el desafío en sí, y aquí estaba pensando que sería imposible escribir otro nuevo desafío de Fibonacci.


Su tarea es, dado un número n, generar el enésimo dígito de esta secuencia.

3 primeros dígitos: [0,1,1],

Patrón 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]

Sugerencia: puede aprovechar esta repetición para su ventaja.


Este es el , el conteo de bytes más bajo es el ganador.


BONIFICACIÓN: Si utiliza la repetición en su respuesta, otorgaré la respuesta de conteo de bytes más baja que aproveche la repetición en la secuencia de una recompensa de 100 puntos. Esto debe enviarse como parte de su respuesta original, después de su respuesta original. Vea esta publicación como un ejemplo de lo que estoy hablando: https://codegolf.stackexchange.com/a/108972/59376

Para calificar para este bono su código debe ejecutarse en tiempo constante ( O(1)) con una explicación.

Ganador de bonificación: Dennis https://codegolf.stackexchange.com/a/108967/59376 <Dennis ganó.

Implementación más exclusiva: https://codegolf.stackexchange.com/a/108970/59376
(También recibirá 100 puntos, finalizados después de elegir la respuesta correcta)

Urna de pulpo mágico
fuente
2
¿Podemos usar la indexación basada en 1 o tiene que estar basada en 0?
Business Cat
1
@BusinessCat sí, claro, que se joda.
Urna mágica del pulpo
1
¿Cómo se define aprovecha la repetición ? ¿Tiene que estar codificado o simplemente agrego una %24a una solución "normal"?
Dennis
1
@Dennis defino aprovechando la repetición para significar O(1). Su código debe ejecutarse en tiempo constante, si realmente está explotando la repetición.
Urna de pulpo mágico
1
@Dennis técnicamente% 24 en la entrada lo haría acotado en 27 iteraciones; mientras que, no es interesante, definitivamente cuenta.
Urna mágica de pulpo

Respuestas:

7

Oasis , 5 bytes

Código:

ScS+T

Pruébalo en línea!

Versión ampliada:

ScS+10

Explicación:

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
fuente
Oh hombre ... voy a empezar a aprender Oasis también.
Urna mágica del pulpo
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>

xy yno pueden ser ambos 9, ya que eso requeriría que fuera el número anterior 0, por lo que su suma digital no puede exceder 17. Esto significa que la raíz digital para números mayores que 9es la misma que el módulo restante 9.

Neil
fuente
66
Esto, esto también obtendrá una recompensa equivalente al líder de repetición ... Esta es una idea matemática increíble.
Urna mágica del pulpo
13

Python 2, 53 bytes

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

Función recursiva. Los casos base n=0y el n=1rendimiento n, los números más grandes calculan el valor llamando f(n-1)y f(n-2)convirtiendo cada uno en una cadena, concatenando las dos cadenas, convirtiendo cada carácter en un entero usando a mapcon la intfunción, y luego suma la lista resultante.


Usando la información del módulo 24, actualmente puedo obtener una función sin nombre no recursiva de 56 bytes:

lambda n:int(('011'+'2358dc7a89hhgfda56b8a9aa'*n)[n],18)
Jonathan Allan
fuente
1
¡Sí! ¡Tanto +1! Una respuesta de repetición :). ¡He agregado una sección de bonificación en su honor, señor, ahora es el líder en un concurso de recompensas de 100 puntos!
Urna mágica de pulpo
11

JavaScript (ES6), 34 bytes

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

Puede congelar su navegador para entradas superiores a 27, pero funciona para todos los valores de entrada. Esto se puede verificar con un simple caché:

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 se señaló en la brillante respuesta de Neil , la salida nunca puede exceder 17, por lo que la suma digital de cualquier salida superior a 9 es igual a n%9. Esto también funciona con salidas por debajo de 9; también podemos hacer que funcione para 9 restando 1 ~-antes del módulo y luego volviendo a agregar 1 después.


Lo mejor que puedo hacer con el hardcoding es 50 bytes:

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

Jalea , 8 bytes

;DFS
ç¡1

Pruébalo en línea!

Cómo 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.

Solución alternativa, 19 bytes, tiempo constante.

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

Pruébalo en línea!

Cómo 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
fuente
1
+1 para el chuzpe de "vamos a calcular toda la sección repetida en tiempo constante": D
Felix Dombek
4

JavaScript (ES6), 52 46 45 bytes

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

Uso

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

Salida

13

Explicación

Esta función verifica si la entrada es menor que 2, y si es así, devuelve la entrada. De lo contrario, crea una matriz de dos valores que se agregan entre sí como cadenas. Esos dos valores son el resultado de llamar a la función con input - 1y input - 2.

El ...operador divide esta cadena en una matriz de caracteres, que luego se convierte de nuevo en una cadena, pero ahora con +es entre valores. Esta cadena se interpreta como código, por lo que se calcula la suma, que luego se devuelve.

Este es un algoritmo de doble recursividad, lo que lo hace bastante ineficiente. Necesita 2 n-2llamadas de función para la entrada n. Como tal, aquí hay una solución más larga pero más rápida. Gracias a ETHproductions por proponerlo.

f=($,p=1,c=0)=>$?f($-1,c,eval([...p+[c]].join`+`)):c
Luke
fuente
Esto no funciona para grandes valores como 27, congela el navegador (al menos lo hace para mí)
Kritixi Lithos
Lleva algún tiempo, pero llegará allí ... eventualmente. Lo investigaré, pero el rendimiento no es importante para este desafío ...
Lucas
Bueno, Jesús, no es tan computacionalmente intenso, tu programa debería funcionar para valores más allá de 27 ... Pero si funciona para 1-28, eso técnicamente demuestra que funciona para niveles superiores.
Magic Octopus Urn
1
@KritixiLithos La recurrencia es el problema. Cálculo de la n ésimo número en la secuencia requiere aproximadamente 2 ^ (n-2) llamadas de función, que se acumula bastante rápidamente.
ETHproductions
Puede guardar un byte con [..._(--$)+[_(--$)]]:-)
ETHproductions
4

05AB1E , 8 bytes

XÎF‚¤sSO

Pruébalo en línea!

Explicación

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

CJam, 22 20 bytes

Guardado 2 bytes gracias a Martin Ender

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

Algoritmo recursivo directo, nada lujoso. 0 indexado.

Pruébalo en línea! o prueba para 0-50 (en realidad se ejecuta bastante rápido).

Explicación

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

Solución usando la repetición. Algoritmo similar a la solución de Jonathan Allan.

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

Pruébalo en línea!

Gato de negocios
fuente
3

Perl 6 ,  41  37 bytes

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

Intentalo

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

Intentalo

{ # 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
fuente
1
Puedes escribir el lambda interno como *.comb.sum+*.comb.sum.
sonríe
2

MATL , 15 bytes

lOi:"yyhFYAss]&

Pruébalo en línea!

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

C, 96 bytes

o 61 bytes contando códigos de escape como 1 byte cada uno

0 indexado. Similar a algunas de las otras respuestas, estoy indexando una tabla de búsqueda de valores, pero la he comprimido en fragmentos de 4 bytes. No me molesté en investigar la versión mod 24 porque no pensé que fuera tan interesante ya que los otros ya lo han hecho, pero seamos sinceros, C no va a ganar de todos modos.

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

explicación:

#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

Pruébalo en línea!

Ahemone
fuente
¡Cuento los códigos de escape como 1 byte cada uno! Gran trabajo
Albert Renshaw
2

Japt , 27 25 bytes

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

Pruébalo en línea!

Ahorró 2 bytes gracias a ETHproductions.

Tom
fuente
Hola, gracias por usar Japt :-) Puedes usarlo ´en lugar de --guardar dos bytes.
ETHproductions
2

Mathematica, 49 bytes

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

Definición recursiva directa. Se vuelve bastante lento después de un tiempo.

Mathematica, 79 71 bytes

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

Codificar el patrón periódico. Relámpago rápido y satisfactoriamente abusivo de Mathematica :) ¡ Gracias a JungHwan Min por guardar 8 bytes!

Greg Martin
fuente
Para su segundo código LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ"es 8 bytes más corto que 43626804920391712116157158790~IntegerDigits~18.
JungHwan Min
¡tienes razón! Voy a recordar uno de estos días LetterNumber...
Greg Martin
1

Python 2 , 56 bytes

Solución iterativa simple.

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

Pruébalo en línea!

El uso en (a%9or a)+(b%9or b)realidad resultó ser más corto que sum(map(int(`a`+`b`)))!

FlipTack
fuente
Creo que quieres decir sum(map(int,a+b))(no puedo entender cómo usar `en los comentarios)
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

Pruébalo en línea!

Solución iterativa larga y aburrida que realiza cálculos directos de suma de dígitos en cada forciclo. Al final del ciclo, el número que queremos está dentro $b, por lo que queda en la tubería y la salida está implícita. Tenga en cuenta que si la entrada es 0, entonces el bucle no entrará ya que el condicional es falso, por lo que $bpermanece 0.

AdmBorkBork
fuente
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%

Me preguntaba cómo iba a transferir mi respuesta de JavaScript al lote, pero la pista estaba en la solución Python de @ Dennis.

Neil
fuente
1

Pyth, 20 bytes

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

Un programa que toma la entrada de un entero indexado a cero e imprime el resultado.

Banco de pruebas (primera parte para formatear)

Cómo funciona

[Explicación más tarde]

TheBikingViking
fuente
1

Ruby, 58 bytes

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

La solución simple codificada.

GB
fuente
1

apilado , 40 bytes

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

Esta lambda es equivalente a la siguiente lambda:

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

Pruébalo en línea!

Conor O'Brien
fuente
1

Octava, 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
fuente
Bienvenido a ppcg! Bonito primer 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)

Invoque la función con f 123456789012345678901234567890123456789012345678, por ejemplo.

El código también funciona con índices muy grandes. Debido a la funcionalidad del módulo 24 implementado, es muy rápido.

El código descomprimido:

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

R, 90 bytes

Una solución horriblemente larga, pero es mejor que la 108 que tenía originalmente. Sospecho que hay una manera mucho mejor de hacer esto, pero no puedo verlo en este 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 es una función sin nombre que usa gsuby scan(t=divide los números del vector en dígitos. La suma de estos se agrega al vector mientras se suelta el primer elemento. repeatse utiliza para recorrer los ntiempos de secuencia y el resultado es el primer elemento del vector.

MickyT
fuente
0

PHP, 80 bytes

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

Versión en línea

Jörg Hülsermann
fuente
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
fuente