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

发布于 2024-09-01 12:02:59 字数 889 浏览 10 评论 0原文

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

系列定义

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

有趣的是，只有一个网站根据 Google 列出了该系列：这个。

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

原文

It takes about minute to achieve 3000 in my comp but I need to know the millionth number in the series. The definition is recursive so I cannot see any shortcuts except to calculate everything before the millionth number. How can you fast calculate millionth number in the series?

Series Def

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

Interestingly, only one site list the series according to Google: this one.

Too slow Bash code

#!/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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

后eg是否自 2024-09-08 12:03:00

通过以二进制方式思考问题，您可以轻松解决这个问题。 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

完整结果此处。

You can easily solve this by thinking about the problem in binary. Floor(3/2*i) is basically shift right, truncate and add. In pseudo code:

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

This should be quite fast to implement in any form.

I just made an implementation of this in Mathematica and it seems that the BitShiftRight operation also chops off the bit past the unit position, so that gets taken care of automatically. Here is the one liner:

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

16 seconds, the number prints just fine, it is quite long though:

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

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

Full result here.

回复收藏 0 原文

薔薇婲 2024-09-08 12:03:00

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

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

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

再次编辑：找到解决方案！请参阅蒂莫或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

You almost found it. Next time, check out the Online Encyclopedia of Integer Series.

Here's the entry: 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

That said:

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

Sanity test:

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

Awesome! Now how about 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')

Well, I tried. :] But you get the idea.

Edit again: Solution is found! See Timo or Lasse V. Karlsen's answers.

Edit: Using Timo's bit-shifting idea:

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

yields

1963756763...226123087 (176092 digits)

% time test.py > test.out

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

回复收藏 0 原文

旧街凉风 2024-09-08 12:03:00

您的脚本如此缓慢的原因是它在循环中生成 bc 三次、tr 一次和 sed 一次。

在 bc 中重写整个内容，并在最后执行 sed 。我的测试表明仅 bc 版本的速度快了 600 多倍。在旧的缓慢系统上，bc 版本只花了不到 16 分钟就找到了第 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'

The reason your script is so slow is that it's spawning bc three times, tr once and sed once in a loop.

Rewrite the whole thing in bc and do the sed at the end. My test shows that the bc-only version is over 600 times faster. It took just under 16 minutes on an old slow system for the bc version to find the 100,000th value (only printing the last).

Also, note that your "floor" function is actually "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

Note that print is an extension and some versions of bc may not have it. If so just reference the variable by itself and its value should be output.

Now you can do chmod +x series.bc and call it like this:

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

回复收藏 0 原文

-黛色若梦 2024-09-08 12:03:00

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

I used the following Java program:

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);
    }
}

The output, cropped: (full output on pastebin)

516380 (milliseconds)
196375676351034182442....29226123087

So it took about 8.5 minutes on my modest machine. I used -Xmx128M, but not sure if that was really necessary.

There are probably better algorithms out there, but this took a total of 10 minutes, including writing the naive implementation and running the program.

Sample runs

N=500 (agrees with OEIS 061418)
N=100K (1445232038814....522773508)

回复收藏 0 原文

云醉月微眠 2024-09-08 12:03:00

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

Here's a Python version that on my 10-year old laptop takes about 220 seconds to run:

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

It produces the same result that this answer has on the pastebin (that is, I verified the start and end of it, not everything.)

回复收藏 0 原文

风为裳 2024-09-08 12:03:00

嗯，bash 不是我用于高速数值处理的工具。给自己一份 GMP 的副本，并编写一个 C 程序来完成它。

很可能有一个数学公式可以快速提供给您，但是，在您需要花时间弄清楚时，GMP 可能会向您提供结果:-)

回复收藏 0 原文

忆梦 2024-09-08 12:03:00

这在 sequences< 中被识别为序列 A061418 /code>站点（又名“整数序列在线百科全书”）；根据相关页面，

公式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和帕塔什尼克）真的很难被击败。

回复收藏 0 原文

橘虞初梦 2024-09-08 12:03:00

您可能可以通过使用更合适的语言来接近一点，例如，Scheme：

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

这在我的机器上大约 8 秒内计算出 (series 100000) 的 17610 位数字。不幸的是，(series 1000000) 仍然需要太长的时间，即使是更新/更快的机器也无法在一分钟内完成。

切换到带有大整数库（本例中为 NTL）的 C++：

#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 秒内计算出 1000000 的级数。这速度足够快，我几乎相信一台非常快的新机器至少可以在一分钟内完成（是的，我检查了当我使用移位而不是乘法/除法时发生了什么 -它比较慢）。

不幸的是，其他人建议的封闭式计算似乎没有什么帮助。要使用它，您需要以足够的精度计算常数 K。我没有看到 K 的封闭形式计算，所以这实际上只是将迭代转移到计算 K，并且看起来计算 K 到足够的精度比计算原始序列快一点（如果有的话）。

You can probably get a bit closer by using a more suitable language, e.g., Scheme:

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

This computes the 17610 digits of (series 100000) in about 8 seconds on my machine. Unfortunately, (series 1000000) still takes far too long for even a much newer/faster machine to have any hope of finishing in a minute.

Switching to C++ with a big-integer library (NTL, in this case):

#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;
}

This computes the series for 1000000 in 4 minutes, 35 seconds on my machine. That's fast enough that I can almost believe a really fast, new machine might at least come close to finishing in a minute (and yes, I checked what happened when I used shifts instead of multiplication/division -- it was slower).

Unfortunately, the closed-form computation others have suggested seems to be of little help. To use it you need to compute the constant K to sufficient precision. I don't see a closed-form computation of K, so this really just shifts the iteration to computing K, and it looks like computing K to sufficient precision is little (if any) faster that computing the original series.

回复收藏 0 原文

帅气称霸 2024-09-08 12:03:00

在 Pari 中这很容易做到：

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

在我的机器上这需要 14 秒。当然，还有更快的方法——我想到了 GMP——但为什么还要麻烦呢？您将无法将运行时间缩短超过 10 秒，并且开发时间将约为分钟。 :)

小点：在原始公式中，是需要第百万项 n₉₉₉₉₉₉ 还是 n_1000000（索引为 100 万的数字）是不明确的；我给出后者，因为我看到前者已经在上面计算过了。

It's very easy to do in Pari:

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

This takes 14 seconds on my machine. There are faster ways, of course -- GMP comes to mind -- but why bother? You won't be able to shave more than 10 seconds off the runtime, and development time would be on the order of minutes. :)

Minor point: It's ambiguous in the original formulation whether the millionth term n₉₉₉₉₉₉ is desired or n_1000000, the number with index one million; I give the latter since I see the former is already calculated above.

回复收藏 0 原文

生死何惧 2024-09-08 12:03:00

这几乎是一阶递归关系，除了地板，它把事情搞乱了。如果您不想发言，

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

另外，不要使用 bash。

回复收藏 0 原文

对你而言 2024-09-08 12:03:00

在大多数情况下，递归公式将花费相当长的时间
因为它必须维护机器堆栈。为什么不使用动态
而是编程？

即（伪代码）

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

当然，为了获得有意义的结果，您需要一个高精度数字库。

The recursive formulation is going to take quite a long time under most
curcumstances because it has to maintain the machine stack. Why not use dynamic
programming instead?

i.e. (pseudocode)

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

Of course, for a meaningful result you'll need a high precision number library.

回复收藏 0 原文

得不到的就毁灭 2024-09-08 12:03:00

我将 Timo 的想法转换为 elisp。失败时为 100，给出负数。失败，请参阅没有 BigNums！

(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

I converted Timo's ideas to elisp. It fails with 100, giving negative number. FAIL, please, see no BigNums!

(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

回复收藏 0 原文

~没有更多了~