アカウント名:
パスワード:
どうすればいい？なるべく簡単な方法で、Linuxでしたいです。てか、いろんな言語で書いてってください。
とか。
%% 計算は始めるけど、出力できるかどうかは知らん
COREi7 で、ファイルにリダイレクトして、50分ほどかかりました
この間のストーリー [srad.jp]でいまいち実用性が疑われていた Haskell だけど (いや俺がデバッグ難しいとかいったんだけど ),Haskell さんだってやればできるところをみせてやろう。Haskell Platform というのをインストールして、
> ghci > prime.txtPrelude> 2^57885161-1
GHCi は何も指定しないと勝手に多倍長で計算してくれる。待つこと３～４分で 17MB のテキストファイルができる。インタプリタでもなんとかなるもんだ。リダイレクトしないと、先頭の桁からどばーっとコンソールに表示されてちょっと楽しい。GIMP の発表の数字と末尾20文字くらいが一致したから、ちゃんと計算できてると思う。デバッグしなくていいなら、やはり Haskell は最強だ。
main = writeFile "prime.txt" $ show $ 2^57885161-1
って書いて ghc --make prime.hs みたいにコンパイルすると、自分の環境で 20秒くらいで終わった。やっぱりコンパイルしたほうが断然早かった
Pythonだと計算は一瞬ですね。元々、Pythonは多倍長整数をサポートしているので。
n = 2**57885161-1
ただ、これを10進数に変換するのは非常に時間がかかるみたいです。数分待っても出力できず(^^;)
print(n)
# 下から10桁切り出すと 1724285951 になります。
2時間待ってもprintされず・・・＞下から10桁切り出すと 1724285951 になります。ってどうやってるんですか？
除算／剰余算は結構早く終わります。なので、
print(n % 10**10)
とすれば下から10桁の切り出しはすぐ求められますね。
# 10000桁分ぐらいだったらあまり時間はかからないので、divmod等で少しずつ10進数化していくほうがトータルでは早いのかも(^^;)
#!/usr/local/bin/python#coding:utf-8#2013-02-07
n = 2**57885161-1print 'n==',n
time ./ruijyou1.pyn== 5818872・・・4285951real 195m43.290s2.6GHz Quad-core Intel Xeon
やっぱり python は最高だぜ！
Cじゃなくシェルでやれよecho 2^57885161-1って
計算?57,585,161 = (14,396,290 * 4) + 1なんだから、0xFFFFFF....FFF1 (Fは14,396,290個) と書くだけでは。
0x1FFFFFF....FFF (Fは14,396,290個)だな
設問が10進数なので出力も10進数にしてください。0x1FFFFFF....FFF は単にソースコードを最適化しただけだと思います。
# 数学の大問が全然わからなくて「つまり○○である」と言い換えて部分点だけゲット、みたいな。
あれ？これじゃうまく動かない？
> $ ruby -e ' print (2**57885161)-1; '> -e:1: warning: in a**b, b may be too big> Infinity
簡単そうに見えて、意外と難しいだろ。
php の場合
> $ echo ' INF
一言「無限」
訂正
> print pow(2,57885161)-1;
結果> INF
ちょっとおもしろかった
もうちょっと条件を具体的に。・ubuntuやCentOS等で、新たなライブラリをインストールしない。 ただし、C、C++以外のスクリプト系で、止む得ない場合はOK。・2日以内に計算が終わる。（スクリプト系はこの制限守れなくても仕方ないか）・マルチスレッド化はOK。/* レス中のecho系は飽きた */
んなもん、プログラム書く必要もないだろ宇宙の答えも出せるGoogleさんにまかせれば．．．ほら
だめじゃん
http://www.wolframalpha.com/input/?i=2%5E57885161-1 [wolframalpha.com]Decimal approximationのMore digitsを気のすむまでクリックしてください。
完全なソリューションではないのですが,「先に解析的に解いてテーブルを作り, 後でそれをひく」というアプローチです。
2^n の1の位の数字は 2, 4, 8, 6, 2... と4乗周期で循環します。証明は2^(n+4) - 2^n ≡ 0 mod 1016 * 2^n - 2^n ≡ 0 mod 1015 * 2^n ≡ 0 mod 1015 * 2 * 2^(n-1) ≡ 0 mod 1030 * 2^(n-1) ≡ 0 mod 10です。57885161 ≡ 1 mod 4 なので 2^57885161 の1の位は2です。ですから 2^57885161 - 1の1の位の数字は1と言えます。
つまり, 1の位だけならばld[0] ='5'ld[1] ='1'ld[2] ='3'ld[3] ='7'としておいてld[power % 4]で求まります。
ここにぶらさがっているコメントだけ読んでいると、素数かどうかの検証なんかすぐに終わるんじゃね？って錯覚してしまうな。
>てか、いろんな言語で書いてってください。OK. I will write in English.
数論好きは PARI/GP を bc の替わりに使ってる人も多いんじゃないかな。$time gp --quiet --stacksize 100000000 mersenne_48th_prime_number.txtreal 0m4.877suser 0m4.751ssys 0m0.113s
$ du -h mersenne_48th_prime_number.txt 17M mersenne_48th_prime_number.txt
Wolfram Alphaだと数秒ですね。
http://www.wolframalpha.com/input/?i=2%5E57885161-1 [wolframalpha.com]
釈迦に説法でしょうが（ライブラリには組み込まれているでしょうが）、例えば2^4 = (2 * 2)^2 = 4^2のように分解すれば単純に57885161回かけ算をする必要もないのでそれなりに速いはず。
お前らみんなプロジェクト・オイラー [projecteuler.net]好きそうだな（笑）。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
「科学者は100%安全だと保証できないものは動かしてはならない」、科学者「えっ」、プログラマ「えっ」
C言語で2^57885161-1を計算するには (スコア:0)
どうすればいい？
なるべく簡単な方法で、Linuxでしたいです。
てか、いろんな言語で書いてってください。
Re:C言語で2^57885161-1を計算するには (スコア:1)
2^57885161-1
とか。
%% 計算は始めるけど、出力できるかどうかは知らん
の
Re:C言語で2^57885161-1を計算するには (スコア:1)
COREi7 で、ファイルにリダイレクトして、50分ほどかかりました
Re:C言語で2^57885161-1を計算するには (スコア:1)
この間のストーリー [srad.jp]でいまいち実用性が疑われていた Haskell だけど (いや俺がデバッグ難しいとかいったんだけど ),
Haskell さんだってやればできるところをみせてやろう。Haskell Platform というのをインストールして、
> ghci > prime.txt
Prelude> 2^57885161-1
GHCi は何も指定しないと勝手に多倍長で計算してくれる。
待つこと３～４分で 17MB のテキストファイルができる。インタプリタでもなんとかなるもんだ。
リダイレクトしないと、先頭の桁からどばーっとコンソールに表示されてちょっと楽しい。
GIMP の発表の数字と末尾20文字くらいが一致したから、ちゃんと計算できてると思う。
デバッグしなくていいなら、やはり Haskell は最強だ。
Re:C言語で2^57885161-1を計算するには (スコア:1)
main = writeFile "prime.txt" $ show $ 2^57885161-1
って書いて ghc --make prime.hs みたいにコンパイルすると、自分の環境で 20秒くらいで終わった。
やっぱりコンパイルしたほうが断然早かった
Re:C言語で2^57885161-1を計算するには (スコア:1)
Pythonだと計算は一瞬ですね。
元々、Pythonは多倍長整数をサポートしているので。
n = 2**57885161-1
ただ、これを10進数に変換するのは非常に時間がかかるみたいです。
数分待っても出力できず(^^;)
print(n)
# 下から10桁切り出すと 1724285951 になります。
Re: (スコア:0)
2時間待ってもprintされず・・・
＞下から10桁切り出すと 1724285951 になります。
ってどうやってるんですか？
Re:C言語で2^57885161-1を計算するには (スコア:1)
除算／剰余算は結構早く終わります。なので、
print(n % 10**10)
とすれば下から10桁の切り出しはすぐ求められますね。
# 10000桁分ぐらいだったらあまり時間はかからないので、divmod等で少しずつ10進数化していくほうがトータルでは早いのかも(^^;)
Re: (スコア:0)
#!/usr/local/bin/python
#coding:utf-8
#2013-02-07
n = 2**57885161-1
print 'n==',n
time ./ruijyou1.py
n== 5818872・・・4285951
real 195m43.290s
2.6GHz Quad-core Intel Xeon
Re: (スコア:0)
やっぱり python は最高だぜ！
Re: (スコア:0)
Cじゃなくシェルでやれよ
echo 2^57885161-1
って
Re: (スコア:0)
計算?
57,585,161 = (14,396,290 * 4) + 1
なんだから、0xFFFFFF....FFF1 (Fは14,396,290個) と書くだけでは。
Re: (スコア:0)
0x1FFFFFF....FFF (Fは14,396,290個)
だな
Re: (スコア:0)
設問が10進数なので出力も10進数にしてください。
0x1FFFFFF....FFF は単にソースコードを最適化しただけだと思います。
# 数学の大問が全然わからなくて「つまり○○である」と言い換えて部分点だけゲット、みたいな。
Re: (スコア:0)
あれ？これじゃうまく動かない？
> $ ruby -e ' print (2**57885161)-1; '
> -e:1: warning: in a**b, b may be too big
> Infinity
Re: (スコア:0)
簡単そうに見えて、意外と難しいだろ。
Re: (スコア:0)
php の場合
> $ echo ' INF
一言「無限」
Re: (スコア:0)
訂正
> print pow(2,57885161)-1;
結果
> INF
Re: (スコア:0)
ちょっとおもしろかった
Re: (スコア:0)
もうちょっと条件を具体的に。
・ubuntuやCentOS等で、新たなライブラリをインストールしない。
ただし、C、C++以外のスクリプト系で、止む得ない場合はOK。
・2日以内に計算が終わる。（スクリプト系はこの制限守れなくても仕方ないか）
・マルチスレッド化はOK。
/* レス中のecho系は飽きた */
Re: (スコア:0)
んなもん、プログラム書く必要もないだろ
宇宙の答えも出せるGoogleさんにまかせれば．．．ほら
だめじゃん
Re: (スコア:0)
http://www.wolframalpha.com/input/?i=2%5E57885161-1 [wolframalpha.com]
Decimal approximationのMore digitsを気のすむまでクリックしてください。
Re: (スコア:0)
完全なソリューションではないのですが,「先に解析的に解いてテーブルを作り, 後でそれをひく」というアプローチです。
2^n の1の位の数字は 2, 4, 8, 6, 2... と4乗周期で循環します。
証明は
2^(n+4) - 2^n ≡ 0 mod 10
16 * 2^n - 2^n ≡ 0 mod 10
15 * 2^n ≡ 0 mod 10
15 * 2 * 2^(n-1) ≡ 0 mod 10
30 * 2^(n-1) ≡ 0 mod 10
です。
57885161 ≡ 1 mod 4 なので 2^57885161 の1の位は2です。
ですから 2^57885161 - 1の1の位の数字は1と言えます。
つまり, 1の位だけならば
ld[0] ='5'
ld[1] ='1'
ld[2] ='3'
ld[3] ='7'
としておいて
ld[power % 4]
で求まります。
Re: (スコア:0)
ここにぶらさがっているコメントだけ読んでいると、素数かどうかの検証なんかすぐに終わるんじゃね？って錯覚してしまうな。
Re: (スコア:0)
>てか、いろんな言語で書いてってください。
OK. I will write in English.
Re: (スコア:0)
数論好きは PARI/GP を bc の替わりに使ってる人も多いんじゃないかな。
$time gp --quiet --stacksize 100000000 mersenne_48th_prime_number.txt
real 0m4.877s
user 0m4.751s
sys 0m0.113s
$ du -h mersenne_48th_prime_number.txt
17M mersenne_48th_prime_number.txt
Re: (スコア:0)
Wolfram Alphaだと数秒ですね。
http://www.wolframalpha.com/input/?i=2%5E57885161-1 [wolframalpha.com]
釈迦に説法でしょうが（ライブラリには組み込まれているでしょうが）、例えば2^4 = (2 * 2)^2 = 4^2のように分解すれば単純に57885161回かけ算をする必要もないのでそれなりに速いはず。
Re: (スコア:0)
お前らみんなプロジェクト・オイラー [projecteuler.net]好きそうだな（笑）。