「史上最大の素数」約2年ぶりに更新、50番目のメルセンヌ素数で桁数は2324万9425桁 77
ストーリー by hylom
でかい 部門より
でかい 部門より
メルセンヌ素数を探索するプロジェクトである「Great Internet Mersenne Prime Search」（GIMPS）が、新たな「これまで知られているなかで最大の素数」を発見したと発表した（ハフィントンポスト、GIGAZINE）。新たな最大素数が発見されたのは2015年9月以来（発表は2016年1月）。
この素数が発見されたのは2017年12月26日で、2の77,232,917乗-1という数。これを単純に数字として表すと2324万9425桁になるという。この数をプレインテキストで表記したファイルも公開されているが、ZIP圧縮されたもので約11.2MBというサイズとなっている。
一方で (スコア:4, 参考になる)
最も大きな既知の
・フェルマー素数: 224 +1: 5桁
・一般化フェルマー素数: 919444220 +1: 625万3210桁
・カレン素数: 6679881×26679881+1: 201万852桁
・一般化カレン素数: 1341174×531341174+1: 231万2561桁
・階乗素数: 208003!−1: 101万5843桁
Re: (スコア:0)
フェルマー素数、それで5桁だと……
# ふふふ。基数が必ず10だとでも思ったか!
Re:一方で (スコア:1)
あ、たった2^16乗だった。消えてなくなりたい。
メルセンヌ素数はロマン (スコア:3)
今から３０数年前27個目のメルセンヌ素数が発見された。
発見したのは男女のペアの研究者。
そして、数年後28個目が発見された。同じ男女ペア。
しかし、同じファミリーネームになっていた。
圧縮率 (スコア:1)
情報量的には
M77,232,917
で表せちゃうものをZIPだと11.2MBも必要とするのか。
最悪に近い圧縮率ですね。
＃10進数の23,249,425桁の圧縮と考えればがんばってるのは承知の上で
Re:圧縮率 (スコア:1)
しかしながら、それは10進数での話。
2進数（バイナリ）ならばZIPで11,496バイト！
更に、bzip2ではわずか47バイト！！
（中身はほぼ0xFFなので(^^;)）
Re: (スコア:0)
むむ、これはメルセンヌ数だ!
パラメタM77,232,917と圧縮できるぞ!
はい、圧縮しました。
というスーパー圧縮エンジンがそのうち出来ますよ!
Re: (スコア:0)
そういう問題はチューリング完全じゃないかな？
Re: (スコア:0)
Re: (スコア:0)
もちろんアスキーコード表記でのテキストファイルだということは分かってますが、
素数なのに圧縮できるってことが不思議な感覚です。
Re:圧縮率 (スコア:2, 興味深い)
バイナリで考えると2の77,232,917乗-1ってことは77,232,917ビット。
つまり10MiB未満。
アスキーにして圧縮して11MBってのは割と納得できる感じじゃない?
Re: (スコア:0)
2進表記のテキストを圧縮するとすごく圧縮できますよね。
Re: (スコア:0)
数学詳しくないから素数の性質わかってないだけかも知れないけど、素数って絶対に圧縮不可なんだっけ？
辞書圧縮とかでも？
Re: (スコア:0)
素数は n までの自然数の中に確率 1/ln n で存在する「ありふれてない数」で低エントロピーだから圧縮率高いだろう。
Re: (スコア:0)
メルセンヌ数の５０番目という記述でいいので辞書圧縮だとヘッダ含めて数バイトで済むレベル。それにメリットがあるのかどうかは分かりません。
Re: (スコア:0)
まれに圧縮率が高くなるが、ほとんどの場合圧縮できず、圧縮するにも素数判定しなきゃならず時間がかかる、そんな圧縮アルゴリズムになります。そんなのでよければ。
Re: (スコア:0)
ZIPファイルは 10.6MiB で、これを展開すると 22.6MiB くらい。（1KiB = 1024Bytes として）
だから半分くらいには圧縮できたって感じ。
ZIPってハフマンコード＋ランレングス圧縮だったけ。
多分、ハフマンコードの時点で1文字あたり平均4bit未満に圧縮されただろうから（数字0～9しか使われてないし）
だとするとランレングスではほぼ圧縮できてない、って事でいいのかな。
乱数列として面白く使えたりするんだろうか。検定のやり方とかさっぱり知らんけど。
でも「あ、この数列はM77232917だな」とバレちゃうとアカンから、セキュアでは無い。。。
Re:圧縮率 (スコア:1)
ZIPはハフマン＋スライド辞書です。この場合は似たようなものですが。
ハフマンの方も「一文字あたり8ビットだけど実際には10種類しか使ってない」ことによるもので、出現頻度にはあまり偏りがないと思われるのでコード長は3ビットか4ビット。
別コメントにあるように「これは素数である」という前提を使える方法でないと、整数を単純にバイナリ表現したものより小さく圧縮することは難しそう。
うじゃうじゃ
Re:圧縮率 (スコア:1)
100桁毎に改行(CR+LF)が入ってますので、使用文字は12種類ですね。
全部で23,714,413Bytesで、CRとLFはそれぞれ232,494個
ハフマン符号化で数字5個に3bit、数字5個に4bit、CR+LF(辞書に100バイト前から2バイトマッチ)に5bit割り当てると、
全部で82.5Mbit=9.84MiByteぐらいですので、
ZIP圧縮におけるスライド辞書はほとんど役に立たず、シンボル数の少なさによるハフマン圧縮だけが効いてる感じですかね。
「スライド辞書が役に立たない」=「シンボル間の相関が見つからない」以上、これ以上はどうしようもなさそう。算術符号などのシンボルに対して小数ビットを割り当てることができる方法をつかえばもうちょい減らすことはできるでしょうけで、まー誤差レベルですかね。
Re:圧縮率 (スコア:1)
うーん、ハフマン符号も算術符号も基本的な考え方は「出現頻度によって符号長(算術符号の場合は区間の大きさ)を変えることにあって、使っている文字が少なければ短く表現できるのは結果論みたいなものですよね。
そのため出現頻度の偏りがほとんどない場合は事前に固定コードを割り振るのと同等にしかならないのにわざわざコード長を決めるための集計処理をするって無駄だなぁと思ってしまいます。
算術符号でも「ハフマンより多少はまし」なだけで、符号とは別に辞書データを持つ分サイズが増えるので非圧縮のバイナリ整数に勝てる見込みはまずないでしょう。
うじゃうじゃ
400字詰め原稿用紙に書き起こすと、5万8000枚近く必要になる。 (スコア:1)
と記事にはあるけども
http://www.huffingtonpost.jp/2018/01/05/gimps-m77232917_a_23324596/ [huffingtonpost.jp]
2324万9425桁の数字を400字詰め原稿用紙に1桁1マスで書き写して行ったとして、58000枚未満で収まる理屈が分からん。
https://www.google.co.jp/search?q=23249425%2F400 [google.co.jp]
Re: (スコア:0)
原稿用紙には余白というものがありまして・・・
# マジレスすると、5万8000枚「近く」を少ないほうにだけと考えるな、ということでは。
Re: (スコア:0)
5万8000枚「近く」を少ないほうにだけと考えるな、ということでは。
https://dictionary.goo.ne.jp/jn/141163/meaning/m0u/ [goo.ne.jp]
> ちかく【近く】の意味
> ２ 数詞の下に付いて、それには達しないが、ほぼそれに近いくらい、の意を表す。「三十近くの男」「五時近くに終わった」
Re: (スコア:0)
三省堂 大辞林
Re: (スコア:0)
なるほど、大辞林の解説は間違ってるというわけか。
Re: (スコア:0)
「近く」だと超えないようなときの使い方がほとんどのような気がするけど、
似たような「近辺」に言いかえると「前後」の意味になりますね。
＃たぶん「nearly」を訳す際にニュアンスを誤った？
でかくない (スコア:0)
円周率 [wikipedia.org]が
> 2016年の時点では、円周率は小数点以下22兆4591億5771万8361桁まで計算されている。
ので、2324万9425桁がそれほどでもなく感じてしまう。
Re:でかくない (スコア:1)
その比較意味あるのかな？
じゃあ日本の借金と比べてもよかですか？
Re:でかくない (スコア:2)
日本の借金なんて100桁も行かないから全く気にする必要が無いぜ!
とかいう話ですかね
確かに誤差範囲もいいところだな
教えて偉い人 (スコア:0)
この分野はさっぱりなんだが、最大桁の素数を見つけると
何かに活用できたり、宇宙の真理に近づいたりするの？純粋な疑問として知りたい
Re:教えて偉い人 (スコア:2, おもしろおかしい)
心を落ち着かせたいときにより長い時間数えられる
Re: (スコア:0)
そういえば、早漏男性が頭の中で九九を暗唱する、って話があったな。
今度から素数数え上げにしよう。
Re:教えて偉い人 (スコア:2)
Re: (スコア:0)
今のところ暗号分野で使われているんじゃないですか。
数学が発展すれば他の分野でも使えるようになるかも。
Re: (スコア:0)
量子コンピュータが実用化されたら
暗号で使われなくなるという話は
本当なのかしらん
同時に素数見つけ放題になる?
Re: (スコア:0)
使ってねーよ。暗号で使ってるのは、適当に生成した素数の確率が高い擬素数。
こういう場合、史上最大と表現するもの？ (スコア:0)
史上最大ってぇことは、有史以前にはもっと大きな素数が発見されていたかもしれん、という意味を含むのかな。
重箱の隅だけどメッチャ違和感があったので…
Re:こういう場合、史上最大と表現するもの？ (スコア:2)
史上を抜くと「最大の素数を発見」となって非常に具合が悪い
今まで記録されていたものというニュアンスで史上と表現するのはそう悪くないと思う
Re: (スコア:0)
ごめん。
「最大の素数を発見」のどこがどう非常に具合が悪いのかわからんです。
マジで。
Re:こういう場合、史上最大と表現するもの？ (スコア:1)
前者なのか、後者なのかはっきりしなくなってしまうので単に、最大の、とやるのは具合が悪いですね。
「人類史上最大の素数」と (スコア:4, おもしろおかしい)
「人類史上最大の素数」と書くのが良さげ。人類はここまで見つけたけど、
他の星の宇宙人ならさらに大きいのも発見しているかも、と言う、勝負の意味で。
時は西暦2050年。 宇宙人「やあ、地球の諸君、君たちの知っている最大の素数はいかほどかな？」
人類代表の数学者「2の77,232,917乗-1だが、 どう思う？」
宇宙人「なんと！ すごく・・・大きいです・・・」（撤退する宇宙人。地球人の勝利に終わる）
Re:「人類史上最大の素数」と (スコア:1)
最大の素数から始めるんですね。
Re:「人類史上最大の素数」と (スコア:1)
おおなるほど、人類がいまだ知らない大きさの素数列が送られてきたら、確かに地球外知性体の証明になるなー。
Re:こういう場合、史上最大と表現するもの？ (スコア:1)
数学的には最大の素数と呼べるのは「これ以上大きな素数は存在しない」と証明できたものです。
うじゃうじゃ
Re: (スコア:0)
より大きい素数が存在しないことになる。夢がなくなる。
みんなこうして大人になってゆく。
Re: (スコア:0)
最大の素数が存在しないことは証明されていますから。
Re: (スコア:0)
「史上」とは、過去のこと（有史以前には発見されていたかもしれん）ではなくて、未来（将来もっと大きな素数が発見されるかもしれん）を担保していると思う。
Re: (スコア:0)
記録上最大あたりが良いかね。
でも史上最大って言われてるものに結構当てはまりそうな気もするな。
気もするだけで確認はしないけど。
Re: (スコア:0)
厳密に言えば数学史上最大なんだろうけど、数学史≒有史と考えても差し支えない程度には
歴史のある学問だし史上最大でも問題ないとは思う。
素数を求める計算式ってあるの？ (スコア:0)
詳しい方ヨロピコ