パスワードを忘れた? アカウント作成
13497890 story
数学

「史上最大の素数」約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, 参考になる)

    by Anonymous Coward on 2018年01月09日 12時09分 (#3341490)

    最も大きな既知の
    ・フェルマー素数: 224 +1: 5桁
    ・一般化フェルマー素数: 919444220 +1: 625万3210桁
    ・カレン素数: 6679881×26679881+1: 201万852桁
    ・一般化カレン素数: 1341174×531341174+1: 231万2561桁
    ・階乗素数: 208003!−1: 101万5843桁

    • by Anonymous Coward

      フェルマー素数、それで5桁だと……

      # ふふふ。基数が必ず10だとでも思ったか!

  • 今から30数年前27個目のメルセンヌ素数が発見された。
    発見したのは男女のペアの研究者。
    そして、数年後28個目が発見された。同じ男女ペア。
    しかし、同じファミリーネームになっていた。

  • by shinshimashima (9763) on 2018年01月09日 11時51分 (#3341482) 日記

    情報量的には
    M77,232,917
    で表せちゃうものをZIPだと11.2MBも必要とするのか。
    最悪に近い圧縮率ですね。

    #10進数の23,249,425桁の圧縮と考えればがんばってるのは承知の上で

    • by T.Sawamoto (4142) on 2018年01月09日 16時14分 (#3341641) ホームページ

      しかしながら、それは10進数での話。
      2進数(バイナリ)ならばZIPで11,496バイト!
      更に、bzip2ではわずか47バイト!!
      (中身はほぼ0xFFなので(^^;))

      --
      へ へ
      の の
      親コメント
    • by Anonymous Coward

      むむ、これはメルセンヌ数だ!
      パラメタM77,232,917と圧縮できるぞ!
      はい、圧縮しました。
      というスーパー圧縮エンジンがそのうち出来ますよ!

      • by Anonymous Coward

        そういう問題はチューリング完全じゃないかな?

      • by Anonymous Coward
        つ THcomp
    • by Anonymous Coward

      もちろんアスキーコード表記でのテキストファイルだということは分かってますが、
      素数なのに圧縮できるってことが不思議な感覚です。

      • Re:圧縮率 (スコア:2, 興味深い)

        by Anonymous Coward on 2018年01月09日 12時20分 (#3341498)

        バイナリで考えると2の77,232,917乗-1ってことは77,232,917ビット。
        つまり10MiB未満。
        アスキーにして圧縮して11MBってのは割と納得できる感じじゃない?

        親コメント
        • by Anonymous Coward

          2進表記のテキストを圧縮するとすごく圧縮できますよね。

      • by Anonymous Coward

        数学詳しくないから素数の性質わかってないだけかも知れないけど、素数って絶対に圧縮不可なんだっけ?
        辞書圧縮とかでも?

        • by Anonymous Coward

          素数は n までの自然数の中に確率 1/ln n で存在する「ありふれてない数」で低エントロピーだから圧縮率高いだろう。

        • by Anonymous Coward

          メルセンヌ数の50番目という記述でいいので辞書圧縮だとヘッダ含めて数バイトで済むレベル。それにメリットがあるのかどうかは分かりません。

          • by Anonymous Coward

            まれに圧縮率が高くなるが、ほとんどの場合圧縮できず、圧縮するにも素数判定しなきゃならず時間がかかる、そんな圧縮アルゴリズムになります。そんなのでよければ。

    • by Anonymous Coward

      ZIPファイルは 10.6MiB で、これを展開すると 22.6MiB くらい。(1KiB = 1024Bytes として)
      だから半分くらいには圧縮できたって感じ。

      ZIPってハフマンコード+ランレングス圧縮だったけ。
      多分、ハフマンコードの時点で1文字あたり平均4bit未満に圧縮されただろうから(数字0~9しか使われてないし)
      だとするとランレングスではほぼ圧縮できてない、って事でいいのかな。

      乱数列として面白く使えたりするんだろうか。検定のやり方とかさっぱり知らんけど。
      でも「あ、この数列はM77232917だな」とバレちゃうとアカンから、セキュアでは無い。。。

      • by albireo (7374) on 2018年01月09日 13時37分 (#3341544) ホームページ 日記

        ZIPはハフマン+スライド辞書です。この場合は似たようなものですが。
        ハフマンの方も「一文字あたり8ビットだけど実際には10種類しか使ってない」ことによるもので、出現頻度にはあまり偏りがないと思われるのでコード長は3ビットか4ビット。

        別コメントにあるように「これは素数である」という前提を使える方法でないと、整数を単純にバイナリ表現したものより小さく圧縮することは難しそう。

        --
        うじゃうじゃ
        親コメント
        • by taka2 (14791) on 2018年01月09日 17時52分 (#3341686) ホームページ 日記

          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圧縮におけるスライド辞書はほとんど役に立たず、シンボル数の少なさによるハフマン圧縮だけが効いてる感じですかね。

          「スライド辞書が役に立たない」=「シンボル間の相関が見つからない」以上、これ以上はどうしようもなさそう。算術符号などのシンボルに対して小数ビットを割り当てることができる方法をつかえばもうちょい減らすことはできるでしょうけで、まー誤差レベルですかね。

          親コメント
          • by albireo (7374) on 2018年01月09日 23時13分 (#3341800) ホームページ 日記

            うーん、ハフマン符号も算術符号も基本的な考え方は「出現頻度によって符号長(算術符号の場合は区間の大きさ)を変えることにあって、使っている文字が少なければ短く表現できるのは結果論みたいなものですよね。
            そのため出現頻度の偏りがほとんどない場合は事前に固定コードを割り振るのと同等にしかならないのにわざわざコード長を決めるための集計処理をするって無駄だなぁと思ってしまいます。

            算術符号でも「ハフマンより多少はまし」なだけで、符号とは別に辞書データを持つ分サイズが増えるので非圧縮のバイナリ整数に勝てる見込みはまずないでしょう。

            --
            うじゃうじゃ
            親コメント
  • と記事にはあるけども
    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]

    • by Anonymous Coward

      原稿用紙には余白というものがありまして・・・

      # マジレスすると、5万8000枚「近く」を少ないほうにだけと考えるな、ということでは。

      • by Anonymous Coward

        5万8000枚「近く」を少ないほうにだけと考えるな、ということでは。

        https://dictionary.goo.ne.jp/jn/141163/meaning/m0u/ [goo.ne.jp]
        > ちかく【近く】の意味
        > 2 数詞の下に付いて、それには達しないが、ほぼそれに近いくらい、の意を表す。「三十近くの男」「五時近くに終わった」

        • by Anonymous Coward

          ②数詞の下に付いて、ほぼその程度・分量という意を表す。 「百キロ-の道のり」

          三省堂 大辞林

          • by Anonymous Coward

            なるほど、大辞林の解説は間違ってるというわけか。

            • by Anonymous Coward

              「近く」だと超えないようなときの使い方がほとんどのような気がするけど、
              似たような「近辺」に言いかえると「前後」の意味になりますね。

              #たぶん「nearly」を訳す際にニュアンスを誤った?

  • by Anonymous Coward on 2018年01月09日 11時44分 (#3341479)

    円周率 [wikipedia.org]が

    > 2016年の時点では、円周率は小数点以下22兆4591億5771万8361桁まで計算されている。

    ので、2324万9425桁がそれほどでもなく感じてしまう。

  • by Anonymous Coward on 2018年01月09日 12時20分 (#3341499)

    この分野はさっぱりなんだが、最大桁の素数を見つけると
    何かに活用できたり、宇宙の真理に近づいたりするの?純粋な疑問として知りたい

    • Re:教えて偉い人 (スコア:2, おもしろおかしい)

      by Anonymous Coward on 2018年01月09日 12時50分 (#3341515)

      心を落ち着かせたいときにより長い時間数えられる

      親コメント
      • by Anonymous Coward

        そういえば、早漏男性が頭の中で九九を暗唱する、って話があったな。
        今度から素数数え上げにしよう。

    • by FutureIsWhatWeAre (32387) on 2018年01月09日 15時58分 (#3341628)
      車田正美のバトルアクション漫画「B't-X」では知力勝負の際に最大の素数を問う問題が出ている。勝つためには知っておかないといけない
      親コメント
    • by Anonymous Coward

      今のところ暗号分野で使われているんじゃないですか。
      数学が発展すれば他の分野でも使えるようになるかも。

      • by Anonymous Coward

        量子コンピュータが実用化されたら
        暗号で使われなくなるという話は
        本当なのかしらん

        同時に素数見つけ放題になる?

      • by Anonymous Coward

        使ってねーよ。暗号で使ってるのは、適当に生成した素数の確率が高い擬素数。

  • by Anonymous Coward on 2018年01月09日 12時29分 (#3341506)

    史上最大ってぇことは、有史以前にはもっと大きな素数が発見されていたかもしれん、という意味を含むのかな。

    重箱の隅だけどメッチャ違和感があったので…

    • 史上を抜くと「最大の素数を発見」となって非常に具合が悪い
      今まで記録されていたものというニュアンスで史上と表現するのはそう悪くないと思う

      親コメント
    • by Anonymous Coward

      「史上」とは、過去のこと(有史以前には発見されていたかもしれん)ではなくて、未来(将来もっと大きな素数が発見されるかもしれん)を担保していると思う。

    • by Anonymous Coward

      記録上最大あたりが良いかね。
      でも史上最大って言われてるものに結構当てはまりそうな気もするな。
      気もするだけで確認はしないけど。

      • by Anonymous Coward

        厳密に言えば数学史上最大なんだろうけど、数学史≒有史と考えても差し支えない程度には
        歴史のある学問だし史上最大でも問題ないとは思う。

  • by Anonymous Coward on 2018年01月09日 16時40分 (#3341660)

    詳しい方ヨロピコ

typodupeerror

ナニゲにアレゲなのは、ナニゲなアレゲ -- アレゲ研究家

読み込み中...