Die berühmte Fibonacci-Sequenz lautet F(0) = 0; F(1) = 1; F(N+1) = F(N) + F(N-1)(für diese Herausforderung beginnen wir mit 0).

Ihre Herausforderung: Geben Sie bei n die Summe aller d- ten Fibonacci-Zahlen für alle Teiler d der n- ten Fibonacci-Zahl aus. Wenn Sie mehr formale Notation bevorzugen,

Eingabe : eine positive ganze Zahl n

Ausgabe : die Summe

Zum Beispiel betrachten n=4. F(4) = 3Die Teiler von 3 sind 1 und 3, daher sollte die Ausgabe sein F(1) + F(3) = 1 + 2 = 3.

Für n=6, F(6) = 8und die Divisoren von 8 sind 1, 2, 4, 8, die Ausgabe ist also F(1) + F(2) + F(4) + F(8) = 1 + 1 + 3 + 21 = 26.

Testfälle:

1 => 1
2 => 1
3 => 2
4 => 3
5 => 6
6 => 26

Dies ist Code-Golf , die kürzeste Antwort in Bytes gewinnt. Es gelten Standardlücken .

Eigentlich 5 Bytes

F÷♂FΣ

Probieren Sie es online!

Wie es funktioniert

       (implicit) Read n from STDIN.
F      Compute F(n).
 ÷     Get F(n)'s divisors.
  ♂F   Map F over the divisors.
    Σ  Take the sum.

Gelee , 7 Bytes

ÆḞÆDÆḞS

Probieren Sie es online!

Erläuterung:

ÆḞÆDÆḞS Main link (Arguments: z)
ÆḞ      zth Fibonacci number's
  ÆD                           divisors'
    ÆḞ                                   Fibonacci numbers'
      S                                                     sum

Mathematica, 29 Bytes

f=Fibonacci;f@#~DivisorSum~f&

Mathematica Simplified , 14 Byte

Fi@#~Div9`~Fi&

Na ja, das war letztendlich identisch mit der @ MartinEnder-Lösung ...

Japt , 11 Bytes

MgU â x@MgX

Probieren Sie es online!

05AB1E , 11 Bytes

!ÅFDI<èÑ<èO

Probieren Sie es online!

Erläuterung

!            # factorial of input
 ÅF          # get the list of fibonacci numbers (starting at 1)
             # smaller than or equal to this
   D         # duplicate list of fibonacci number
    I<è      # get the element at index (input-1)
       Ñ     # get the list of its divisors
        <    # decrement each
         è   # get the fibonacci numbers at those indices
          O  # sum

Haskell, 54 Bytes

f=0:scanl(+)1f
g x=sum[f!!d|d<-[1..f!!x],mod(f!!x)d<1]

Anwendungsbeispiel: g 6-> 26. Probieren Sie es online!

Alice , 38 36 Bytes

Danke an Leo für das Speichern von 2 Bytes.

/ow;B1dt&w;31J
\i@/01dt,t&w.2,+k;d&+

Probieren Sie es online!

Mit ziemlicher Sicherheit nicht optimal. Der Kontrollfluss ist ziemlich kompliziert und obwohl ich ziemlich zufrieden bin mit der Anzahl der Bytes, die gegenüber früheren Versionen gespeichert wurden, habe ich das Gefühl, dass ich Dinge, die einfacher sein könnten, überkompliziere und kürzere Lösung .

Erläuterung

Zuerst muss ich etwas über Alices Return Address Stack (RAS) herausfinden. Wie viele andere Fungeoids hat Alice den Befehl, im Code herumzuspringen. Es gibt jedoch auch Befehle, mit denen Sie zu Ihrem Ursprungsort zurückkehren können, sodass Sie Subroutinen ganz bequem implementieren können. Da es sich um eine 2D-Sprache handelt, existieren Unterprogramme natürlich nur nach Konvention. Es gibt nichts, was Sie daran hindert, eine Unterroutine mit anderen Mitteln als einem Rückkehrbefehl (oder an einem beliebigen Punkt in der Unterroutine) zu betreten oder zu verlassen, und je nachdem, wie Sie den RAS verwenden, gibt es möglicherweise ohnehin keine saubere Sprung- / Rückkehrhierarchie.

Im Allgemeinen wird dies implementiert, indem der Sprungbefehl jdie aktuelle IP-Adresse zum RAS überträgt, bevor der Sprung ausgeführt wird. Der Rücksprungbefehl gibt kdann eine Adresse des RAS aus und springt dorthin. Wenn der RAS leer ist, kgeschieht gar nichts.

Es gibt auch andere Möglichkeiten, den RAS zu manipulieren. Zwei davon sind für dieses Programm relevant:

• wschiebt die aktuelle IP-Adresse zum RAS, ohne irgendwo zu springen. Wenn Sie diesen Befehl wiederholen, können Sie ganz bequem einfache Schleifen schreiben &w...k, wie ich es bereits in früheren Antworten getan habe.
• Jist wie j, merkt sich aber nicht die aktuelle IP-Adresse auf dem RAS.

Es ist auch wichtig zu beachten, dass der RAS keine Informationen über die Richtung der IP speichert . Wenn Sie also zu einer Adresse mit zurückkehren, kwird immer die aktuelle IP-Richtung beibehalten (und daher auch, ob Sie sich im Kardinal- oder Ordinal-Modus befinden), unabhängig davon, wie wir die IP-Adresse durchlaufen haben joder durch wwelche die IP-Adresse übertragen wurde.

Nachdem dies erledigt ist, schauen wir uns zunächst die Subroutine im obigen Programm an:

01dt,t&w.2,+k

Diese Unterroutine zieht das untere Element des Stapels n nach oben und berechnet dann die Fibonacci-Zahlen F (n) und F (n + 1) (wobei sie oben auf dem Stapel verbleiben). Wir brauchen niemals F (n + 1) , aber es wird außerhalb der Unterroutine verworfen, da &w...kSchleifen mit dem RAS interagieren (was erfordert, dass diese Schleifen am Ende sind) einer Unterroutine sein müssen). Der Grund, warum wir Elemente von unten anstelle von oben verwenden, besteht darin, dass wir den Stapel eher wie eine Warteschlange behandeln. Das heißt, wir können alle Fibonacci-Zahlen auf einmal berechnen, ohne sie an einer anderen Stelle speichern zu müssen.

So funktioniert dieses Unterprogramm:

                                                          Stack
01    Push 0 and 1, to initialise Fibonacci sequence.     [n ... 0 1]
dt,   Pull bottom element n to top.                       [... 0 1 n]
t&w   Run this loop n times...                            [... F(i-2) F(i-1)]

  .     Duplicate F(i-1).                                 [... F(i-2) F(i-1) F(i-1)]
  2,    Pull up F(i-2).                                   [... F(i-1) F(i-1) F(i-2)]
  +     Add them together to get F(i).                    [... F(i-1) F(i)]

k     End of loop.

Das Ende der Schleife ist etwas knifflig. Solange sich eine Kopie der 'w'-Adresse auf dem Stapel befindet, wird die nächste Iteration gestartet. Sobald diese erschöpft sind, hängt das Ergebnis davon ab, wie die Unterroutine aufgerufen wurde. Wenn das Unterprogramm mit 'j' aufgerufen wurde, kehrt das letzte 'k' dorthin zurück, sodass das Schleifenende als Rückkehr des Unterprogramms gilt. Wenn das Unterprogramm mit 'J' aufgerufen wurde und es noch eine Adresse von früher auf dem Stapel gibt, springen wir dorthin. Dies bedeutet, wenn das Unterprogramm in einer äußeren Schleife selbst aufgerufen wurde, kehrt dieses 'k' zum Anfang dieser äußeren Schleife zurück. Wurde das Unterprogramm mit 'J' aufgerufen, aber der RAS ist jetzt leer, dann macht dieses 'k' nichts und die IP bewegt sich einfach weiter nach der Schleife. Wir werden alle drei dieser Fälle im Programm verwenden.

Zum Schluss zum Programm selbst.

/o....
\i@...

Dies sind nur zwei schnelle Exkursionen in den Ordnungsmodus, um Dezimalzahlen zu lesen und zu drucken.

Nach dem igibt es einen, wder sich aufgrund der Sekunde die aktuelle Position merkt, bevor er in das Unterprogramm übergeht /. Dieser erste Aufruf des Unterprogramms berechnet F(n)und übergibt F(n+1)die Eingabe n. Danach springen wir zurück, aber wir ziehen jetzt nach Osten, also der Rest der Programmoperatoren im Kardinalmodus. Das Hauptprogramm sieht folgendermaßen aus:

;B1dt&w;31J;d&+
        ^^^

Hier 31Jist ein weiterer Aufruf des Unterprogramms und berechnet daher eine Fibonacci-Nummer.

                                              Stack
                                              [F(n) F(n+1)]
;     Discard F(n+1).                         [F(n)]
B     Push all divisors of F(n).              [d_1 d_2 ... d_p]
1     Push 1. This value is arbitrary.        [d_1 d_2 ... d_p 1]
      The reason we need it is due to
      the fact that we don't want to run
      any code after our nested loops, so
      the upcoming outer loop over all
      divisors will *start* with ';' to
      discard F(d+1). But on the first
      iteration we haven't called the
      subroutine yet, so we need some 
      dummy value we can discard.
dt&w  Run this loop once for each element     [d_1 d_2 ... d_p 1]
      in the stack. Note that this is once    OR
      more than we have divisors. But since   [d_i d_(i+1) ... F(d_(i-1)) F(d_(i-1)+1)] 
      we're treating the stack as a queue,
      the last iteration will process the 
      first divisor for a second time. 
      Luckily, the first divisor is always 
      1 and F(1) = 1, so it doesn't matter 
      how often we process this one.

  ;     Discard the dummy value on the        [d_1 d_2 ... d_p]
        first iteration and F(d+1) of         OR
        the previous divisor on subsequent    [d_i d_(i+1) ... F(d_(i-1))]
        iterations.
  31J   Call the subroutine without pushing   [d_(i+1) ... F(d_i) F(d_i+1)]
        the current address on the RAS.
        Thereby, this doubles as our outer
        loop end. As long as there's an
        address left from the 'w', the end
        of the subroutine will jump there
        and start another iteration for the
        next divisor. Once that's done, the
        'k' at the end of the subroutine will
        simply do nothing and we'll continue
        after it.

;     Discard the final F(d_i+1).
d&+   Get the stack depth D and add the top   [final result]
      D+2 values. Of course that's two more
      than we have divisors, but the stack is
      implicitly padded with zeros, so that
      doesn't matter.

Axiom, 68 Bytes

g==>fibonacci;f(x:NNI):NNI==(x<3=>1;reduce(+,map(g,divisors(g(x)))))

ein Test

(46) -> [[i,f(i)] for i in [0,1,2,3,4,5,6,10,15] ]
   (46)
   [[0,1], [1,1], [2,1], [3,2], [4,3], [5,6], [6,26], [10,139583862540],
     [15,
      135823697912782666169062844948067355657769395021071830756126284114988028_
       12823029319917411196081011510136735503204397274473084444
     ]
   ]
                                       Type: List List NonNegativeInteger

Pari / GP , 34 Bytes

n->sumdiv((f=fibonacci)(n),x,f(x))

Probieren Sie es online!

Python 2 , 89 84 Bytes

^{-5 Bytes dank ovs}

lambda n:sum(f(i)for i in range(1,f(n)+1)if f(n)%i<1)
f=lambda x:x<3or f(x-1)+f(x-2)

Probieren Sie es online!

R, 77 Bytes

F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)

Verwendet die 'gmp'-Bibliothek. Dies hat eine eingebaute Fibonacci-Funktion und bietet die Möglichkeit, große Zahlen zu machen. Es verursachte ein paar Probleme mit seqs und applys, obwohl es immer noch kleiner ist, als meine eigene Fibonacci-Funktion zu erstellen.

Erläuterung

F=gmp::fibnum;               # Set F as fibnum function
N=F(scan());                 # get input and set N to the fibonacci number of that index
i=n=N-N;                     # set i and n to 0 with data type bigz
while(i<N)                   # loop while i < N
   if(N%%(i=i+1)<1)          # if incremented i is divisor of N 
       n=n+F(i);             # add F(i) to rolling sum
print(n)                     # output final result

Prüfung

> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 6
2: 
Read 1 item
Big Integer ('bigz') :
[1] 26
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 10
2: 
Read 1 item
Big Integer ('bigz') :
[1] 139583862540
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 15
2: 
Read 1 item
Big Integer ('bigz') :
[1] 13582369791278266616906284494806735565776939502107183075612628411498802812823029319917411196081011510136735503204397274473084444

Ohne Verwendung von gmp

81 Bytes , rekursive Funktion, die hoffnungslos langsam ist, wenn große (9+) Zahlen ausgewählt werden

F=function(n)`if`(n<2,n,F(n-1)+F(n-2));sum(sapply(which((N=F(scan()))%%1:N<1),F))

88 Bytes , die Binet-Formel, die mit größeren Zahlen einigermaßen gut funktioniert, aber dennoch recht schnell die Ganzzahlgrenze erreicht

F=function(n)round(((5+5^.5)/10)*((1+5^.5)/2)^(n-1));sum(F(which(F(N<-scan())%%1:N<1)))

Perl 6 , 49 Bytes

{my \f=0,1,*+*...*;sum f[grep f[$_]%%*,1..f[$_]]}

CJam , 26 Bytes

qi_[XY@{_2$+}*]_@\f%:!.*:+

Probieren Sie es online!

Ich bin sicher, dass es besser geht. Erläuterung:

Die Idee ist, ein Array von Fibonacci-Zahlen zu haben und dieses mit einem Array mit 1 und 0 zu versehen, wenn diese Zahl ein Teiler der Eingabe ist oder nicht.

qi                                 Read the input (n)
   [XY        ]                    Array starting with [1,2,...]
  _   @{_2$+}*                     Append n times the sum of the previous two
               _                   Duplicate the array
                @\f%               Modulo each item with n (0 if divisor, a number otherwise)
                    :!             Logical NOT everything (1 if divisor, 0 otherwise) 
                      .*:+         Dot product those two arrays

JavaScript (ES6), 76 65 Bytes

f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

Testfälle

f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(4))
console.log(f(5))
console.log(f(6))

JavaScript (ES6), 105 104 103 101 97 Byte

i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s

Versuch es

f=
i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s
o.innerText=f(j.value=4)
oninput=_=>o.innerText=f(+j.value)

<input id=j type=number><pre id=o>

Q, 75 Bytes

{f:{$[x<2;x;.z.s[x-1]+.z.s[x-2]]};sum f each m where(~)b mod m:1+til b:f x}

C (GCC) , 93 90 80 Bytes

F(n){n=n<2?n:F(n-1)+F(n-2);}i,s;f(n){for(s=0,i=F(n);i;i--)s+=F(n)%i?0:F(i);n=s;}

Probieren Sie es online!

++ hinzufügen , 89 Bytes

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,r,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{r}
D,d,@,{g}dF€gs

Probieren Sie es online!