19
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ https://oeis.org/A099919 \$\endgroup\$ – xnor Jan 3 '17 at 23:42
  • \$\begingroup\$ @EasterlyIrk The test cases imply the latter, but it should be explicitly stated. \$\endgroup\$ – Mego Jan 3 '17 at 23:49
  • \$\begingroup\$ @Mego yeah, I figured as much. \$\endgroup\$ – Rɪᴋᴇʀ Jan 3 '17 at 23:49
  • 9
    \$\begingroup\$ 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. \$\endgroup\$ – Rɪᴋᴇʀ Jan 4 '17 at 0:42
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – Zgarb Jan 4 '17 at 7:54

20 Answers 20

8
\$\begingroup\$

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.

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

Python, 33 bytes

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

Try it online

Magic formula!

\$\endgroup\$
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ – Theo Jan 4 '17 at 13:14
  • \$\begingroup\$ @xnor, Any reference to this magic formula? \$\endgroup\$ – TheChetan Jan 4 '17 at 13:43
  • \$\begingroup\$ @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 \$\endgroup\$ – Titus Jan 4 '17 at 13:50
7
\$\begingroup\$

Python 2, 35 bytes

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

Try it online!

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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)

\$\endgroup\$
6
\$\begingroup\$

Pyke, 6 bytes

3m*.bs

Try it here!

3m*    -   map(i*3, range(input))
   .b  -  map(nth_fib, ^)
     s - sum(^)
\$\endgroup\$
4
\$\begingroup\$

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

}
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 27 21 bytes

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

Fibonacci[3#-1]/2-.5&
\$\endgroup\$
  • 1
    \$\begingroup\$ Might the (Fibonacci(3*n+2)-1)/2 formula be shorter? \$\endgroup\$ – xnor Jan 4 '17 at 0:38
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – BrainSteel Jan 5 '17 at 21:30
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Christian Sievers Jan 4 '17 at 12:44
  • \$\begingroup\$ @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! \$\endgroup\$ – Dylan Meeus Jan 4 '17 at 12:49
1
\$\begingroup\$

Mathematica, 32 27 bytes

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

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

\$\endgroup\$
  • \$\begingroup\$ Surely Mathematica has Fibonacci and it's shorter to do either (Fibonacci(3*n+2) - 1)/2 or write the sumi? \$\endgroup\$ – xnor Jan 4 '17 at 0:19
  • \$\begingroup\$ @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?. \$\endgroup\$ – Dennis Jan 4 '17 at 18:13
  • \$\begingroup\$ @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. \$\endgroup\$ – Dennis Jan 4 '17 at 18:15
  • \$\begingroup\$ @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. \$\endgroup\$ – JungHwan Min Jan 4 '17 at 18:16
  • \$\begingroup\$ 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.) \$\endgroup\$ – JungHwan Min Jan 4 '17 at 18:24
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I managed to match your bytecount without recursion :) \$\endgroup\$ – JAD Jan 5 '17 at 14:41
  • \$\begingroup\$ @JarkoDubbeldam Nice! I've ditched the recursion also and made a one-byte improvement :) \$\endgroup\$ – rturnbull Jan 5 '17 at 15:30
  • \$\begingroup\$ Nice, what exactly does desctools::fibonacci do that numbers::fibonacci cant? Because that mist be a bit shorter. \$\endgroup\$ – JAD Jan 5 '17 at 15:39
  • \$\begingroup\$ Oh nevermind, found it. Sweet, the other implementations I found don't support asking for multiple numbers at once. \$\endgroup\$ – JAD Jan 5 '17 at 15:40
  • 1
    \$\begingroup\$ @JarkoDubbeldam Yeah, ``gmp::fibnum'' returns objects of type bigz, which the *apply class of functions converts to type raw because reasons... \$\endgroup\$ – rturnbull Jan 5 '17 at 15:50
1
\$\begingroup\$

Japt, 10 bytes

Uo@MgX*3Ãx

Try it online!

Thanks ETHproductions :)

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

PARI/GP, 21 bytes

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

\ is the integer quotient.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.