The Lucas-nacci Numbers

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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)

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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

Answer 12

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~#&

Answer 13

R, 55 bytes

A=c(0,1,1,4);for(x in 4:scan()+1)A[x]=3*A[x-2]-A[x-4];A

Try it online!

• -24 bytes thanks to JayCe

Answer 14

Mathematica, 41 bytes

LinearRecurrence[{0,3,0,-1},{0,1,1,4},#]&

Answer 15

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.

Answer 16

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.

Answer 17

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}

Answer 18

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

Answer 19

C++ Template Meta Programming, 130 bytes

template<int X>struct L{enum{v=3*L<X-2>::v-L<X-4>::v};};
#define D(X,A) template<>struct L<X>{enum{v=A};};
D(0,0)D(1,1)D(2,1)D(3,4)

Recursive definitions somehow cry for C++TMP, usage:

L<x>::v

with x being the A(x) you like.