Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Background

Most everyone is familiar with the Fibonacci numbers F(n):

0, 1, 1, 2, 3, 5, 8, 13, 21 ...

These are formed by the recursion function F(n) = F(n-1) + F(n-2) with F(0)=0 and F(1)=1. A000045

A closely related sequence is the Lucas numbers L(m):

2, 1, 3, 4, 7, 11, 18, 29 ...

These are formed by the recursion function L(m) = L(m-1) + L(m-2) with L(0)=2 and L(1)=1. A000032

We can alternate between the two sequences based on even/odd indices, with the construction
A(x) = F(x) if x mod 2 = 0 and A(x) = L(x) otherwise. For example, A(4) is equal to F(4) since 4 mod 2 = 0. We'll call this sequence the Lucas-nacci Numbers, A(x):

0, 1, 1, 4, 3, 11, 8, 29, 21, 76 ...

This can be formed by the recursion function A(x) = 3*A(x-2) - A(x-4) with A(0)=0, A(1)=1, A(2)=1, and A(3)=4. A005013

Challenge

Given input n, output the sequence of n+1 numbers up to and including A(n) as described above. Fewest bytes (or byte-equivalents, such as for LabVIEW, as determined individually on Meta) wins.

Input

A single non-negative integer n.

Output

A list of numbers that correspond to the subsequence of Lucas-nacci numbers from A(0) to A(n). The list must be in sequential order as described above.

Rules

  • Standard code-golf rules and loophole restrictions apply.
  • Standard input/output rules apply.
  • Input number can be in any suitable format: unary or decimal, read from STDIN, function or command-line argument, etc. - your choice.
  • Output can be printed to STDOUT or returned as a result of the function call. If printed, suitable delimiters to differentiate the numbers must be included (space-separated, comma-separated, etc.).
  • Additionally, if output to STDOUT, surrounding whitespace, trailing newline, etc. are all optional.
  • If the input is a non-integer or a negative integer, the program can do anything or nothing, as behavior is undefined.

Examples

Input -> Output
0 -> 0
5 -> 0, 1, 1, 4, 3, 11
18 -> 0, 1, 1, 4, 3, 11, 8, 29, 21, 76, 55, 199, 144, 521, 377, 1364, 987, 3571, 2584
share|improve this question
    
Is newline considered an accepted delimiter? – corsiKa Feb 8 at 20:51
    
@corsiKa Sure, that's fine. – TimmyD Feb 8 at 21:26

18 Answers 18

up vote 9 down vote accepted

Jelly, 12 bytes

;2U+¥Ð¡-,1ZḢ

Try it online!

Background

We can extend F and L to -1 by defining F(-1) = 1 and L(-1) = -1. This is consistent with the recursive function.

Our program starts with

-1  1
 0  2

In each step, to form the next pair, we reverse the last pair and add it to the penultimate pair. For example:

[0, 2] U+¥ [-1, 1] -> [2, 0] + [-1, 1] -> [1, 1]

If we continue this process for a few more steps, we get

-1  1
 0  2
 1  1
 1  3
 4  2
 3  7
11  5

The Lucas-nacci sequence is simply the left column.

How it works

;2U+¥Ð¡-,1ZḢ  Niladic link. No implicit input.
              Since the link doesn't start with a nilad, the argument 0 is used.

;2            Concatenate the argument with 2, yielding [0, 2].
       -,1    Yield [-1, 1]. This is [L(-1), F(-1)].
    ¥         Create a dyadic chain of the two atoms to the left:
  U             Reverse the left argument.
   +            Add the reversed left argument and the right one, element-wise.
     С       For reasons‡, read a number n from STDIN.
              Repeatedly call the dyadic link U+¥, updating the right argument with
              the value of the left one, and the left one with the return value.
              Collect all intermediate results.
          Z   Zip the list of results, grouping the first and seconds coordinates.
           Ḣ  Head; select the list of first coordinates.

С peeks at the two links to the left: 2 and U+¥. Since the leftmost one is a nilad, it cannot be the body of the loop. Therefore, U+¥ is used as body and a number is read from input. Since there are no command-line arguments, that number is read from STDIN.

share|improve this answer
2  
I get the impression that you do this kind of stuff (golfing in Jelly) for a living. Which makes me terrified. – Draco18s Feb 8 at 16:33
21  
If anyone sorts out how to golf (code) for a living, please ping me in chat. Asking for a friend... – Martin Ender Feb 8 at 16:33
1  
So basically you're just calculating both sequences, but reversing at each step, which effectively switches between the sequences. – Neil Feb 8 at 19:48
1  
@Neil Yes, exactly. It avoids interleaving the sequences afterwards, which is slightly longer. – Dennis Feb 8 at 20:01

CJam, 21 20 bytes

Thanks to Sp3000 for saving 1 byte.

TXX4ri{1$3*4$-}*?;]p

Test it here.

Explanation

Simply uses the recurrence given in the challenge spec.

TXX4 e# Push 0 1 1 4 as base cases.
ri   e# Read input and convert to integer N.
{    e# Run this N times...
  1$ e#   Copy a(n-2).
  3* e#   Multiply by 3.
  4$ e#   Copy a(n-4).
  -  e#   Subtract.
}*
?;   e# Discard the last three values, using a ternary operation and popping the result.
]p   e# Wrap the rest in an array and pretty-print it.
share|improve this answer
1  
Who (or what) is Sp3000 that you thank on every answer? – CJ Dennis Feb 9 at 2:20
    
5  
@CJDennis Some say he is the greatest Python golfer to ever live. Some say he lives in a secluded cabin on top of a mountain, built out of a minimal number of logs. Some say he is the voice in the back of our heads, which nags us when we post solutions which can be golfed further. But most of us just say he's the user whose profile Martin linked. – Mego Feb 9 at 8:38

Perl 6, 42 bytes

{(0,1,1,4,{$^b;$^d;3*$^c-$^a}...*)[0..$_]}

usage

> my &f = {(0,1,1,4,{$^b;$^d;3*$^c-$^a}...*)[0..$_]}
-> ;; $_? is raw { #`(Block|184122176) ... }
> f(0)
(0)
> f(5)
(0 1 1 4 3 11)
> f(18)
(0 1 1 4 3 11 8 29 21 76 55 199 144 521 377 1364 987 3571 2584)
share|improve this answer
1  
The clearest lambda that I have come up with is {( (0,1,*+*...*) Z (2,1,*+*...*) ).flat.rotor( 1=>2, 1=>0 )[ 0..$_ ].flat} – Brad Gilbert b2gills Feb 9 at 18:30
    
Given that the exact wording is "given n", you could save a byte with: (0,1,1,4,{$^b;$^d;3*$^c-$^a}...*)[^(n+1)]. – raiph Feb 10 at 3:58

ES6, 65 bytes

n=>[...Array(n)].map(_=>a.shift(a.push(a[2]*3-a[0])),a=[0,1,1,4])

Uses the recurrence relation given in the question.

share|improve this answer

Haskell, 59, 57, 56, 52, 51 bytes

l a=2*mod a 2:scanl(+)1(l a)
f n=[l i!!i|i<-[0..n]]

Series definition adapted from this answer.

Less golfed:

fibLike start = start : scanl (+) 1 (fibLike start)
whichStart i = (2*mod i 2)
lucasNacci i = fibLike (whichStart i) !! i
firstN n = [ lucasNacci i | i <- [0..n]]

fibLike start gives an infinite list, defined: f(0)=start, f(1)=1, f(n)=f(n-1) + f(n-2). whichStart i returns 2 for odd input (Lucas series) or 0 for even (Fibonacci series). lucasNacci i gives the ith Lucas-nacci number. firstN n maps over the list.

One byte saved by Boomerang.

share|improve this answer
1  
I think you can get one more byte by moving 2*mod i 2 into l then you can remove the parenthesis. Like this: l a=2*mod a 2:scanl(+)1(l a) and f n=[l i!!i|i<-[0..n]] – Boomerang Feb 8 at 17:10
    
@Boomerang Yup, that works. Thank you – Michael Klein Feb 8 at 22:29

Retina, 70 62 59 bytes

1
¶$`1
m`^(11)*1$
$&ff
m`$
 f
+`1(f*) (f*)
$2 $2$1
 f*

f
1

Try it online

  • Input is in unary base, n 1s.
  • 1? $`¶ - Create a line for each number from 0 to n:  , 1, 11, 111, 1111, ...
  • m`^(11)*1$ $&ff - Append ff to odd lines. This will seed the function with L(0)=2.
  • m`$  f - Append  f to all lines (note the space). This seeds the function with 0 and 1 for Fibonacci numbers, and 2 and 1 for Lucas numbers.
  • +`1(f*) (f*) $2 $2$1 - Loop: calculate F(n+1) = F(n) + F(n-1) while there are still 1s.
  •  f*   - Remove F(n+1) from the end of each line.
  • Replace fs back to 1s. If this isn't needed and we can stay with fs, the length is just 55 bytes.
share|improve this answer

Oracle SQL 11.2, 218 216 201 bytes

WITH v(a,b,c,d,i)AS(SELECT 0,1,1,4,3 FROM DUAL UNION ALL SELECT b,c,d,3*c-a,i+1 FROM v WHERE i<:1)SELECT SIGN(LEVEL-1) FROM DUAL WHERE LEVEL-1<=:1 CONNECT BY LEVEL<4UNION ALL SELECT d FROM v WHERE:1>2;

Un-golfed

WITH v(a,b,c,d,i) AS 
(
  SELECT 0,1,1,4,3 FROM DUAL 
  UNION ALL 
  SELECT b,c,d,3*c-a,i+1 FROM v WHERE i<:1
)
SELECT SIGN(LEVEL-1) FROM DUAL WHERE LEVEL-1<=:1 CONNECT BY LEVEL<4
UNION ALL SELECT d FROM v WHERE:1>2;

I managed to gain a few bytes by using (abusing ?) the SIGN function to generate the first 3 elements of the sequence.

share|improve this answer

Japt, 25 22 21 bytes

Uò £MgXf2)+X%2*Mg°X)r

Test it online!

Background

It's somewhat difficult to create a Fibonacci sequence in Japt, but we have a built-in Mg to do it for us. However, this only gives us the Fibonacci sequence, not the Lucas sequence. We can accomplish the Lucas sequence fairly easily using this trick:

N    F(N-1)  F(N+1)  F(N-1)+F(N+1)
0    1       1       2
1    0       1       1
2    1       2       3
3    1       3       4
4    2       5       7
5    3       8       11
6    5       13      18
7    8       21      29

As you can see, F(N-1) + F(N+1) is equal to L(N) for all N. However, since we only need Lucas numbers on the odd indices, we can combine the two formulas into one:

N    N-N%2  N+N%2    F(N-N%2)  F(N+N%2)*(N%2)  F(N-N%2)+F(N+N%2)*(N%2)
0    0      0        0         0               0
1    0      2        0         1               1
2    2      2        1         0               1
3    2      4        1         3               4
4    4      4        3         0               3
5    4      6        3         8               11
6    6      6        8         0               8
7    6      8        8         21              29

How it works

Uò £  MgX-1 +X%2*Mg° X)r
Uò mX{MgX-1 +X%2*Mg++X)r

             // Implicit: U = input integer
Uò mX{       // Create the inclusive range [0..U], and map each item X to:
MgXf2)+      //  Floor X to a multiple of 2, calculate this Fibonacci number, and add:
+X%2*Mg++X)  //  Calculate the (X+1)th Fibonacci number and multiply by X%2.
)r           //  Round the result. (The built-in Fibonacci function returns
             //  a decimal number on higher inputs.)
share|improve this answer

Mathematica, 52 51 bytes

If[#>2,3#0[#-2]-#0[#-4],#-If[#>1,1,0]]&/@0~Range~#&

Very similar idea to Martin's above, I spent some time trying to find a shorter way of defining the "base cases" for the function. Polynomial interpolation was a bust, so I went for this, using the extension into negatives to yield a fairly short definition.

share|improve this answer

Mathematica, 56 bytes

f@0=0
f@1=f@2=1
f@3=4
f@n_:=3f[n-2]-f[n-4];
f/@0~Range~#&

Very straightforward implementation. Defines a helper-function f and then evaluates to an unnamed function which applies f to a range to get all the results. This feels unnecessarily cumbersome.

A single unnamed function seems to be one byte longer though:

Switch[#,0,0,1,1,2,1,3,4,_,3#0[#-2]-#0[#-4]]&/@0~Range~#&
share|improve this answer

MATL, 17 18 bytes

0ll4i:"y3*5$y-](x

Almost direct translation of Martin's CJam answer.

Try it online!

0ll4       % push first four numbers: 0,1,1,4
i:         % input n and generate array [1,2,...,n]
"          % for loop. Repeat n times
  y        % copy second-top element from stack
  3*       % multiply by 3
  5$y      % copy fifth-top element from stack
  -        % subtract. This is the next number in the sequence
]          % end loop
(x         % indexing operation and delete. This gets rid of top three numbers
share|improve this answer

Brachylog, 51 bytes

:0re{:4<:[0:1:1:4]rm!.|-4=:1&I,?-2=:1&*3-I=.}w,@Sw\

This takes a number as input and prints to STDOUT the list, with spaces separating each number.

Explanation

§ Main predicate

:0re{...}               § Enumerate integers between 0 and the Input, pass the integer 
                        § as input to sub-predicate 1      
         w,@Sw          § Write sub-predicate 1's output, then write a space
              \         § Backtrack (i.e. take the next integer in the enumeration)


§ Sub-predicate 1

:4<                     § If the input is less than 4
   :[0:1:1:4]rm!.       § Then return the integer in the list [0,1,1,4] at index Input

|                       § Else

-4=:1&I,                § I = sub_predicate_1(Input - 4)
        ?-2=:1&*3-I=.   § Output = sub_predicate_1(Input - 2) * 3 - I

The cut ! in the first rule of sub-predicate 1 is necessary so that when we backtrack (\), we don't end up in an infinite loop where the interpreter will try the second rule for an input less than 4.

share|improve this answer

Groovy, 50 Bytes

x={a,b=0,c=1,d=1,e=4->a<0?:[b,x(a-1,c,d,e,3*d-b)]}

This defines the function x, which takes in n as it's first argument and has the base case of the first four numbers in the Fibocas sequence as default arguments for the rest of the function.

a here is n. b, c, d, and e are the next four elements in the sequence.

It decrements n and recurses until n is less than zero-- when it recurses, it adds on to the ultimate return value the first element in its current sequence. The new values for the next four elements in the sequence are given to the recursive call-- the last three elements are shifted over to be the first three, and a new fourth element is generated from two of the previous elements using 3*d-b.

It delimits new values with list nestings, as groovy can return multiple values by stuffing them into a list-- so each call returns the current first element and the result of recursion, which will be its own list.

share|improve this answer

Pylons, 19

This is a pretty direct translation of Martin's approach.

0114{@-4@-33*-,i}=4

How it works:

0114    # Push 0, 1, 1, 4 to the stack.
{       # Start a for loop.
 @-4    # Get the stack element at index -4
 @-3    # Get the stack element at index -3
 3      # Push 3 to the stack.
 *      # Multiply the top two elements of the stack.
 -      # Subtract the top two elements of the stack.
  ,     # Switch to loop iterations.
 i      # Get command line args.
}       # End for loop.
=4      # Discard the top 4 elements of the stack.
share|improve this answer

R, 79 bytes

A=function(x)if(x<4)c(0,1,1,4)[x+1]else 3*A(x-2)-A(x-4);cat(sapply(0:scan(),A))
share|improve this answer

DUP, 32 bytes

[a:0 1$4[a;1-$a:][1ø3*4ø-]#%%]

Try it here!

An anonymous lambda that leaves a sequence of numbers on the stack. Usage:

8[a:0 1$4[a;1-$a:][1ø3*4ø-]#%%]!

Explanation

[                              {start lambda}
 a:                            {save input number to a}
   0 1$4                       {base cases to get us started}
        [       ][       ]#    {while loop}
         a;1-$a:               {a--, check if a>0}
                  1ø3*4ø-      {3*stack[n-2]-stack[n-4]}

                           %%  {discard top 2 stack items}
                             ] {end lambda}
share|improve this answer

Python 2, 71 bytes

def a(n,x=0,y=1,z=2,w=1,p=0):
 if~n:print[x,z][p];a(n-1,y,x+y,w,z+w,~p)

This definitely seems too long. However, I was pleased that I got to use the bitwise not operator...twice. Once as kind of a parity flip back and forth, and once to terminate the recursion when n reaches -1.

The variable p will always be either 0 or -1, so it will alternate between entries 0 or -1 of the list. (Choosing entry -1 of a Python list means choosing the last element.)

share|improve this answer

Mathematica, 41 bytes

LinearRecurrence[{0,3,0,-1},{0,1,1,4},#]&
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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