Wszyscy znamy sekwencję Fibonacciego :

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

Zamiast tego f(n) = f(n-1) + f(n-2)weźmiemy cyfrową sumę poprzednich 2 wpisów.

Sekwencja powinna zacząć się od tego 0, 1, po czym różnice są szybko widoczne. Ta lista jest indeksowana na 0, możesz również użyć indeksowania 1, którego użyłeś.

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)

Uwaga: nie zauważyłem powtórzenia, dopóki nie opublikowałem samego wyzwania, a tutaj myślałem, że nie będzie możliwe napisanie kolejnej powieści Fibonacciego.

Twoim zadaniem jest, biorąc pod uwagę liczbę n, wyprowadzenie n-tej cyfry tej sekwencji.

3 pierwsze cyfry: [0,1,1],

24-cyfrowy powtarzalny wzór: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]

Wskazówka: Być może będziesz w stanie wykorzystać to powtórzenie na swoją korzyść.

To jest golf golfowy , zwycięzcą jest najniższa liczba bajtów.

BONUS: Jeśli użyjesz powtórzenia w swojej odpowiedzi, przyznam odpowiedź o najniższej liczbie bajtów, która korzysta z powtórzenia w sekwencji, nagrodę 100 punktów. Należy ją przesłać jako część oryginalnej odpowiedzi, po oryginalnej odpowiedzi. Zobacz ten post jako przykład tego, o czym mówię: https://codegolf.stackexchange.com/a/108972/59376

Aby zakwalifikować się do tej premii, Twój kod musi działać w stałym czasie ( O(1)) z wyjaśnieniem.

Zwycięzca bonusowy: Dennis https://codegolf.stackexchange.com/a/108967/59376 <Dennis wygrał.

Najbardziej wyjątkowa implementacja: https://codegolf.stackexchange.com/a/108970/59376
( Otrzyma również 100 punktów, sfinalizowane po wybraniu poprawnej odpowiedzi)

Oaza , 5 bajtów

Kod:

ScS+T

Wypróbuj online!

Wersja rozszerzona:

ScS+10

Wyjaśnienie:

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

JavaScript (ES6), 45 bajtów

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>

xi ynie mogą być oba 9, ponieważ wymagałoby to poprzedniego numeru 0, więc ich suma cyfrowa nie może przekroczyć 17. Oznacza to, że cyfrowy pierwiastek dla liczb większych niż 9jest taki sam, jak reszta modulo 9.

Python 2, 53 bajty

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

Funkcja rekurencyjna. Przypadki bazowe n=0i n=1wydajności n, większej liczby oblicza wartość wywołując f(n-1)i f(n-2)konwersji do każdego ciągu, łącząc dwa łańcuchy, przekształcając każdy znak na całkowitą użyciem mapz intfunkcji, a następnie sumuje otrzymaną listą.

Korzystając z informacji modulo-24, mogę obecnie uzyskać 56-bajtową nierekurencyjną funkcję bez nazwy:

lambda n:int(('011'+'2358dc7a89hhgfda56b8a9aa'*n)[n],18)

JavaScript (ES6), 34 bajty

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

Może zamrozić przeglądarkę dla danych wejściowych powyżej 27 lub więcej, ale działa dla wszystkich wartości wejściowych. Można to zweryfikować za pomocą prostej pamięci podręcznej:

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>

Jak wskazano w genialnej odpowiedzi Neila , wyjście nigdy nie może przekroczyć 17, więc suma cyfrowa dowolnego wyjścia powyżej 9 jest równa n%9. Działa to również z wyjściami poniżej 9; możemy sprawić, że będzie działał również dla 9, odejmując 1 z ~-przed modułem, a następnie dodając z powrotem 1 po.

Najlepsze, co mogę zrobić z kodowaniem na twardo, to 50 bajtów:

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

Galaretka , 8 bajtów

;DFS
ç¡1

Wypróbuj online!

Jak to działa

ç¡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.

Alternatywne rozwiązanie, 19 bajtów, stały czas

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

Wypróbuj online!

Jak to działa

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.

JavaScript (ES6), 52 46 45 bajtów

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

Stosowanie

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

Wydajność

13

Wyjaśnienie

Ta funkcja sprawdza, czy dane wejściowe są mniejsze niż 2, a jeśli tak, zwraca dane wejściowe. W przeciwnym razie tworzy tablicę dwóch wartości, które są dołączane do siebie jako ciągi znaków. Te dwie wartości są wynikiem wywołania funkcji za pomocą input - 1i input - 2.

...Operatora dzieli to ciąg znaków w postaci tablicy, która jest następnie jest przekształcona do łańcucha ponownie, ale teraz z +es pomiędzy wartościami. Ten ciąg jest następnie interpretowany jako kod, więc suma jest obliczana, a następnie zwracana.

Jest to algorytm podwójnie rekurencyjny, co czyni go dość nieefektywnym. Do wprowadzenia potrzeba 2 ^n-2wywołań funkcji n. Jako takie, oto dłuższe, ale szybsze rozwiązanie. Dzięki ETHproductions za wymyślenie tego.

f=($,p=1,c=0)=>$?f($-1,c,eval([...p+[c]].join`+`)):c

05AB1E , 8 bajtów

XÎF‚¤sSO

Wypróbuj online!

Wyjaśnienie

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

CJam, 22 20 bajtów

Zaoszczędzono 2 bajty dzięki Martinowi Enderowi

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

Prosty algorytm rekurencyjny, nic szczególnego. 0-indeksowane.

Wypróbuj online! lub test na 0-50 (faktycznie działa dość szybko).

Wyjaśnienie

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 bajty

Rozwiązanie wykorzystujące powtórzenie. Algorytm podobny do rozwiązania Jonathana Allana.

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

Wypróbuj online!

Perl 6 ,  41  37 bajtów

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

Spróbuj

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

Spróbuj

{ # 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
}

MATL , 15 bajtów

lOi:"yyhFYAss]&

Wypróbuj 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

Python 2 , 54 46 bajtów

f=lambda n:n>2and~-f(n-1)%9+~-f(n-2)%9+2or n>0

Mocno zainspirowany odpowiedzią ESET @ETHproductions .

Wypróbuj online!

C, 96 bajtów

lub 61 bajtów liczących kody ucieczki jako 1 bajt każdy

0 zindeksowanych. Podobnie do niektórych innych odpowiedzi indeksuję tabelę wartości, ale skompresowałem ją do 4-bajtowych porcji. Nie zawracałem sobie głowy badaniem wersji mod 24, ponieważ nie sądziłem, że jest tak interesująca, ponieważ inni już to zrobili, ale spójrzmy prawdzie w oczy, C i tak nie wygra.

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

wyjaśnienie:

#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

Wypróbuj online!

Japt , 27 25 bajtów

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

Wypróbuj online!

Zaoszczędzono 2 bajty dzięki produktom ETH.

Haskell , 54 bajty

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

Wypróbuj online! Stosowanie:(g!!) 12

Mathematica, 49 bajtów

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

Prosta definicja rekurencyjna. Po chwili robi się dość wolny.

Mathematica, 79 71 bajtów

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

Twarde kodowanie wzoru okresowego. Błyskawicznie i satysfakcjonująco obraźliwe dla Mathematiki :) Dzięki JungHwan Min za oszczędność 8 bajtów!

Python 2 , 56 bajtów

Proste iteracyjne rozwiązanie.

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

Wypróbuj online!

Używanie (a%9or a)+(b%9or b)okazało się być krótsze niż sum(map(int(`a`+`b`)))!

PowerShell , 79 bajtów

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

Wypróbuj online!

Długie nudne iteracyjne rozwiązanie, które wykonuje bezpośrednie obliczenia sumy cyfr w każdej forpętli. Na końcu pętli potrzebna jest liczba $b, więc pozostaje ona w potoku, a dane wyjściowe są niejawne. Zauważ, że jeśli wejście jest 0, wtedy pętla nie wejdzie, ponieważ warunek jest fałszywy, więc $bpozostaje 0.

Partia, 85 bajtów

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

Zastanawiałem się, jak przenieść moją odpowiedź JavaScript na partię, ale wskazówka była w rozwiązaniu Python @ Dennisa.

Pyth, 20 bajtów

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

Program, który pobiera liczbę całkowitą zerową i wypisuje wynik.

Zestaw testowy (pierwsza część do formatowania)

Jak to działa

[Wyjaśnienie nastąpi później]

Rubinowy, 58 bajtów

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

Proste zakodowane rozwiązanie.

ułożone w stos , 40 bajtów

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

Ta lambda jest równoważna następującej lambda:

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

Wypróbuj online!

Oktawa, 148 bajtów

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

Haskell, 151 bajtów

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)

Wywołaj funkcję f 123456789012345678901234567890123456789012345678na przykład za pomocą.

Kod działa również z bardzo dużymi indeksami. Dzięki zaimplementowanej funkcjonalności modulo 24 jest bardzo szybki.

Nieskompresowany kod:

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

R, 90 bajtów

Strasznie długie rozwiązanie, ale lepsze niż 108, które pierwotnie miałem. Podejrzewam, że istnieje o wiele lepszy sposób, ale nie widzę tego w tej chwili.

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

Jest to nienazwana funkcja, która używa gsubi scan(t=dzieli liczby w wektorze na cyfry. Ich suma jest dodawana do wektora podczas upuszczania pierwszego elementu. repeatsłuży do przechodzenia między nczasami sekwencji, a wynik jest pierwszą pozycją wektora.

PHP, 80 bajtów

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

Wersja online

Mathematica, 67 bajtów

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