Digitale Summe Fibonacci

30

Wir alle kennen die Fibonacci-Sequenz :

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

Stattdessen nehmen f(n) = f(n-1) + f(n-2)wir jedoch die digitale Summe der vorherigen 2 Einträge.


Die Sequenz sollte immer noch beginnen 0, 1, danach werden die Unterschiede schnell sichtbar. Diese Liste ist 0-indiziert. Sie können auch 1-indiziert verwenden und angeben, welche Liste Sie verwendet haben.

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)

Hinweis: Ich habe die Wiederholung erst bemerkt, als ich die Herausforderung selbst veröffentlicht habe, und hier dachte ich, es wäre unmöglich, eine weitere neuartige Fibonacci-Herausforderung zu schreiben.


Ihre Aufgabe ist es, unter Angabe einer Nummer ndie n-te Stelle dieser Sequenz auszugeben.

Die ersten 3 Ziffern: [0,1,1],

24-stelliges wiederholtes Muster: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]

Tipp: Möglicherweise können Sie diese Wiederholung zu Ihrem Vorteil ausnutzen.


Dies ist , die niedrigste Byte-Anzahl ist der Gewinner.


BONUS: Wenn Sie in Ihrer Antwort die Wiederholung verwenden, erteile ich der Antwort mit der niedrigsten Byteanzahl, die die Wiederholung in der Sequenz nutzt, eine Prämie von 100 Punkten. Dies sollte als Teil Ihrer ursprünglichen Antwort nach Ihrer ursprünglichen Antwort eingereicht werden. Sehen Sie sich diesen Beitrag als Beispiel für das an, worüber ich spreche: https://codegolf.stackexchange.com/a/108972/59376

Um sich für diesen Bonus zu qualifizieren, muss Ihr Code in konstanter Zeit ( O(1)) mit einer Erklärung ausgeführt werden.

Bonussieger: Dennis https://codegolf.stackexchange.com/a/108967/59376 <Dennis hat gewonnen.

Einzigartigste Implementierung: https://codegolf.stackexchange.com/a/108970/59376
(Erhält auch 100 Punkte, finalisiert nach Auswahl der richtigen Antwort)

Magische Kraken-Urne
quelle
2
Können wir 1-basierte Indizierung verwenden oder muss es 0-basierte sein?
Business Cat
1
@ BusinessCat ja, klar, scheiß drauf.
Magic Octopus Urn
1
Wie definiert man nutzt die Wiederholung ? Muss es hartcodiert sein oder füge ich einfach %24eine "normale" Lösung hinzu?
Dennis
1
@Dennis definiere ich unter Ausnutzung der Wiederholung zu meinen O(1). Ihr Code sollte in konstanter Zeit ausgeführt werden, wenn die Wiederholung wirklich ausgenutzt wird.
Magic Octopus Urn
1
@ Tennis technisch% 24 auf der Eingabe würde es bei 27 Iterationen Obergrenze machen; obwohl es nicht interessant ist, zählt es definitiv.
Magic Octopus Urn

Antworten:

7

Oase , 5 Bytes

Code:

ScS+T

Probieren Sie es online!

Erweiterte Version:

ScS+10

Erläuterung:

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
quelle
Oh man ... Ich werde auch anfangen, Oasis zu lernen.
Magic Octopus Urn
28

JavaScript (ES6), 45 Byte

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>

xund ykann nicht beides sein 9, da dies die vorherige Zahl erfordern würde 0, so dass ihre digitale Summe nicht übersteigen kann 17. Dies bedeutet, dass die digitale Wurzel für Zahlen, die größer als 9sind, mit dem Restmodulo identisch ist 9.

Neil
quelle
6
Dies, dies wird auch ein Kopfgeld bekommen, das dem Wiederholungsleiter entspricht ... Dies ist eine wunderbare mathematische Einsicht.
Magic Octopus Urn
13

Python 2, 53 Bytes

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

Rekursive Funktion. Die Basisfälle von n=0und n=1ergeben n, dass größere Zahlen den Wert berechnen , indem sie jedes Zeichen aufrufen f(n-1)und f(n-2)in eine Zeichenfolge konvertieren, die beiden Zeichenfolgen verketten, jedes Zeichen mapmit der intFunktion in eine Ganzzahl konvertieren und dann die resultierende Liste summieren.


Unter Verwendung der Modulo-24-Informationen kann ich derzeit eine nicht rekursive unbenannte 56-Byte-Funktion erhalten:

lambda n:int(('011'+'2358dc7a89hhgfda56b8a9aa'*n)[n],18)
Jonathan Allan
quelle
1
Ja! Soviel +1! Eine Wiederholungsantwort :). Ich habe einen Bonus-Bereich zu Ihren Ehren hinzugefügt, Sie sind jetzt der Anführer in einem 100-Punkte-Kopfgeldwettbewerb!
Magic Octopus Urn
11

JavaScript (ES6), 34 Byte

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

Kann Ihren Browser für Eingaben über 27 oder so einfrieren, funktioniert aber für alle Eingabewerte. Dies kann mit einem einfachen Cache überprüft werden:

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>

Wie in Neils brillanter Antwort hervorgehoben , kann die Ausgabe 17 nicht überschreiten, sodass die digitale Summe aller Ausgaben über 9 gleich ist n%9. Dies funktioniert auch mit Ausgängen unter 9; Wir können es auch für 9 arbeiten lassen, indem wir 1 ~-vor dem Modul abziehen und danach wieder 1 hinzufügen.


Das Beste, was ich mit Hardcoding anfangen kann, sind 50 Bytes:

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

Gelee , 8 Bytes

;DFS
ç¡1

Probieren Sie es online!

Wie es funktioniert

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

Alternative Lösung, 19 Bytes, konstante Zeit

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

Probieren Sie es online!

Wie es funktioniert

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
quelle
1
+1 für den Chuzpe von „Berechnen wir einfach den gesamten wiederholten Abschnitt in konstanter Zeit“: D
Felix Dombek
4

JavaScript (ES6), 52 46 45 Bytes

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

Verwendung

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

Ausgabe

13

Erläuterung

Diese Funktion überprüft, ob die Eingabe kleiner als 2 ist, und gibt in diesem Fall die Eingabe zurück. Andernfalls wird ein Array mit zwei Werten erstellt, die als Zeichenfolgen aneinander angehängt werden. Diese beiden Werte ergeben sich aus dem Aufruf der Funktion mit input - 1und input - 2.

Der ...Operator teilt diese Zeichenfolge in ein Array von Zeichen auf, das dann erneut in eine Zeichenfolge konvertiert wird, jetzt jedoch mit einem +Abstand zwischen den Werten. Diese Zeichenfolge wird dann als Code interpretiert, sodass die Summe berechnet wird, die dann zurückgegeben wird.

Dies ist ein doppelt rekursiver Algorithmus, der ziemlich ineffizient ist. Es werden 2 n-2Funktionsaufrufe für die Eingabe benötigt n. Als solche ist hier eine längere, aber schnellere Lösung. Vielen Dank an ETHproductions für die Entwicklung.

f=($,p=1,c=0)=>$?f($-1,c,eval([...p+[c]].join`+`)):c
Luke
quelle
Dies funktioniert nicht für große Werte wie 27, es friert den Browser ein (zumindest für mich)
Kritixi Lithos
Es dauert einige Zeit, aber es wird dort ankommen ... irgendwann. Ich werde es untersuchen, aber die Leistung ist für diese Herausforderung nicht wichtig ...
Luke
Nun, Jesus, es ist nicht so rechenintensiv, dein Programm sollte für Werte über 27 funktionieren ... Aber wenn es für 1-28 funktioniert, dann beweist das technisch, dass es für höhere Werte funktioniert.
Magic Octopus Urn
1
@KritixiLithos Die Rekursion ist das Problem. Das Berechnen der n- ten Zahl in der Sequenz erfordert ungefähr 2 ^ (n-2) Funktionsaufrufe, die sich ziemlich schnell aufbauen.
ETHproductions
Sie können ein Byte speichern mit [..._(--$)+[_(--$)]]:-)
ETHproductions
4

05AB1E , 8 Bytes

XÎF‚¤sSO

Probieren Sie es online!

Erläuterung

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

CJam, 22 20 Bytes

2 Bytes gespart dank Martin Ender

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

Einfacher rekursiver Algorithmus, nichts Besonderes. 0-indiziert.

Probieren Sie es online! oder auf 0-50 testen (läuft eigentlich ziemlich schnell).

Erläuterung

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

Lösung mit der Wiederholung. Ähnlicher Algorithmus wie bei Jonathan Allan.

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

Probieren Sie es online!

Geschäfts-Katze
quelle
3

Perl 6 ,  41  37 Bytes

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

Versuch es

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

Versuch es

{ # 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
quelle
1
Sie können das innere Lambda als schreiben *.comb.sum+*.comb.sum.
smls
2

MATL , 15 Bytes

lOi:"yyhFYAss]&

Probieren Sie es 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
quelle
2

C 96 Bytes

oder 61 Bytes, die die Escape-Codes als jeweils 1 Byte zählen

0 indiziert. Ähnlich wie bei einigen anderen Antworten indiziere ich eine Wertetabelle, habe sie jedoch in 4-Byte-Blöcke komprimiert. Ich habe mich nicht darum gekümmert, die Mod 24-Version zu untersuchen, weil ich es nicht so interessant fand, da die anderen dies bereits getan haben, aber seien wir ehrlich, C wird sowieso nicht gewinnen.

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

Erläuterung:

#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

Probieren Sie es online!

Ahemone
quelle
Ich zähle die Escape-Codes als jeweils 1 Byte! Großartige Arbeit
Albert Renshaw
2

Japt , 27 25 Bytes

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

Probieren Sie es online!

2 Bytes gespart dank ETHproductions.

Tom
quelle
Hey, danke für die Verwendung von Japt :-) Du kannst ´anstelle von --zwei Bytes speichern.
ETHproductions
2

Mathematica, 49 Bytes

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

Einfache rekursive Definition. Wird nach einer Weile ziemlich langsam.

Mathematica, 79 71 Bytes

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

Hardcodierung des periodischen Musters. Blitzschnell und für Mathematica in befriedigender Weise missbräuchlich :) Danke an JungHwan Min für die Einsparung von 8 Bytes!

Greg Martin
quelle
Für Ihren zweiten Code LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ"sind 8 Bytes kürzer als 43626804920391712116157158790~IntegerDigits~18.
JungHwan Min
Du hast recht! Eines Tages werde ich mich erinnern LetterNumber...
Greg Martin
1

Python 2 , 56 Bytes

Einfache iterative Lösung.

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

Probieren Sie es online!

Das Verwenden (a%9or a)+(b%9or b)stellte sich tatsächlich als kürzer heraus als sum(map(int(`a`+`b`)))!

FlipTack
quelle
Ich denke du meinst sum(map(int,a+b))(kann nicht herausfinden, wie man in Kommentaren verwendet)
1

PowerShell , 79 Byte

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

Probieren Sie es online!

Langwierige iterative Lösung, die für jede forSchleife direkte Ziffernsummenberechnungen durchführt . Am Ende der Schleife befindet sich die gewünschte Zahl in $bder Pipeline und die Ausgabe ist implizit. Beachten Sie, dass bei einer Eingabe 0die Schleife nicht aktiviert wird, da die Bedingung false ist und somit erhalten $bbleibt 0.

AdmBorkBork
quelle
1

Batch, 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%

Ich habe mich gefragt, wie ich meine JavaScript-Antwort auf Batch portieren wollte, aber der Hinweis lag in @ Dennis 'Python-Lösung.

Neil
quelle
1

Pyth, 20 Bytes

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

Ein Programm, das die Eingabe einer Ganzzahl mit Nullindex annimmt und das Ergebnis ausgibt.

Testsuite (Erster Teil zur Formatierung)

Wie es funktioniert

[Erklärung kommt später]

TheBikingViking
quelle
1

Ruby, 58 Bytes

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

Die einfache Hardcodelösung.

GB
quelle
1

gestapelt , 40 Bytes

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

Dieses Lambda entspricht dem folgenden Lambda:

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

Probieren Sie es online!

Conor O'Brien
quelle
1

Oktave, 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
quelle
Willkommen bei ppcg! Schöner erster Beitrag!
6.
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)

Rufen Sie die Funktion f 123456789012345678901234567890123456789012345678beispielsweise mit auf.

Der Code funktioniert auch mit sehr großen Indizes. Aufgrund der implementierten Modulo 24-Funktionalität ist es sehr schnell.

Der unkomprimierte Code:

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

R, 90 Bytes

Eine schrecklich lange Lösung, aber sie ist besser als die 108, die ich ursprünglich hatte. Ich vermute, dass es einen viel besseren Weg gibt, aber ich kann es im Moment nicht sehen.

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

Dies ist eine Funktion , dass unnamed Verwendungen gsubund scan(t=die Zahlen in dem Vektor in Stellen zu spalten. Die Summe davon wird zum Vektor addiert, während das erste Objekt abgelegt wird. repeatwird verwendet, um die Sequenzzeiten zu durchlaufen, nund das Ergebnis ist das erste Element des Vektors.

MickyT
quelle
0

PHP, 80 Bytes

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

Online Version

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