math - 新しいメルセンヌ素数を整数で表すには何バイト必要ですか？

Question

2^57,885,161 - 1整数として何バイトを保存する必要がありますか？

Answer 1

2の補数を実行していて、8ビットが1バイトに等しいと仮定します。少なくとも（57,885,161 + 7）/8バイトが必要です。

おそらくそれを説明する簡単な方法が必要な場合は、2 ^ 32-1が32ビット整数が表す最大数であり、32が8で割り切れる2の底であるという数学的帰納法を使用することです。バイトあたりのビット数。2^32-1は4バイトになります。

この仮定の定義を拡張すると、8で割り切れない数2 ^ 57885161が得られますが、それに7を加えると割り切れます。したがって、2 ^ 57885168が残り、8で割ると、結果の7235646バイトが得られます。

これはGregSのコメントの説明にすぎません。

Answer 2

答えは、それをどうするかによって大きく異なります。メルセンヌ素数のみで動作するプログラムを作成している場合、それがメルセンヌ素数を表すことを理解すれば、それを格納するのにおそらく4バイトしか必要ありません。

通常の非圧縮の「大きな整数」として保存する場合は、約7235646バイト（ceildiv（57885161、8））かかります。一部の形式は他の形式よりも効率的です。たとえば、Pythonlongフォーマットは7718048バイトを使用して(2**57885161 - 1).__sizeof__()、フォーマットのオーバーヘッドのためにこの数値をマシン（）に格納します（Pythonは30ビットの数字を使用するため）。