Da es sehr viele normale Fibonacci-Herausforderungen gab, entschied ich, dass es interessant sein könnte, die reziproke Fibonacci-Konstante zu berechnen - nämlich die Summe der Reziprokwerte der Fibonacci-Sequenz.

Die Herausforderung besteht darin, die reziproke Fibonacci-Konstante mit der Anzahl der Fibonacci-Reihen zu berechnen, um die als Eingabe angegebene Ziffer zu verwenden, dh eine Eingabe von 10 bedeutet, basierend auf den Kehrwerten der ersten 10 Fibonacci-Zahlen zu berechnen. Im wahrscheinlichen Fall eines Unentschieden gewinnt der kürzeste Code.

Der Gewinner wird in drei Wochen nach den Standard-Code-Golf-Regeln ermittelt.

K (19)

(oder 17, wenn Sie die Definition als Funktion überspringen)

f:{+/*+%x(|+\)\|!2}

Auf Kona getestet.

Grundsätzlich werden die ersten x-Werte der Fibonacci-Sequenz in einem Array generiert (ohne eingebaute Elemente), 1 durch jeden Wert des gesamten Arrays dividiert, transponiert und zusammengefasst.

(danke an @tmartin für die bessere Summenmethode)

Perl - 35 Bytes

print!map$\-=1/($%+=$.=$%-$.),0..<>

Beispielnutzung:

$ echo 10 | perl inv-fib-sum.pl
3.34170499581934

Weitere Analyse

Es ist interessant festzustellen, dass die Summe

ist konvergent. Angenommen, wir wollten ein paar tausend Stellen oder so berechnen, ist der naive Ansatz fast ausreichend. Die Konvergenz ist zunächst recht langsam, beschleunigt sich jedoch schnell, sodass 1000 Stellen nur etwa 4800 Terme benötigen . Eine Beispiel-Python-Implementierung könnte sein:

a=[1,1]
for i in range(4800):a=[a[0]+a[1]]+a
z=10**1000
print sum(map(lambda i:z/i,a))

was nach einer Sekunde oder so ausgibt:

33598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142832933

(Die letzten vier Ziffern konvergieren nicht ganz, aber das werden wir vorerst ignorieren.)

Versuchen wir, die Konvergenz etwas zu beschleunigen. Ein Standardtrick ist die Verwendung von Eulers Transformation . Nach Erweiterung und Vereinfachung ergibt sich ein schöneres Ergebnis:

Es sollte ziemlich offensichtlich sein, warum dies schneller konvergiert; Jeder Term hat 3 Terme im Nenner und nicht nur einen. Die Berechnung von 1000 Stellen erfordert nur 1600 (ein Drittel so viele) Begriffe:

a=[1,1]
for i in range(1601):a=[a[0]+a[1]]+a
z=10**1000
print sum(map(lambda i:(-1)**i*z/(a[i]*a[i+1]*a[i+2]),range(1601)))

Ausgabe:

3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142834500

(Auch hier konvergieren die letzten 4 Ziffern nicht.)

Wir sind noch nicht ganz fertig. Wenn wir benachbarte Begriffe kombinieren, erhalten wir Folgendes:

Das Ausklammern jedes Terms aus dem Rest der Summierung ergibt den verschachtelten Ausdruck:

Jetzt kommen wir irgendwohin. Beachten Sie, dass die Zähler von OEIS A206351 folgen (mit Ausnahme des ersten Terms, der verdoppelt wird):

und die Nenner folgen OEIS A081016 (um einen Begriff verschoben):

Jedes von diesen hat sehr einfache Wiederholungsrelationen, nämlich:

und

beziehungsweise. Alles in allem benötigen wir nur 800 Iterationen für 1000 Ziffern:

b,c=[16,3,1],[273,40,3]
for i in range(800):b,c=[7*b[0]-b[1]-4]+b,[7*c[0]-c[1]-1]+c
s=z=10**1000
for x,y in zip(b,c):s=(z+s)*x/y
print s

welche Ausgänge:

3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142835294

(Hier konvergieren schließlich die letzten 4 Ziffern korrekt.)

Das ist aber noch nicht alles. Wenn wir die Zwischenwerte für s beobachten , stellen wir fest, dass sie vollständig auf einen anderen Wert konvergieren, bevor sie auf den tatsächlichen Konvergenzpunkt konvergieren. Der Grund dafür ist folgender:

Wenn wir nach einem stabilen s suchen, finden wir Folgendes:

Da dies eine einfache Wurzel ist, können wir die Newtonsche Methode verwenden , um den größten Teil des Weges dorthin zu finden, und dann zu einem viel späteren Zeitpunkt in der Iteration einspringen. Es sind nur etwa 400 Stellen Genauigkeit erforderlich (da die b- und c- Werte ohnehin nicht größer sind), was mit nur 7 Iterationen erreicht werden kann, während 320 Iterationen der Hauptschleife gespeichert werden:

b,c=[16,3,1],[273,40,3]
for i in range(480):b,c=[7*b[0]-b[1]-4]+b,[7*c[0]-c[1]-1]+c
z=10**1000;s=z/17
for i in range(7):s-=(s*s+s*z-z*z/16)/(2*s+z)
for x,y in zip(b,c):s=(z+s)*x/y
print s

Die Ausgabe ist identisch mit der vorherigen, die Laufzeit beträgt auf meinem System mit PyPy v2.1 etwa 0,02 Sekunden. Obwohl es ein Zehntel der Anzahl von Iterationen wie das Original benötigt, ist es aufgrund der Multiplikation und Division durch viel kleinere Begriffe deutlich schneller als das Zehnfache. Ich denke nicht, dass viel mehr daran geändert werden kann, obwohl ich froh wäre, wenn ich falsch dargestellt würde.

Mathematica (32 Zeichen ohne eingebauten Fibonacci)

Tr[1/⌈(.5+√5/2)^Range@#/√5-.5⌉]&

Hier habe ich die Rundungsformel für Fibonacci-Zahlen verwendet

Wo φist der goldene Schnitt?

Kona ( 25 21)

{+/%(x(|+\)\1 1)[;1]}

Könnte wahrscheinlich von Experten verkleinert werden, aber ich lerne immer noch die Sprache.

  f 10
3.341705
  f 3
2.8333
  f 25
3.359872
  f 400
3.359886

Der letzte hat nicht länger gedauert als die anderen.

Mathematica 30 24

Mit 6 Zeichen dank ybeltukov gespeichert.

 Tr[1/Fibonacci@Range@#]&

Vor dem Hinzufügen der Begriffe:

1/Fibonacci@Range@#&[20]

Mit Zusatz enthalten:

 Tr[1/Fibonacci@Range@#]&[20]

APL, 21 Zeichen / Bytes *

{+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵}

Beispiel

      {+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵} 10
3.330469041
      ⍪{+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵}¨⍳10
1          
2          
2.5        
2.833333333
3.033333333
3.158333333
3.23525641 
3.282875458
3.312287223
3.330469041
      {+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵} 100
3.359885666

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ^{*: APL kann in einem eigenen (} alten) Einzelbyte ^{-Zeichensatz geschrieben werden, der APL-Symbole den oberen 128-Byte-Werten} zuordnet
^{. Für die Bewertung kann daher ein Programm mit N Zeichen , das nur ASCII-Zeichen und APL-Symbole verwendet, als N Byte lang angesehen werden.}

Javascript, 33

Eingang: n = 10

s=f=t=1;for(;n--;)t+=1/(s+=f=s-f)

Basierend auf meinem ersten Beitrag in Perl ist hier das Ergebnis direkt von der Google Chrome-Konsole .

K, 22

...

{+/%x#x{x,+/-2#x}/1 1}

GTB , 35

Läuft auf einem TI-84-Rechner

1→Y:0→X`N4;N,1,N~1/X:Y→Z:X+Y→Y:Z→X&

• Lager 1in Yund 0inX
• Nehmen Sie Nals Eingabe
• Initialisieren Sie eine ForSchleife
• Anzeige X
• Lager Yin Zund X+YinY
• Speichern ZinX
• Beenden Sie die ForSchleife

BC - 116

define f(n){if(n < 2){return n;}else{return f(n-1)+f(n-2);}}
define r(n){for(i=1;i<n;++i){m=m+(1/f(i));};return m;}

rufe r (n) mit n auf, um zu lösen. Die Genauigkeit kann beliebig eingestellt werden, daher ist dies die genaueste Lösung.

PERL, 62 43

$s=$t=1;$t+=1/($a=$f+$s),$f=$s,$s=$a,for 0..<>;say $t

Bearbeiten:

Nachdem ich mir meinen Code noch einmal angesehen hatte, konnte ich 19 Zeichen speichern:

$s=1;$t+=1/($s+=$f=$s-$f)for 0..<>;say $t+2

Eingabe: 10
> 3.35294128575734

Viertens 64

: r 1 1 rot 1e 0 do 2dup - nip tuck + dup s>f 1/f f+ swap loop ;

Verwendungszweck:

10 r f. 3.34170499581934  ok
100 r f. 3.35988566624318  ok
1000 r f. 3.35988566624318  ok

Python ( 55 51)

i,r=p=1,1
while i<n+1:r+=1./p[-1];p=p[1],sum(p);i+=1
r

i,r,a,b=[1]*4
while i<n+1:r+=1./b;a,b=b,b+a;i+=1
r

Im interaktiven Modus:

n=10
3.341704995819338

n=100

3.3598856429940778

3.359885666243178

n=400

3.3598855578800064

3.359885666243178

Perl 6 , 27 Bytes

{sum 1 X/(1,&[+]...*)[^$_]}

Probieren Sie es online aus!

Alternative

{sum 1 xx$_ Z/(1,&[+]...*)}

Probieren Sie es online aus!

Japt -mx, 6 Bytes

1/MgUÄ

Versuch es

C # (.NET Core) , 66 Byte

a=>{double r=1,x=1,y=1,i=0;for(;++i<a;y+=x,x=y-x)r+=1/y;return r;}

Probieren Sie es online aus!

Floats können wegen Ungenauigkeit nicht verwendet werden.

Beispiel mit Eingabe = 8:

• double: 3.28287545787546 (rundet auf 3.282875)
• float: 3,282876 (um 0,000001 aus)

Ungolfed:

a => {
    double r = 1,                       // initialize r (sum of reciprocals) - start at 1 to save one byte in for loop
            x = 1, y = 1,                   // initialize x (2nd largest Fibonacci) and y (largest Fibonacci)
            i = 0;                          // initialize i (loop counter)
    for(; ++i < a; y += x, x = y - x)   // from 1 to a, while incrementing the Fibonacci numbers
        r += 1 / y;                         // increment the reciprocal Fibonacci
    return r;                           // return the reciprocal Fibonacci
}

RPL (HP 49G / G + / 50 g), 50 Bytes

« 0. 1. DUP2 5. ROLL
  START SWAP OVER + ROT OVER INV + UNROT
  NEXT DROP2
»

Beispiele:

10 -> 3.33046904076

11 -> 3.34170499582

30 -> 3,35988372158

55 -> 3.35988566622

Theoretisch würde die Summe der ersten 55 Ziffern 12 korrekte Ziffern ergeben. Die letzte Ziffer sollte '4' anstelle von '2' sein. Dies sollte behoben werden, indem die Begriffe rückwärts addiert werden, der Code wäre jedoch etwas länger.

Wenn die Konstante unter Verwendung der Definition auf 1000 Dezimalstellen berechnet werden soll, sollte die Summe mindestens zu den ersten 4790 Termen ausgeführt werden, was auf dem HP 50g, wenn möglich, zu viel Zeit in Anspruch nehmen würde. Für diese Aufgabe ist eine effizientere Methode erforderlich, wie sie im folgenden RPL-Programm (464 Byte, Prüfsumme Nr. 207Eh) verwendet wird, dessen Argument die gewünschte Anzahl von Dezimalstellen ist:

%%HP: T(3)A(R)F(.);
\<< PUSH RAD -105 CF -3 CF R\->I DUP 1 + 2 INV SWAP 100 LN * 5 LN + OVER ASINH / \v/ * CEIL DUP 2 MOD + DUP 0 ROT
[[ 1 1 ]
 [ 1 0 ]] SWAP DUP2 ^ 3 GETI UNROT GET 4 ROLLD 4 ROLLD DUP + ^ 1 GETI UNROT GET 1 + 0 1 8 ROLL 2 /
  START PICK3 + DUP PICK3 * NEG 6 PICK SQ + / 4 PICK SQ * EXPAND ROT PICK3 - ROT OVER - ROT 6 ROLL 6 ROLL 6 ROLL + LASTARG * LASTARG 5 ROLLD 5 ROLLD / + ROT PICK3 - ROT OVER - 6 ROLL 6 ROLL 6 ROLL
  NEXT ROT + INV 5 ROLL + EXPAND 4 ROLLD 3 DROPN FXND PICK3 ALOG OVER - PICK3 * SWAP IQUOT + \->STR DUP HEAD -51 FC? { "." } { "," } IFTE + SWAP TAIL + 1 ROT 2 + SUB POP
\>>

'RFC' STO

1000 RFC ->

3.3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142835294

(22 min 23 sec, auf dem echten HP 50g)

Für tausend Stellen werden die ersten 50 Terme der Reihe plus weitere 50 Terme eines fortgesetzten Bruchs ausgewertet, jeweils zwei in nur 25 Iterationen (jeweils 48 Terme hätten ausgereicht). Ein gleichwertiges DECIMAL BASIC-Programm benötigt auf meinem Computer nur 10 Millisekunden (Intel (R) Core (TM) Duo-CPU E4700 bei 2,6 GHz).

JAEL, 9 7 Bytes

Das Ändern der diakritischen Zeichen von einem Zeichen zu einem anderen gab mir 1 Byte

Arbeitet noch an der SBCS-Codierung.

#`&@uȦ

Erläuterung (automatisch generiert):

./jael -u explain '#`&@uȦ'

ORIGINAL CODE:
#`&@uȦ

EXPANDING EXPLANATION:
Ȧ => .a!

EXPANDED CODE:
#`&@u.a!

COMPLETED CODE:
#`&@u.a!,


#       ,               repeat (p1) times:
 `                              stack 1
  &                             push number of iterations of this loop
   @                            push nth fibonacci number
    u                           push p2 / p1
     .                          push the value under the tape head
      a                         push p1 + p2
       !                        write p1 to the tapehead
         ␄              print machine state

Gelee , 5 Bytes

RÆḞİS

Probieren Sie es online aus!

Wie es funktioniert

RÆḞİS    Main link (monad). Input: integer
R        Range
 ÆḞ      nth Fibonacci number
   İ     Reciprocal
    S    Sum

cQuents , 13 11 Bytes

;/b$
=1:Z+Y

Probieren Sie es online aus!

Erläuterung

;          The sum of the first n terms of the sequence
 /         which are 1 divided by
  b$       the nth term in the sequence on the second line

=1:Z+Y     Fibonacci with starting indexes 1,1