Sum the First n Even Fibonacci Numbers

There seems not to be a contest for this one yet.

The task is simple. Add the first n numbers of the Fibonacci sequence that are even and output the result.

This is given by OEIS A099919, except that sequence is shifted by one, starting with fib(1) = 0 instead of fib(1) = 1.

This is code golf. Lowest byte count wins.

Examples

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


Related

• https://oeis.org/A099919 – xnor Jan 3 '17 at 23:42
• @EasterlyIrk The test cases imply the latter, but it should be explicitly stated. – Mego Jan 3 '17 at 23:49
• @Mego yeah, I figured as much. – Rɪᴋᴇʀ Jan 3 '17 at 23:49
• Please don't accept answers so fast. It's only been an hour, golfier answer could come in. EDIT: I see now there's already a shorter answer that's not accepted yet. – Rɪᴋᴇʀ Jan 4 '17 at 0:42
• It's customary to wait at least a week before accepting an answer, because many people interpret it as a sign that the challenge is no longer active. – Zgarb Jan 4 '17 at 7:54

Oasis, 87 5 bytes

1 byte saved thanks to @ETHProductions and 2 more saved thanks to @Adnan!

zc»+U


Try it online!

Explanation:

This uses the same recurrence formula as my MATL answer.

• Oasis's info.txt says U is replaced in the code with 00, might that save you a byte? – ETHproductions Jan 4 '17 at 0:06
• @ETHproductions Thanks! I forgot that – Luis Mendo Jan 4 '17 at 0:14
• Nice! You can replace 4* with z and 2+ with » :) – Adnan Jan 4 '17 at 0:29
• @Adnan Thank you! I really should read the doc :-) – Luis Mendo Jan 4 '17 at 0:40

Mathematica, 27 21 bytes

Thanks to xnor for pointing out an alternate formula, alephalpha for correcting for starting index

Fibonacci[3#-1]/2-.5&

• Might the (Fibonacci(3*n+2)-1)/2 formula be shorter? – xnor Jan 4 '17 at 0:38

PARI/GP, 21 bytes

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


\ is the integer quotient.

Pyke, 6 bytes

3m*.bs


Try it here!

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


PHP, 73 70 bytes

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


showcasing variable variables. O(n). Run with -nr.

breakdown

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


Numbers are perfectly valid variable names in PHP.
But, for the literals, they require braces; i.e. ${0}, not $0.

36 bytes, O(1)

<?=(7-$c=2+5**.5)*$c**$argv[1]/20|0;  port of xnor´s answer C, 8238 36 bytes 2 bytes saved thanks to @BrainSteel The formulas at the OEIS page made it much shorter: a(n){return--n<1?0:4*a(n)+a(n-1)+2;}  Try it 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;}  The first version is 75 bytes but the function is not reusable, unless you always call f with greater N than the previous call :-) 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;}  My first answer here. Didn't check any other answers nor the OEIS. I guess there are a few tricks that I can apply to make it shorter :-) • You can make this a tad shorter by shuffling things around a bit: a(n){return--n<1?0:4*a(n)+a(n-1)+2;} (36 bytes) – BrainSteel Jan 5 '17 at 21:30 Japt, 10 bytes Uo@MgX*3Ãx  Try it online! Thanks ETHproductions :) R, 42 41 bytes sum(DescTools::Fibonacci(3*(scan():2-1)))  scan() : take n from stdin. scan():2-1 : generate integers from n to 2, decrement by 1, yielding n-1 through 1. 3*(scan():2-1) : multiply by 3, as every third fibonacci number is even. DescTools::Fibonacci(3*(scan():2-1)) : Return these fibonacci numbers (i.e. 3 through (n-1)*3). sum(DescTools::Fibonacci(3*(scan():2-1))) : Sum the result. Previously, I had this uninteresting solution using one of the formulae from OEIS: a=function(n)if(n<2,0,4*a(n-1)+a(n-2)+2)  • I managed to match your bytecount without recursion :) – JAD Jan 5 '17 at 14:41 • @JarkoDubbeldam Nice! I've ditched the recursion also and made a one-byte improvement :) – rturnbull Jan 5 '17 at 15:30 • Nice, what exactly does desctools::fibonacci do that numbers::fibonacci cant? Because that mist be a bit shorter. – JAD Jan 5 '17 at 15:39 • Oh nevermind, found it. Sweet, the other implementations I found don't support asking for multiple numbers at once. – JAD Jan 5 '17 at 15:40 • @JarkoDubbeldam Yeah, gmp::fibnum'' returns objects of type bigz, which the *apply class of functions converts to type raw because reasons... – rturnbull Jan 5 '17 at 15:50 R, 42 bytes Non-recursive solution, as contrast to the earlier solution by @rtrunbull here. for(i in 1:scan())F=F+gmp::fibnum(3*i-3);F  Uses the property that each third value of the Fibonacci sequence is even. Also abuses the fact that F is by default defined as FALSE=0, allowing it as a basis to add the values to. dc, 25 22 bytes 9k5v1+2/3?*1-^5v/0k2/p  Try it online! Or save the program in a file and run it by typing dc -f *filename*  The program accepts a non-negative integer n on stdin, and it outputs the sum of the first n even Fibonacci numbers on stdout. (The Fibonacci sequence is taken to start with 0, as per the OP's examples.) This program uses the formula (F(3n-1)-1)/2 for the sum of the first n even Fibonacci numbers, where F is the usual Fibonacci function, given by F(0) = 0, F(1) = 1, F(n) = F(n-2) + F(n-1) for n >= 2. dc is a stack-based calculator. Here's a detailed explanation: 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.  At this point, the number (1+sqrt(5))/2 is at the top of the stack. 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.  At this point, 3n-1 is at the top of the stack (where n is the input), and (1+sqrt(5))/2 is second from the top. ^ # 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).  At this point, the number at the top of the stack is (((1+sqrt(5))/2)^(3n-1))/sqrt(5). The closest integer to this number is F(3n-1). Note that F(3n-1) is always an odd number. 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.  Mathematica, 32 27 bytes Fibonacci[3Input[]-1]/2-1/2  Credit to xnor. Saved 5 bytes thanks to JungHwan Min. • Surely Mathematica has Fibonacci and it's shorter to do either (Fibonacci(3*n+2) - 1)/2 or write the sumi? – xnor Jan 4 '17 at 0:19 • @JungHwanMin This isn't plagiarism; it mentions the OEIS page. Also, this isn't a candidate for community wiki. See How should Community Wikis be used?. – Dennis Jan 4 '17 at 18:13 • @devRichter Sorry for undeleting your post, but it was necessary to have a conversation. If you want to keep it deleted, let me know and I'll move this conversation to a chat room. – Dennis Jan 4 '17 at 18:15 • @Dennis still, I believe credit should be given to Vincenzo Librandi explicitly -- (accidentally deleted my last comment... could that be undeleted?) For the community post suggestion, I stand corrected. – JungHwan Min Jan 4 '17 at 18:16 • What I meant was to mention his name in the post... (or perhaps include the Mathematica comment (* Vincenzo Librandi, Mar 15 2014 *) in the post, as it is on OEIS.) – JungHwan Min Jan 4 '17 at 18:24 Haskell (32 31 bytes) Saved one byte thanks to @ChristianSievers. Using the formula given in OEIS: a(n) = 4*a(n-1)+a(n-2)+2, n>1 by Gary Detlefs a n|n>1=4*a(n-1)+a(n-2)+2|n<2=0 • A golfier way to say n<=1 for integers is n<2. Also, the second condition doesn't need to be the negation of the first (the idiomatic otherwise is simply True), so usally in golfing something like 1<2 is used. – Christian Sievers Jan 4 '17 at 12:44 • @ChristianSievers indeed the n<2 is an obvious improvement, thank you. The second one works as well, though it does not save me anything in this case. I'm still learning Haskell and did not realise I could have a guard like that. Thank you! – Dylan Meeus Jan 4 '17 at 12:49 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%  Uses the fact that every third Fibonacci number is even, and just calculates them three at a time (calculating more than one at a time is actually easier as you don't have to swap values around). I tried the (Fibonacci(3*n+2)-1)/2 formulation but it's actually a few bytes longer (t+= turns out to be quite efficient in terms of code size). Octave, 3635 33 bytes @(n)filter(2,'FAD'-69,(1:n)>1)(n)  Try it online! Explanation This anonymous function implements the difference equation a(n) = 4*a(n-1)+a(n-2)+2 as a recursive filter: Y = filter(B,A,X) filters the data in vector X with the filter described by vectors A and B to create the filtered data Y. The filter is a "Direct Form II Transposed" implementation of the standard difference equation: 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 our case A = [1 -4 -1], B = 2, and the input x should be a vector of ones, with the result appearing as the last entry of the output y. However, we set to 0 the first value of the input so that an initial 0 appears in the output, as required. 'FAD'-69 is just a shorter way to produce the coefficient vector A = [1 -4 -1]; and (1:n)>1 produces the input vector x = [0 1 1 ... 1]. Perl 6, 38 35 32 bytes {[+] grep(*%%2,(1,&[+]...*))[^($_-1)]}


Try it

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


Try it

Expanded:

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

}


Python, 33 bytes

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


Try it online

Magic formula!

• Oh god. It took me much longer than it should have to realize why you were "commenting out" that 20 on the second line :P – Theo Jan 4 '17 at 13:14
• @xnor, Any reference to this magic formula? – TheChetan Jan 4 '17 at 13:43
• @TheChetan: possibly a(n) = (-10 + (5-3*sqrt(5))*(2-sqrt(5))^n + (2+sqrt(5))^n*(5+3*sqrt(5)))/20 (Colin Barker, Nov 26 2016) from the OEIS page – Titus Jan 4 '17 at 13:50

MATL, 15 14 bytes

OOi:"t4*b+2+]x


Try it online!

Explanation

This uses one of the recurrence formulas from OEIS:

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

For input N the code iterates N times, which is 2 more times than necessary. This is compensated for by setting 0, 0 (instead of 0, 2) as initial values, and by deleting the last obtained value and displaying the previous one.

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)


JavaScript (ES6), 27 bytes

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


Recursion to the rescue! This uses one of the formulas on the OEIS page:

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

(but shifted by one because the challenge shifts it by one)

Actually, 6 bytes

r3*♂FΣ


Try it online!

Explanation:

Every third Fibonacci number (starting from F_0 = 0) is even. Thus, the first n even Fibonacci numbers are F_{i*3} for i in [0, n).

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


Python 2, 35 bytes

f=lambda n:n/2and 4*f(n-1)+f(n-2)+2


Try it online!