Sum the First n Even Fibonacci Numbers

Question

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

Answer 1

Python, 33 bytes

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

Try it online

Magic formula!

Answer 2

Oasis, 8 7 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.

Answer 3

Python 2, 35 bytes

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

Try it online!

Answer 4

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

Answer 5

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)

Answer 6

Pyke, 6 bytes

3m*.bs

Try it here!

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

Answer 7

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

}

Answer 8

Octave, 36 35 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].

Answer 9

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.

Answer 10

Mathematica, 27 21 bytes

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

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

Answer 11

Forth (gforth), 38 bytes

: f 1 1 rot 1 ?do tuck 4 * + loop 2/ ;

Try it online!

Wins over existing Forth answer by porting this formula:

$$ G(0)=G(1)=1, G(n+2)=4G(n+1)+G(n) \\ a(n) = \left\lfloor \frac{G(n)}2 \right\rfloor $$

: f ( n -- a_n )  \ Take single number n and return a_n
  1 1 rot 1       \ g0 g1 n 1
  ?do             \ loop n-1 times
    tuck 4 * +    \ gn-1 gn -> gn gn+1=4gn+gn-1
  loop            \ end loop; top is gn
  2/              \ an = gn/2 (floor division)
;

Answer 12

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)

Answer 13

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

Answer 14

C, 82 38 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 :-)

Answer 15

APL (Dyalog Unicode), 22 21 bytes

-1 byte thanks to Adám

(2+5*.5)∘(⌊20÷⍨*×7-⊣)

Try it online!

Uses xnor's magic formula

(2+5*.5)∘(⌊20÷⍨*×7-⊣)

(2+5*.5)               ⍝ constant c
        ∘(           ) ⍝ joined to
                 7-⊣  ⍝ 7-c
                ×      ⍝ multiplied by
               *       ⍝ input^c
           20÷⍨        ⍝ all over 20
          ⌊            ⍝ floor

Or with APL (Dyalog Extended), 19 bytes

(Thanks to Adám)

(2+√5)∘(⌊20÷⍨*×7-⊣)

Try it online!

Answer 16

APL (Dyalog Unicode), 16 bytes^SBCS

⌊⊃⌽(4∘⊥,⊃)⍣⎕÷2 2

Try it online!

A full program.

How it works: the math

Uses a(n) = (Fibonacci(3*n + 2) - 1)/2 from the OEIS page, but we have offset 1 in a(n), so the actual formula is:

$$ a(n) = \frac{F(3 n - 1) - 1}{2} = \Bigl\lfloor \frac{F(3 n - 1)}{2} \Bigr\rfloor $$

And using \$ F(2) = F(-1) = 1 \$ and \$ F(n+3) = 4F(n) + F(n-3) \$, we define a derived sequence \$ G(n) \$ such that

$$ G(0)=G(1)=\frac12, G(n+2)=4G(n+1)+G(n) $$

Then the desired value is \$ a(n) = \lfloor G(n) \rfloor \$.

How it works: the code

⌊⊃⌽(4∘⊥,⊃)⍣⎕÷2 2  ⍝ Input: n
            ÷2 2  ⍝ 2-element vector [.5 .5] i.e. [G(1) G(0)]
   (4∘⊥,⊃)⍣⎕      ⍝ Derive [G(x+2) G(x+1)] from [G(x+1) G(x)] n times:
    4∘⊥           ⍝   G(x+2) = 4×G(x+1) + G(x)
        ⊃         ⍝   G(x+1) as first element of the vector
       ,          ⍝   Concatenate
 ⊃⌽               ⍝ Get the last element of the result vector, i.e. G(n)
⌊                 ⍝ Floor

Answer 17

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

Answer 18

Mathematica, 32 27 bytes

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

Credit to xnor. Saved 5 bytes thanks to JungHwan Min.

Answer 19

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.

Answer 20

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)

Answer 21

Japt, 10 bytes

Uo@MgX*3Ãx

Try it online!

Thanks ETHproductions :)

Answer 22

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

Answer 23

Forth (gforth), 47 bytes

: f 3 * 1- 0 1 rot 0 do tuck + loop d>s 1- 2/ ;

Try it online!

Uses the first formula for OEIS a(n) = (Fibonacci(3*n + 2) - 1)/2, since the code for Fibonacci is relatively small in forth.

: f              \ start a new word definition
  3 * 1-         \ multiply by 3 and subtract 1 (simplified form of 3*(n-1) + 2 )
  0 1 rot 0      \ create starting Fibonacci values and set up loop parameters
  do tuck + loop \ Fibonacci code - iteratively copy top value add top 2 stack values
  d>s            \ drop the top stack value
  1- 2/          \ subtract 1 and divide result by 2
;                \ end word definition

Answer 24

Husk, 8 bytes

Σ↑Θnİ0İf

Try it online!

painfully slow due to intersecting two infinite lists.

Answer 25

PARI/GP, 21 bytes

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

\ is the integer quotient.

Answer 26

Excel (Version 1911), 119 Bytes

Using iterative calculations (Maximum iteration 1024)

A1 'Input
B1 =IF(B1=4^5,1,B1+1)
C1 =SEQUENCE(A1*3-1)-1
D1 =IF(B1=1,N(C1#>0),IF(C1#=B1,SUM(INDEX(D1#,B1-{0,1})),D1#))
E1 =SUM(D1#*(MOD(D1#,2)=0)) 'Output

Tests

Answer 27

GolfScript, 46 bytes

(:m;5 2 -1??:i 3*5\- 2i-m?*3i*5+2i+m?*+-10+20/

Ignore the floating point, TIO isn't perfect.

Yeah, yeah. I cheated. This is just a fancy arithmetic equation to calculate the result. Works in O(1) time, though, assuming a^n can be calculated in O(1) time, which might not be true.

(:m;5 2 -1??:i 3*5\- 2i-m?*3i*5+2i+m?*+-10+20/ #Sum the first n even F
(:m;                                           #Set m to our input minus one, pop the value from the list. 
    5 2 -1??:i                                 #Set i to sqrt(5), but don't pop it since we're gonna use it (saves 1 byte)
               3*5\-                           #5-3sqrt(5)
                     2i-m?                     #[2-sqrt(5)]^m
                          *                    #Multiply those two together
                           3i*5+2i+m?*         #Same as the above lines, but + instead of -.
                                      +        #Add the left part with the right part
                                       -10+    #Add -10 (-10+20/ and 10- 20/ are the same size)
                                           20/ #Divide by twenty.

Try it online!

Answer 28

05AB1E, 7 bytes

L<3*ÅfO

Try it online!

Answer 29

GolfScript, 15 bytes

0.@{.4*@2++}\*;

This one actually does the "operation" using a neat little trick I found. The sum is actually just a 0, 0 leading sequence, with a(n) = 4a(n-1) + a(n-2) + 2. So I do that.

0.@{.4*@2++}\*; #Print the sum of the first n even F
0.              #Add two 0s to the stack. [n 0 0]
  @             #Bring the n up front. [0 0 n]
   {       }    #A block of "do something" [0 0 n {}]
   {       }\   #Bring n to the front again [0 0 {} n]
   {       } *  #Perform the block n times on the stack below it [0 0]
   {.      }    #Duplicate our top element (a[n-1] a[n-1])
   { 4*    }    #Multiply the dupe by 4 (a[n-1] 4a[n-1])
   {   @   }    #Bring up our bottom element (a[n-1] 4a[n-1] a[n-2])
   {    2++}    #4a[n-1]+a[n-2]+2 = a[n]
   {       }    #Stack is now a[n-1] a[n], so we dop the loop until our n is right!
              ; #The stack has a[n-1] a[n], but our "n" in question is 1 too high
                #So we pop the top element, leaving a[n-1], W5.

Try it online!

Answer 30

Jelly, 6 bytes

Ḷ×3ÆḞS

Try it online!

Uses the formula

$$a(n) = \sum_{i=0}^{n-1}f(3i)$$

where \$f(n)\$ is the \$n\$-th Fibonacci number

How it works

Ḷ×3ÆḞS - Main link. Take n on the left
Ḷ      - [0, 1, 2, ..., n-1]
 ×3    - [0, 3, 6, ..., 3n-3]
   ÆḞ  - n'th Fibonacci number for each
     S - Sum