我如何找到该系列中的百万号:2 3 4 6 9 13 19 28 42 63 ...？

Question

在我的comp中达到3000需要大约几分钟,但我需要知道系列中的第一百万个数字.该定义是递归的,所以我看不到任何快捷方式,除了计算百万分之前的所有内容.你如何快速计算系列中的百万号？

系列定义

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

有趣的是,只有一个网站根据谷歌列出该系列:这一个.

太慢的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

您可以通过考虑二进制问题轻松解决此问题.楼层(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

完整结果在这里.

Answer 2

你几乎找到了它.下一次,查看在线百科全书系列.

这是条目:http://oeis.org/A061418

     FORMULA    

a(n) = ceiling[K*(3/2)^n] where K=1.08151366859...

The constant K is 2/3*K(3) (see A083286). - Ralf Stephan, May 29, 2003 

那说:

>>> def f(n):
...     K = 1.08151366859
...     return int(ceil(K*(1.5)**n))

完整性测试:

>>> for x in range(1, 10):
...     print f(x)
...     
2
3
4
6
9
13
19
28
42

真棒!现在如何1000000:

>>> f(1000000)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 3, in f
OverflowError: (34, 'Result too large')

好吧,我试过了.:]但是你明白了.

再次编辑:找到解决方案!请参阅Timo或Lasse V. Karlsen的回答.

编辑:使用Timo的位移想法:

import gmpy
n=gmpy.mpz(2)
for _ in xrange(10**6-1):
    n+=n>>1
print(n)

产量

1963756763 ... 226123087(176092位)

% time test.py > test.out

real    0m21.735s
user    0m21.709s
sys 0m0.024s

Answer 3

你的脚本如此慢的原因是它产生bc了三次,tr一次一次,sed一次循环.

重写整个事情bc并sed在最后完成.我的测试表明,bc-only版本的速度提高了600多倍.在旧的慢速系统上花了不到16分钟bc才能找到第100,000个值(仅打印最后一个).

另外,请注意您的"floor"函数实际上是"int".

#!/usr/bin/bc -lq
define int(n) {
    auto oscale
    oscale = scale
    scale = 0
    n = n/1
    scale = oscale
    return n
}

define series(n) {
    return int(3/2*n)
}

n = 2
end = 1000
for (count = 1; count < end; count++ ) {
    n = series(n)
}
print count, "\t", n, "\n"
quit

请注意,这print是一个扩展,有些版本bc可能没有它.如果是这样,只需自己引用变量,并输出其值.

现在你可以这样做chmod +x series.bc并调用它:

./series.bc | tr -d '\n' | sed 's.\\..g'

Answer 4

我使用了以下Java程序:

import java.math.*;

public class Series {
    public static void main(String[] args) {
        BigInteger num = BigInteger.valueOf(2);
        final int N = 1000000;

        long t = System.currentTimeMillis();
        for (int i = 1; i < N; i++) {
            num = num.shiftLeft(1).add(num).shiftRight(1);
        }
        System.out.println(System.currentTimeMillis() - t);
        System.out.println(num);
    }
}

裁剪的输出:( 在pastebin上的完整输出)

516380 (milliseconds)
196375676351034182442....29226123087

所以我的适度机器花了大约8.5分钟.我用过-Xmx128M,但不确定这是否真的有必要.

可能有更好的算法,但这总共需要10分钟,包括编写天真的实现和运行程序.

样品运行

• N=500(同意OEIS 061418)
• N=100K(1445232038814....522773508)

Answer 5

这是一个Python版本,在我10岁的笔记本电脑上运行大约需要220秒:

import math;
import timeit;

def code():
  n = 2
  nth = 1

  while nth < 1000000:
    n = (n * 3) >> 1
    nth = nth + 1

  print(n);

t = timeit.Timer(setup="from __main__ import code", stmt="code()");
print(t.timeit(1));

它会产生与此答案在pastebin上相同的结果(也就是说,我验证了它的开头和结尾,而不是所有内容.)