問題97 - プロジェクトオイラー：私のコードで何が問題になっていますか？

Question

私はpythonを使ってプロジェクトEulerから問題97を解決しようとしています。

目標は、28433×2^7830457 + 1の最後の10桁を見つけることですが、私の解決策はオフになり、何が間違っているのかを特定することはできません。

私のループではオフ・バイ・ワンのエラーが考えられましたが、追加または削除すると間違った答えが得られ、とにかくこれは論理的に見えます。

誰かが私を助けることができますか？

おかげ

def PE97(): 
    mod = 10**10 
    base = 2 

    for i in range(7830456): 
     base = (base * base)%mod 

    print((28433*base+1)%mod) 

PE97() 

編集：これを無視し、私はそれはそうPOW（）関数を作成するに吸います。

Answer 1

このフラグメント：

for i in range(7830456): 
     base = (base * base)%mod 

が2^7830457を計算しません。 2の累乗した各ループベースの後、最初の実行後に、あなたがベース= 4を持っているので、その後、等をベース= 8

Answer 2

あなたの問題は、ベース起こる初めてとなり、ここで

base = 2 
for i in range(7830456): 
    base = (base * base)%mod 

です2^2、次に2^4、2^8 ... &cです。

2の累乗を計算するためにアルゴリズムを再考する必要があります。

Answer 3

わかりやすくするために、私は、pythonに組み込まれているpowがモジュラ指数を行うことを指摘します。そしてそれは速いです。

>>> pow(2, 5, 30) 
2 
>>> pow(2, 7830456, 6542) 
5778 
>>> timeit.timeit(stmt='pow(2, 5, 30)', number=100000) 
0.031174182891845703 
>>> timeit.timeit(stmt='pow(2, 7830456, 6542)', number=100000) 
0.11496400833129883 

あなたが編集したかどうか分からなかったので、私はそれを言いたいと思いました。