卢卡斯-纳奇数

Question

背景

大多数人都熟悉斐波纳契数字F(n)：

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

它们由递归函数F(n) = F(n-1) + F(n-2)与F(0)=0和F(1)=1组成。A000045

一个密切相关的序列是Lucas数L(m)：

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

它们由递归函数L(m) = L(m-1) + L(m-2)与L(0)=2和L(1)=1组成。A000032

我们可以根据偶数/奇数指数在这两个序列之间交替使用构造。

A(x) = \begin{cases} F(x) & x \equiv 0 \pmod 2 \\ L(x) & x \equiv 1 \pmod 2 \\ \end{cases}

例如，自A(4)以来，F(4)等于4 \bmod 2 \equiv 0。我们将此序列命名为Lucas-nacci数字，A(x)：

0，1，1，4，3，11，8，29，21，76

这可以由递归函数A(x) = 3A(x-2) - A(x-4)与A(0)=0, A(1)=1, A(2)=1和A(3)=4组成。A005013

挑战

给定输入n，如上文所述，输出n+1数字到并包括A(n)的顺序。最少字节(或字节等价物，如LabVIEW，由元个体决定)获胜。

输入

一个非负整数n。

输出

与从A(0)到A(n)的Lucas数的子序列对应的数字列表.如上文所述，该列表必须按顺序排列。

规则

• 标准代码-高尔夫球规则和漏洞限制应用。
• 标准输入/输出规则应用。
• 输入数字可以是任何适当的格式:一元或十进制，从STDIN读取，函数或命令行参数等-您的选择。
• 输出可以打印到STDOUT，或者作为函数调用的结果返回。如果打印，必须包括适当的分隔符来区分数字(空格分隔，逗号分隔，等等)。
• 此外，如果输出到STDOUT，则周围的空格、尾换行符等都是可选的。
• 如果输入是一个非整数或负整数，程序可以做任何事情或什么也不做，因为行为是未定义的。

示例

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

ES6，65字节

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

使用问题中给出的递推关系。

Answer 2

布氏对数，51字节

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

这将一个数字作为输入，并打印到STDOUT列表，并将每个数字分隔开来。

解释

§ 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

子谓词1的第一条规则中的剪切!是必要的，这样当我们回溯(\)时，我们就不会以无限循环结束，在这个循环中，解释器将尝试输入小于4的第二个规则。

Answer 3

Mathematica，56字节

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

非常简单的实现。定义一个助手函数f，然后计算为一个未命名的函数，该函数将f应用于一个范围，以获得所有结果。这让人觉得不必要的麻烦。

但是，一个未命名的函数似乎要长一个字节：

Switch[#,0,0,1,1,2,1,3,4,_,3#0[#-2]-#0[#-4]]&/@0~Range~#&