かの百万分の番号のシリーズ2 3 4 6 9 13 19 28 42 63 ...?

StackOverflow https://stackoverflow.com/questions/2840593

  •  27-09-2019
  •  | 
  •  

質問

約分を3000っcompでも知る必要があるのは百万分の番号のシリーズです。この定義は再帰的でなショートカットを除くすべてを計算前の百万分の番号です。どのようにすることができます高速の計算は百万分の番号です。

シリーズDef

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
役に立ちましたか？

解決

することを考えて、問題バイナリー.階（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

フル結果 こちらの.

他のヒント

ほとんど見つかります。次回、チェックアウトの オンライン百科事典の整数シリーズ.

こちらの登録"を選択してください 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's"応答となります。

編集： 利用ティモのビットシフトという

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

出力の切り出された:(フル出力にふ)

516380 (milliseconds)
196375676351034182442....29226123087

いたので、8.5分も控えめます。使用した -Xmx128M, ものだった本当に必要です。

があり、多くのアルゴリズムであり、こって10分を含む文書のナイーブの実施ならびにプログラム。

サンプル走

こちらはPythonのバージョンの私が10歳のpcには約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));

で同じ結果になる この答え が壊(これは、検証の開始と終了のではないです。)

んー、 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でき用のデフォルト式のためにもスピーディーな計算"、百万分の商品のシリーズ"等が挙げられる。

でき入れを再帰的に定再発に閉式に代入します。で、初心者の入門科目、 具体的な数学 （グラハム氏（KnuthとPatashnikあります。

できるのではないでしょうかを取得しビットに近い利用をより適切な言語、例えば、スキーム：

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

この計算に17610桁 (series 100000) 約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;
}

この計算は、シリーズ1000000 4分35秒私の機です。があることができま ほとんど えーん、新しい機械が少なくともどり、仕上げに自分の（ありがかかったとして使用シフトの代わりに乗除算部門でゆっくりした).

残念ながら、デフォルトその他計算が示唆されているそうなのです。利用で必要なものを計算するための定数Kを十分な精度。きというものはないと思い閉形計算のK、この私がシフトし、繰り返し計算K、という計算に十分な精度は(もしあれば)より速くることをコンピューティングするこ独自のシリーズです。

非常に簡単でい Pari:

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

この間14秒私の機です。がより速く、もちろん--GMPが気になる--そもそも、なぜわざわざ?することはできませんので削り10秒のランタイム時において、開発するの 分. :)

マイナポイント：この曖昧の策定か百万分の期間n999999 が望またはn1000000, のインデックス一万円、私は後者からの元で計算します。

これはほぼ初再発の関係を除き、階、ヘヴンリースキーリゾートもの。思いついたの階

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を負い。失敗しください、 な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
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top