bash - 如何找到系列 : 2 3 4 6 9 13 19 28 42 63 . 中的第百万个数字 ..？

Question

在我的比赛中达到 3000 大约需要几分钟，但我需要知道系列中的百万分之一。该定义是递归的，因此除了计算百万分之一之前的所有内容外，我看不到任何捷径。您如何快速计算该系列中的百万分之一？

系列定义

n_{i+1} =\floor{ 3/2 * n_{i} } 和 n_{0}=2。

有趣的是，只有一个站点根据 Google 列出了该系列:this one .

Bash 代码太慢

#!/bin/bash

function series 
{
        n=$( echo "3/2*$n" | bc -l | tr '\n' ' ' | sed -e 's@\\@@g' -e 's@ @@g' );
                                        # bc gives \ at very large numbers, sed-tr for it
        n=$( echo $n/1 | bc )           #DUMMY FLOOR func
}

n=2
nth=1

while [ true ]; #$nth -lt 500 ];
do
        series $n                        # n gets new value in the function through global value
        echo $nth $n
        nth=$( echo $nth + 1 | bc )     #n++
done

Answer 1

你可以很容易地通过考虑二进制问题来解决这个问题。 Floor(3/2*i) 基本上是右移、截断和相加。在伪代码中:

0b_n[0]   = 10              // the start is 2
0b_n[1]   = 10 + 1(0) = 11  // shift right, chop one bit off and add 
0b_n[i+1] = 0b_n[i] + Truncate(ShiftRight(0b_n[i]))

这对于以任何形式实现都应该是相当快的。

我刚刚在 Mathematica 中实现了这一点，似乎 BitShiftRight 操作也切断了单位位置之后的位，因此自动处理。这是一个类轮:

In[1] := Timing[num = Nest[(BitShiftRight[#] + #) &, 2, 999999];]
Out[2] = {16.6022, Null}

16 秒，数字打印得很好，虽然它很长:

In[2] := IntegerLength[num]
Out[2] = 176092

In[3] := num
Out[3] = 1963756...123087

完整结果 here .