生成Linus序列

Question

定义

来自OEIS A006345的描述：

要找到a(n)，可以考虑1或2。对于每一个，查找最长的重复后缀，也就是说，对于每个a(n)=1,2，查找具有序列a(1),...,a(n)以ss结尾的属性的最长序列s。使用导致这种后缀较短的数字。a(1) = 1。

编写的示例

a(1)=1。

如果是a(2)=1，我们将得到序列1 1，其中从末尾最长的加倍子字符串是1。如果是a(2)=2，那么它将是空子字符串。因此，a(2)=2.

当n=6时，我们在1 2 1 1 2 1和1 2 1 1 2 2之间进行选择。在第一选择中，1 2 1从结尾开始连续加倍。在第二种选择中，则是2。因此，a(6)=2.

当n=9时，我们在1 2 1 1 2 2 1 2 1和1 2 1 1 2 2 1 2 2之间进行选择。在第一个选择中，最长的双倍连续子字符串是2 1，而在第二个选择中，1 2 2在结束时连续加倍。因此，a(9)=1.

任务

给定n，返回a(n)。

规范

• n将呈阳性。
• 您可以使用0索引而不是1索引。在这种情况下，请在你的答复中说明这一点。而且，在这种情况下，n也可以是0。

测试案例

测试用例是1索引的。但是，您可以使用0索引.

n  a(n)
1  1
2  2
3  1
4  1
5  2
6  2
7  1
8  2
9  1
10 1
11 2
12 1
13 2
14 2
15 1
16 1
17 2
18 1
19 1
20 1

参考资料

• WolframMathWorld
• 强制性OEIS A006345

Answer 1

Python，137个字节

def a(n,s=[0],r=lambda l:max([0]+filter(lambda i:l[-i:]==l[-i*2:-i],range(len(l))))):
 for _ in[0]*n:s+=[r(s+[0])>r(s+[1])]
 return-~s[n]

此解决方案使用基于0的索引.

Answer 2

Mathematica，84个字节

a@n_:=a@n=First@MinimalBy[{1,2},Array[a,n-1]~Append~#/.{___,b___,b___}:>Length@{b}&]

Answer 3

Python2，94个字节

import re
s='1'
exec"s+=`3-int(re.search(r'(.*)(.)\\1使用基于0的索引。在艾德龙上进行测试。,s).groups()[1])`;"*input()
print s[-1]

使用基于0的索引。在艾德龙上进行测试。