Summiere die ersten n geraden Fibonacci-Zahlen

19

Es scheint noch keinen Wettbewerb für diesen zu geben.

Die Aufgabe ist einfach. Addieren Sie die ersten ngeraden Zahlen der Fibonacci-Folge und geben Sie das Ergebnis aus.

Dies ist in OEIS A099919 festgelegt , mit der Ausnahme, dass die Reihenfolge beginnend mit fib(1) = 0statt um eins verschoben wird fib(1) = 1.

Das ist Code Golf. Die niedrigste Byteanzahl gewinnt.

Beispiele

n sum
1 0
2 2
3 10
4 44
5 188
6 798
7 3382
8 14328
9 60696

verbunden

dfernan
quelle
@EasterlyIrk Die Testfälle implizieren letztere, sollten jedoch ausdrücklich angegeben werden.
Mego
@Mego ja, das habe ich mir gedacht.
3.
9
Bitte nimm keine Antworten so schnell an. Es ist erst eine Stunde her, eine golferischere Antwort könnte hereinkommen . EDIT: Ich sehe jetzt, dass es bereits eine kürzere Antwort gibt, die noch nicht akzeptiert wird.
4.
6
Es ist üblich, mindestens eine Woche zu warten, bevor eine Antwort angenommen wird, da viele Leute dies als Zeichen dafür interpretieren, dass die Herausforderung nicht mehr aktiv ist.
Zgarb

Antworten:

8

Oasis , 8 7 5 Bytes

Dank @ETHProductions 1 Byte und dank @Adnan 2 weitere Bytes gespart!

zc»+U

Probieren Sie es online!

Erläuterung:

Dies verwendet dieselbe Wiederholungsformel wie meine MATL-Antwort.

Luis Mendo
quelle
1
Oasis 'info.txt sagt , dass Uder Code durch ersetzt wurde. Könnte 00Ihnen das ein Byte ersparen?
ETHproductions
@ETHproductions Danke! Ich habe das vergessen
Luis Mendo
1
Nett! Sie können 4*mit zund 2+mit ersetzen »:)
Adnan
@Adnan Danke! Ich sollte das Dokument wirklich lesen :-)
Luis Mendo
17

Python, 33 Bytes

c=2+5**.5
lambda n:(7-c)*c**n//20

Probieren Sie es online aus

Zauberformel!

xnor
quelle
3
Oh Gott. Ich habe viel länger gebraucht, als ich hätte erkennen müssen, warum Sie diese 20 in der zweiten Zeile "auskommentiert" haben: P
Theo
@xnor, Irgendwelche Hinweise auf diese Zauberformel?
TheChetan
@TheChetan: möglicherweise a(n) = (-10 + (5-3*sqrt(5))*(2-sqrt(5))^n + (2+sqrt(5))^n*(5+3*sqrt(5)))/20(Colin Barker, 26. November 2016) von der OEIS-Seite
Titus
7

Eigentlich 6 Bytes

r3*♂FΣ

Probieren Sie es online!

Erläuterung:

Jede dritte Fibonacci-Zahl (ab F_0 = 0) ist gerade. Somit sind die ersten ngeraden Fibonacci-Zahlen F_{i*3}für iin [0, n).

r3*♂FΣ
r       [0, n)
 3*     multiply each element by 3
   ♂F   retrieve the corresponding element in the Fibonacci sequence
     Σ  sum
Mego
quelle
7

JavaScript (ES6), 27 Byte

f=x=>x>1&&4*f(x-1)+f(x-2)+2

Rekursion zur Rettung! Dies verwendet eine der Formeln auf der OEIS-Seite:

f (n <1) = 0, f (n) = 4 · a (n + 1) + a (n) + 2

(aber um eins verschoben, weil die Herausforderung es um eins verschiebt)

ETHproductions
quelle
6

Pyke, 6 Bytes

3m*.bs

Probieren Sie es hier aus!

3m*    -   map(i*3, range(input))
   .b  -  map(nth_fib, ^)
     s - sum(^)
Blau
quelle
4

Perl 6 ,  38 35  32 Bytes

{[+] grep(*%%2,(1,&[+]...*))[^($_-1)]}

Versuch es

{[+] grep(*%%2,(0,1,*+*...*))[^$_]}

Versuch es

{[+] (0,1,*+*...*)[3,6...^$_*3]}

Versuch es

Erweitert:

{  # bare block lambda with implicit parameter 「$_」

  [+]                       # reduce with 「&infix:<+>」

    ( 0, 1, * + * ... * )\  # fibonacci sequence with leading 0

    [ 3, 6 ...^ $_ * 3 ]    # every 3rd value up to
                            # and excluding the value indexed by
                            # the input times 3

}
Brad Gilbert b2gills
quelle
3

Oktave , 36 35 33 Bytes

@(n)filter(2,'FAD'-69,(1:n)>1)(n)

Probieren Sie es online!

Erläuterung

Diese anonyme Funktion implementiert die Differenzgleichung a(n) = 4*a(n-1)+a(n-2)+2als rekursiven Filter :

Y = filter(B,A,X)filtert die Daten in Vektor Xmit dem durch Vektoren beschriebenen Filter Aund Berzeugt die gefilterten Daten Y. Der Filter ist eine "Direct Form II Transposed" -Implementierung der Standarddifferenzgleichung:

a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + ... + b(nb+1)*x(n-nb) - a(2)*y(n-1) - ... - a(na+1)*y(n-na)

In unserem Fall A = [1 -4 -1]sollte B = 2und die Eingabe xein Vektor von Einsen sein, wobei das Ergebnis als letzter Eintrag der Ausgabe erscheint y. Wir setzen jedoch auf 0den ersten Wert der Eingabe, sodass 0bei Bedarf eine Initiale in der Ausgabe angezeigt wird.

'FAD'-69ist nur ein kürzerer Weg, um den Koeffizientenvektor zu erzeugen A = [1 -4 -1]; und (1:n)>1erzeugt den Eingabevektor x = [0 1 1 ... 1].

Luis Mendo
quelle
3

Gleichstrom , 25 22 Bytes

9k5v1+2/3?*1-^5v/0k2/p

Probieren Sie es online!

Oder speichern Sie das Programm in einer Datei und führen Sie es durch Eingabe aus

dc -f *filename*

Das Programm akzeptiert eine nicht negative ganze Zahl n für stdin und gibt die Summe der ersten n geraden Fibonacci-Zahlen für stdout aus. (Die Fibonacci-Sequenz beginnt gemäß den Beispielen des OP mit 0.)


Dieses Programm verwendet die Formel (F (3n-1) -1) / 2 für die Summe der ersten n geraden Fibonacci-Zahlen, wobei F die übliche Fibonacci-Funktion ist, gegeben durch F (0) = 0, F (1) = In 1 ist F (n) = F (n - 2) + F (n - 1) für n> = 2.


dc ist ein stapelbasierter Rechner. Hier ist eine detaillierte Erklärung:

9k  # Sets the precision to 9 decimal places (which is more than sufficient).

5v  # Push the square root of 5

1+  # Add 1 to the number at the top of the stack.

2/  # Divide the number at the top of the stack by 2.

Zu diesem Zeitpunkt befindet sich die Zahl (1 + sqrt (5)) / 2 oben auf dem Stapel.

3   # Push 3 on top of the stack.

?   # Read a number from stdin, and push it.

\*  # Pop two numbers from the stack, multiply them, and push the product

1-  # Subtract 1 from the number at the top of the stack.

Zu diesem Zeitpunkt befindet sich 3n-1 oben im Stapel (wobei n die Eingabe ist), und (1 + sqrt (5)) / 2 befindet sich an zweiter Stelle von oben.

^   # Pop two numbers from the stack (x, then y), compute the power y^x, and push that back on the stack.

5v/ # Divide the top of the stack by sqrt(5).

Zu diesem Zeitpunkt ist die Zahl oben im Stapel (((1 + sqrt (5)) / 2) ^ (3n-1)) / sqrt (5). Die nächste Ganzzahl zu dieser Zahl ist F (3n-1). Beachten Sie, dass F (3n-1) immer eine ungerade Zahl ist.

0k # Change precision to 0 decimal places.

2/ # Divide the top of the stack by 2, truncating to an integer.

p # Print the top of the stack on stdout.
Mitchell Spector
quelle
3

Mathematica, 27 21 Bytes

Vielen Dank an xnor für den Hinweis auf eine alternative Formel, Alephalpha für die Korrektur des Startindex

Fibonacci[3#-1]/2-.5&
Genisis
quelle
1
Könnte die (Fibonacci(3*n+2)-1)/2Formel kürzer sein?
Xnor
2

MATL , 15 bis 14 Bytes

OOi:"t4*b+2+]x

Probieren Sie es online!

Erläuterung

Dies verwendet eine der Wiederholungsformeln von OEIS:

a (n) = 4 · a (n-1) + a (n-2) + 2

Für die Eingabe von N iteriert der Code N- mal, was 2-mal mehr als erforderlich ist. Dies wird ausgeglichen durch Einstellen 0, 0(statt 0, 2) als Anfangswert, und durch den letzten erhaltene Wert zu löschen und die vorherige Anzeige.

OO      % Push two zeros as initial values of a(n-2), a(n-1)
i       % Input N
:"      % Do this N times
  t     %   Duplicate a(n-1)
  4*    %   Multiply by 4
  b+    %   Bubble up a(n-2) and add to 4*a(n-1)
  2+    %   Add 2. Now we have 4*a(n-1)+a(n-2)+2 as a(n), on top of a(n-1)
]       % End
x       % Delete last value, a(n). Implicitly display the remaining value, a(n-1)
Luis Mendo
quelle
2

Batch, 80 Bytes

@set/at=x=0,y=1
@for /l %%i in (2,1,%1)do @set/az=x+y,y=z+x,t+=x=y+z
@echo %t%

Verwendet die Tatsache, dass jede dritte Fibonacci-Zahl gerade ist und berechnet sie nur zu dritt. Ich habe die (Fibonacci(3*n+2)-1)/2Formulierung ausprobiert , aber sie ist tatsächlich einige Bytes länger ( t+=was die Codegröße betrifft, stellt sich heraus, dass sie ziemlich effizient ist).

Neil
quelle
2

C 82 38 36 Bytes

2 Bytes gespart dank @BrainSteel

Die Formeln auf der OEIS-Seite haben es viel kürzer gemacht:

a(n){return--n<1?0:4*a(n)+a(n-1)+2;}

Probieren Sie es online!

82 Bytes:

x,s,p,n,c;f(N){s=0;p=n=1;c=2;while(n<N){if(~c&1)s+=c,n++;x=p+c;p=c;c=x;}return s;}

Die erste Version ist 75 Bytes, aber die Funktion ist nicht wiederverwendbar, es sei denn, Sie rufen immer fmit mehr Nals dem vorherigen Aufruf auf :-)

x,s,p=1,n=1,c=2;f(N){while(n<N){if(~c&1)s+=c,n++;x=p+c;p=c;c=x;}return s;}

Meine erste Antwort hier. Habe weder andere Antworten noch das OEIS überprüft. Ich denke, es gibt ein paar Tricks, die ich anwenden kann, um es kürzer zu machen :-)

simon
quelle
1
Sie können dies ein bisschen kürzer machen, indem Sie die Dinge ein wenig a(n){return--n<1?0:4*a(n)+a(n-1)+2;}
umrühren
1

Haskell ( 32-31 Bytes)

Dank @ChristianSievers ein Byte gespart.

Nach der Formel in OEIS: a(n) = 4*a(n-1)+a(n-2)+2, n>1von Gary Detlefs

a n|n>1=4*a(n-1)+a(n-2)+2|n<2=0

Dylan Meeus
quelle
Eine golferische Art, n<=1für ganze Zahlen zu sagen, ist n<2. Außerdem muss die zweite Bedingung nicht die Negation der ersten sein (die Redewendung otherwiseist einfach True), so dass üblicherweise beim Golfen so etwas 1<2verwendet wird.
Christian Sievers
@ ChristianSievers in der Tat die n <2 ist eine offensichtliche Verbesserung, danke. Der zweite funktioniert auch, rettet mir aber in diesem Fall nichts. Ich lerne immer noch Haskell und wusste nicht, dass ich so eine Wache haben könnte. Vielen Dank!
Dylan Meeus
1

Mathematica, 32 27 Bytes

Fibonacci[3Input[]-1]/2-1/2

Gutschrift an xnor . 5 Bytes gespart dank JungHwan Min.

devRicher
quelle
Sicherlich hat Mathematica Fibonacci und es ist kürzer, entweder (Fibonacci(3*n+2) - 1)/2das Sumi zu schreiben oder es zu tun ?
Xnor
@JungHwanMin Dies ist kein Plagiat; Es erwähnt die OEIS-Seite. Dies ist auch kein Kandidat für Community-Wiki. Siehe Wie sollen Community-Wikis verwendet werden? .
Dennis
@devRichter Es tut uns leid, dass Sie Ihren Beitrag wiederhergestellt haben, aber es war notwendig, ein Gespräch zu führen. Wenn Sie es gelöscht lassen möchten, lassen Sie es mich wissen und ich werde dieses Gespräch in einen Chatroom verschieben.
Dennis
@Dennis trotzdem, ich glaube, Vincenzo Librandi sollte ausdrücklich gedankt werden - (versehentlich meinen letzten Kommentar gelöscht ... konnte das nicht gelöscht werden?) Für den Community-Post-Vorschlag stehe ich korrigiert.
JungHwan Min
Ich wollte seinen Namen in der Post erwähnen ... (oder vielleicht den Mathematica-Kommentar (* Vincenzo Librandi, Mar 15 2014 *)in die Post aufnehmen, wie es bei OEIS der
Fall
1

R, 42 Bytes

Nicht-rekursive Lösung, im Gegensatz zur früheren Lösung von @rtrunbull hier .

for(i in 1:scan())F=F+gmp::fibnum(3*i-3);F

Verwendet die Eigenschaft, dass jeder dritte Wert der Fibonacci-Sequenz gerade ist. Missbräuchlich ist auch die Tatsache, dass Fstandardmäßig definiert als FALSE=0, so dass es als Grundlage für das Hinzufügen der Werte zu.

JAD
quelle
1

R, 42 41 Bytes

sum(DescTools::Fibonacci(3*(scan():2-1)))

scan(): nvon stdin nehmen.

scan():2-1: generiere ganze Zahlen von nbis 2, dekrementiere durch 1, gebe n-1durch 1.

3*(scan():2-1) : Mit 3 multiplizieren, da jede dritte Fibonacci-Zahl gerade ist.

DescTools::Fibonacci(3*(scan():2-1)): Geben Sie diese Fibonacci-Zahlen zurück (dh 3durch (n-1)*3).

sum(DescTools::Fibonacci(3*(scan():2-1))) : Summiere das Ergebnis.

Bisher hatte ich diese uninteressante Lösung mit einer der Formeln von OEIS:

a=function(n)`if`(n<2,0,4*a(n-1)+a(n-2)+2)
rturnbull
quelle
Ich habe es geschafft, Ihr bytecount ohne Rekursion zu entsprechen :)
JAD
@ JarkoDubbeldam Schön! Ich habe die Rekursion ebenfalls
verworfen
Schön, was genau kann desctools::fibonaccidas numbers::fibonaccinicht? Weil der Nebel etwas kürzer ist.
JAD
Oh, vergiss, hab es gefunden. Süß, die anderen Implementierungen, die ich gefunden habe, unterstützen es nicht, nach mehreren Nummern gleichzeitig zu fragen.
JAD
1
@JarkoDubbeldam Ja, `` gmp :: fibnum '' gibt Objekte vom Typ zurück bigz, die die *applyKlasse von Funktionen aus rawGründen in Typ konvertiert ...
rturnbull
1

PHP, 73-70 Bytes

for(${0}=1;$i++<$argv[1];$$x=${0}+${1})${$x^=1}&1?$i--:$s+=$$x;echo$s;

Präsentation variabler Variablen . Auf). Laufen Sie mit -nr.

Nervenzusammenbruch

for(${0}=1;         # init first two fibonaccis (${1}=NULL evaluates to 0 in addition)
                    # the loop will switch between $0 and $1 as target.
    $i++<$argv[1];  # loop until $i reaches input
    $$x=${0}+${1}       # 3. generate next Fibonacci
)
    ${$x^=1}            # 1. toggle index (NULL => 1 => 0 => 1 ...)
    &1?$i--             # 2. if current Fibonacci is odd, undo increment
    :$s+=$$x;           #    else add Fibonacci to sum
echo$s;             # print result

Zahlen sind in PHP vollkommen gültige Variablennamen.
Aber für die Literale brauchen sie geschweifte Klammern; also ${0}nicht $0.

36 Bytes, O (1)

<?=(7-$c=2+5**.5)*$c**$argv[1]/20|0;

Port von Xnors Antwort

Titus
quelle
0

PARI / GP, 21 Bytes

n->fibonacci(3*n-1)\2

\ ist der ganzzahlige Quotient.

Alephalpha
quelle