如何找到该系列中的第一百万个数字：2 3 4 6 9 13 19 28 42 63 …？

https://stackoverflow.com/questions/2840593

27-09-2019
|

题

在我的比较中达到 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

解决方案

您可以轻松地考虑在二进制问题的解决这个问题。地板（3/2 * i）的基本上右移，截断和ADD。在伪码：

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]))

此应该相当快的任何形式来实现。

我刚才提出的这个实现在数学和它似乎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

完整结果 rel="noreferrer">。

其他提示

你差一点就找到了。下次，请查看整数级数在线百科全书.

这是条目： 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')

嗯，我尝试过。 :] 但你明白了。

再次编辑： 解决办法找到了！看蒂莫或者拉塞 V.卡尔森的答案。

编辑： 使用 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

原因你的脚本是如此之慢是它的产卵bc三次，tr一次sed一次的循环。

重写在bc整个事情并执行sed末。我的测试表明，只有bc版本快600倍。仅仅过了不足16分钟，bc版本旧的慢行系统上找到100,000值（仅打印最后一个）。

另外，还要注意你的 “地板” 功能其实是 “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'

我使用了以下 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)

这是一个 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上有（也就是说，我验证了它的开始和结束，而不是所有内容。）

嗯，bash是不是我会使用用于高速数值处理。让自己 GMP 的副本，并把一个C程序来做到这一点。

有可能是一个数学公式，它很快给你，但是，在它把你弄明白的时候，GMP很可能你扔结果： - ）

这被识别为序列 A061418 在里面 sequences 网站（又名“整数序列在线百科全书”）；每相关页面,

公式 a(n) =A061419(n)+1 = ceiling[K*(3/2)^n] 在哪里 K=1.08151366859...常数K是 2/3*K(3) （参见 A083286）。

并有一个合适的高精度库（GMP如已经建议的那样，或MPIR，也许像我的宝贝一样在上面有一个包装纸 gmpy 适用于 Python）您可以使用封闭式公式来更快地计算“系列中的第 100 万项”等。

通常可以将递归指定的递归放入封闭公式中。对于初学者对该主题的广泛介绍，具体数学（作者：Graham、Knuth 和 Patashnik）确实很难被击败。

可以可能得到一个更接近的位通过使用更合适的语言，例如，方案：

(define (series n) (if (= n 0) 2
                       (quotient (* 3 (series (- n 1))) 2)))

此计算(series 100000)的17610位在我的机器上约8秒钟。不幸的是，(series 1000000)仍然需要时间太长甚至一个非常新的/更快的机器有在一分钟内完成的希望。

切换到C ++有一个大整数库（NTL，在这种情况下）：

#include <NTL/zz.h>
#include <fstream>
#include <time.h>
#include <iostream>

int main(int argc, char **argv) {
    NTL::ZZ sum;

    clock_t start = clock();
    for (int i=0; i<1000000; i++) 
        sum = (sum*3)/2;
    clock_t finish = clock();
    std::cout << "computation took: " << double(finish-start)/CLOCKS_PER_SEC << " seconds.\n";

    std::ofstream out("series_out.txt");
    out << sum;

    return 0;
}

此计算系列百万在4分钟内35秒我的机器上。这足够快，我的几乎的相信真快，新的机器可能至少接近在一分钟内完成（是的，我检查时，我使用的变化，而不是乘法/除法发生了什么 - 它是慢）。

不幸的是，封闭形式计算其他人所说似乎帮助不大。要使用它，你需要计算常数K足够的精度。我没有看到K的封闭形式计算，所以这真的只是转移的迭代计算K，它看起来像计算K至足够的精度是很少（如果有的话）快，计算原始的系列。

这是很容易做到帕里：

n=2;for(k=1,10^6,n+=n>>1)

这需要我的机器上14秒。有更快的方式，当然 - GMP想到的 - 但何必呢？您将无法刮胡子超过10秒关运行，并缩短开发时间将是分钟的量级的。：）

次要点：这是在原制剂暧昧是否百万分之一项n <子> 999999 期望或正<子>百万，与索引数百万;我给后者，因为我看到前者已经在上面计算的。

这几乎是一个一阶递归关系，除了地板上，这混乱的事情了。如果你不想在地板上，

http://en.wikipedia.org/wiki/Recurrence_relation

另外，不要使用bash。

递归制剂将需要相当长的时间下最 curcumstances因为它必须保持机堆栈。为什么不使用动态编程代替？

即。（伪代码）

bignum x = 2
for (int i = 1; i < 1000000; i++) {
    x = floor(3.0/2*x)
}

当然，对于一个有意义的结果，你需要一个高精度的数字图书馆。

我转换蒂莫的想法elisp的。它失败，100，给负数。 FAIL，请参见没有大数！

(progn
  (let ((a 2)
        (dummy 0))
    (while (< dummy 100)
      (setq a (+ a (lsh a -1)))
      (setq dummy (1+ dummy)))
    (message "%d" a)))
-211190189 #WRONG evalution

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow