Digital Sum Fibonacci

30

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

Urna Magicznej Ośmiornicy
źródło
2
Czy możemy korzystać z indeksowania opartego na 1, czy też musi być oparty na 0?
Business Cat
1
@BusinessCat tak, jasne, pieprzyć to.
Magic Octopus Urn
1
Jak definiujesz, korzysta z powtórzenia ? Czy to musi być zakodowane na stałe, czy po prostu dodaję %24„normalne” rozwiązanie?
Dennis
1
@Dennis Zdecydowałem, że skorzystanie z powtórzenia oznacza O(1). Twój kod powinien działać w stałym czasie, jeśli naprawdę wykorzystuje powtórzenie.
Magic Octopus Urn
1
@Dennis technicznie% 24 na wejściu sprawi, że będzie górna granica przy 27 iteracjach; choć nie jest interesujące, to na pewno się liczy.
Magic Octopus Urn

Odpowiedzi:

7

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
Adnan
źródło
O rany ... Ja też zacznę uczyć się Oazy.
Magic Octopus Urn
28

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.

Neil
źródło
6
To również dostanie nagrodę równoważną liderowi powtórzeń ... To niesamowity wgląd matematyczny.
Magic Octopus Urn
13

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)
Jonathan Allan
źródło
1
Tak! Tyle +1! Powtórzenie odpowiedzi :). Dodałem sekcję bonusów do pana honoru, jesteście teraz liderem w konkursie z nagrodami za 100 punktów!
Magic Octopus Urn
11

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
ETHprodukcje
źródło
6

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.
Dennis
źródło
1
+1 za chuzpe „po prostu obliczmy cały powtarzany odcinek w stałym czasie”: D
Felix Dombek
4

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
Luke
źródło
To nie działa dla dużych wartości, takich jak 27, zawiesza przeglądarkę (przynajmniej robi to dla mnie)
Kritixi Lithos
To zajmuje trochę czasu, ale dotrze tam ... w końcu. Przyjrzę się temu, ale wydajność nie jest ważna dla tego wyzwania ...
Luke
Jezu, to nie jest tak intensywne obliczeniowo, twój program powinien działać dla wartości przekraczających 27 ... Ale jeśli działa dla 1-28, to technicznie dowodzi, że działa na wyższe.
Magic Octopus Urn
1
@KritixiLithos Problemem jest rekurencja. Obliczenie n- tej liczby w sekwencji wymaga z grubsza 2 ^ (n-2) wywołań funkcji, które budują się dość szybko.
ETHprodukcje
Możesz zapisać bajt za pomocą [..._(--$)+[_(--$)]]:-)
ETHproductions
4

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
Emigna
źródło
3

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!

Business Cat
źródło
3

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
}
Brad Gilbert b2gills
źródło
1
Możesz zapisać wewnętrzną lambda jako *.comb.sum+*.comb.sum.
smls
2

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
Luis Mendo
źródło
2

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!

Ahemone
źródło
Liczę kody ucieczki jako 1 bajt każdy! Świetna robota
Albert Renshaw,
2

Japt , 27 25 bajtów

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

Wypróbuj online!

Zaoszczędzono 2 bajty dzięki produktom ETH.

Tomek
źródło
Hej, dzięki za skorzystanie z Japt :-) Możesz użyć ´zamiast --zapisać dwa bajty.
ETHprodukcje
2

Haskell , 54 bajty

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

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

Laikoni
źródło
2

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!

Greg Martin
źródło
Twój drugi kod LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ"jest o 8 bajtów krótszy niż 43626804920391712116157158790~IntegerDigits~18.
JungHwan Min
masz rację! Pewnego dnia będę pamiętać LetterNumber...
Greg Martin
1

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`)))!

FlipTack
źródło
Myślę, że masz na myśli sum(map(int,a+b))(nie mogę dowiedzieć się, jak używać `w komentarzach)
1

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.

AdmBorkBork
źródło
1

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.

Neil
źródło
1

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]

TheBikingViking
źródło
1

Rubinowy, 58 bajtów

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

Proste zakodowane rozwiązanie.

GB
źródło
1

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!

Conor O'Brien
źródło
1

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
Pitagora
źródło
Witamy w ppcg! Miły pierwszy post!
Rɪᴋᴇʀ
1

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
Gerhard
źródło
0

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.

MickyT
źródło
0

PHP, 80 bajtów

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

Wersja online

Jörg Hülsermann
źródło
0

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@#&
J42161217
źródło