Problem 97 - シェルピンスキー数

最近、素数ばっかりだな

100万桁を超える初めての素数は1999年に発見された. これはメルセンヌ素数であり, 2^6972593-1 である. 実際, 2,098,960桁ある. それ以降も, より多くの桁になるメルセンヌ素数 (2p-1の形の数) が他にも発見されている.
しかし, 2004年に, 非常に大きな非メルセンヌ素数が発見された. これは2,357,207桁の数であり, 28433×2^7830457+1である.
この素数の最後の10桁を答えよ.

簡単な問題だけど、調べてみると面白い。

シェルピンスキー数 - Wikipedia

へぇぇぇ。

解答はこんなん。

(modulo (+ (* 28433 (expt 2 7830457)) 1) (expt 10 10)) ; 8739992577

200万桁でもスイスイ計算できちゃうSchemeってスゲー。

解答を見ると、Cでやってる人がいた。写経写経。

#include <stdio.h>

int main(void)
{
    long long i,n = 1;

    for (i = 0; i < 7830457; i++)
        n = (n << 1) % 10000000000;

    printf("%lld\n", n * 28433 % 10000000000 + 1);

    return 0;
}

なるほどぉ。

色々やってみよう。

Pythonで。

>>> 2 ** 7830457
固

2 ** 10000でヤバめ。

Rubyで。

irb(main):001:0> 2 ** 7830457
(irb):1: warning: in a**b, b may be too big
=> Infinity

2 ** 0x40000以上は無理っぽい。

ま、200万桁がありえないわけで・・・。