无交叉序列计算

很抱歉发布此问题。

显然,这是一个著名的序列,叫做Wythoff序列,有一个简洁的公式,由a[n]=[n*phi]给出,其中[x]=x和phi的整数部分是黄金比率。

计算[ n ] phi),我们可以将phi近似为连续斐波那契数的比值,给出一个o(logn loglogn)算法。(O(log n)对O(log n)位数字进行算术运算的时间)。

这是它的开始

1 2 3 4 5 6 7 8 ... A[1] = 1, cross 2
1 X 3 4 5 6 7 8 ... A[2] = 1, cross 3
1 X X 4 5 6 7 8 ... A[3] = 1, cross 4
...

数字1从不交叉,因为可以交叉的最小数字是1+1==2。

所以有一个常数时间算法:所有n的a[n]=1。