2015年08月31日の日記です


夏の終わりの素数  2015-08-31 16:58:07  コンピュータ 家族

今年の春ごろ…長男が5年生に進級したころだったと思うが、こんな質問をされた。


1~100までのすべての自然数で綺麗に割り切れる数って、どんな数だろう?



一応彼なりに答えは持っているのだけど、その答えが大きすぎて算出できない、という。


長男の考え方はこうだ。


まず、100 までの素数を探し出す。

100以下の数は、これらの素数を適切な回数掛け合わせることで作り出せるはずだ。


だけど、これらの素数を全て掛け合わせても、問題の答えにはならない。

素数をかけるだけでは、素数である「2」で割れることは保証されても、4で割れることを保証できない。


2を適切な回数掛け合わせることで、この保証を作り出さないといけない。


この「適切な回数」は、掛け合わせた数が 100を超えない最大の値になるようにする。

2であれば、6回掛け合わせて 64 にする。64 で割れる数字は、32、16、8、4、2でも割れることが保障される。


同じように、3ならば4回掛け合わせて 81とする。

全ての素数に対し、この操作を行う。


そして、最後にこれら掛け合わせて出来た数を、すべて掛け合わせる。

その答えが冒頭の質問の答えとなる。



説明を受けて、なるほど、と思った。考え方はあっている。つまり、それが答えだ。

でも、その数を実際に算出できない。



長男の疑問には条件に入っていなかったが、この数は、条件を満たすうちの「最小の数」でもある。


(素数を使った考え方は、最小公倍数の求め方と同じだ。

 つまり、この数は1~100の最小公倍数である)




この時点で、長男はためしに 10 までの数値で試算を行っていた。

1~10 の自然数で割り切れる数は、2520 だった。


その疑問は、大きすぎて解決できない数としてそのままになっていた。



夏休みも終わりに近づき、長男は宿題を全部終わらせ、急に「Scratch って、どのくらい大きな数を扱えるの?」と聞いてきた。


なかなか難しい質問だ。

宇宙物理学などで大きな数を使う時には浮動小数点を使う、という話は長男は知っているので、コンピューターも浮動小数点を使えることを教える。


その上で、Scratch 内部では 64bit 倍精度演算を行っていて、正確に出せるのは 52bit 分だけど、大きな数の表現としては、さらに 11bit 分の指数が付けられることを教えた。


ややこしい話に最初は混乱していたけど、次に「指数を使うと、大きな数は表現できるけど、その場合は細かな数は出ない?」と聞かれる。


うん、その認識で正しい。正確な数を求めたければ、52bit の範囲に収めないといけない。


じゃぁ、52bit ってどのくらい? と聞かれたのだけど、即答できない。

32bit で40 億、さらに 20bit 余るけど、10bit で 1024 だから、40億の千倍の千倍くらい、と答える。



ここで、「じゃぁ、1~100までの全ての数で割り切れる数、計算できるかな」と言われる。

先に書いたように、冒頭の話は春のこと。僕はすっかり忘れていたけど、長男はまだ疑問に思っていた。


面白い、やってごらん、とノートパソコンの使用許可を出す。


#長男が Scratch をやりたいときは、僕か妻に許可をもらってノートパソコンを借りている。




1~100までの素数は知っているのだけど、うまくいったらもっと大きな数も計算してみたいので、と、エラストテネスの篩から作りはじめる。


素数を求めるアルゴリズムね。プログラムの初心者向けの課題として良く出されます。


普通は配列で作るのだけど、Scratch には配列が無い。でも、リストがある。

最初にリストに 2~100の数字を入れて、「倍数」はリストから削除していく、というプログラムにした。


リストの先頭を取り出すと、それは常に素数。

素数を取りだしたら、リストの数値を順次確認し、取り出した素数で割った余りが 0 なら、削除する。


最後に、取り出した素数は、素数を入れるもう一つのリストに追加される。



元となるリストがどんどん削除されていくので、終わりに向かって加速していくプログラムが出来上がった。

見ていてなかなか楽しい。



これで素数が得られたら、次にそれらの素数を掛け合わせ、100を超えない最大の数にした数値を、また別のリストに入れていく。


最後に、リストに入った数値を全て掛け合わせれば答えが出る。


結果は… 6.9720375229..e+40 !


…残念! Scratch では正確に求められないほど大きな数値だった。


#最後が e+40 となっているのは、52bit の範囲を超えてしまい、指数表現になったことを意味する。




プログラムを作って、答えは出たけど、正確な数じゃなかったーーー と、残念がりながらも面白がる長男。

せっかくなので、ここは父の威厳の見せどころ。


自分のマシンに向かって、UBASIC を起動する。

というか、以前にちょっと使ってみようとしたけど、使い物にならなくてほったらかしてあったのね。


UBASIC は、DOS 時代のフリー BASIC 。

実効桁数なんと 8640bit (540word) という恐ろしい演算性能を持つ。


DOS では動いたけど、残念ながら今の Windows では動かない。

でも、フリーの DOS エミュレータである DOSBox 上では動く。


…のだけど、DOSBox は英語版 DOS だし、キーボードも US 101 キーボードが前提。

これが「使い物にならない」としていた理由。


とりあえず、数値演算だけだから日本語は使えなくてもいい。

エラーメッセージが文字化けして読めないけど気にしない。

長男の考え方を、どんどんプログラムしていく。


…のだけど、流石に US 101 キーボード用は使いづらい。

いちいち記号を探すことになって効率が悪い。


ちょっと調べると、改造品で 106 キーボード対応があったので、DOSBox を入れ替える。

後で書くけど、その後さらに環境整えたら日本語も出るようになった

(この時は、BASIC プログラムを作ることが優先で、そこまでやってない)


久しぶりの UBASIC で無駄に手間取った部分もあるのだけど、2時間ほどで完成。


  100   Max=100
  110   dim F%(Max)
  120   for I=2 to Max
  130   if F%(I)=1 then 160
  140   F%(P)=I:P=P+1
  150   for J=I to Max step I:F%(J)=1:next
  160   next
  170   B=1
  180   for I=0 to P-1:A=F%(I)
  190   if A<Max/F%(I) then A=A*F%(I):goto 190
  200   B=B*A
  210   next
  220   print B

BASIC ではリストは使えないので、素数を求める部分は普通の配列。

1だと「既にチェックされた」、つまり倍数であることを意味している。


# F% というのは、UBASIC 独特の書き方。1word 数値であることを示す。

 0 か 1 かを保存するだけなので十分。

 こうしないと、540word の変数を配列にしようとして、すぐにメモリ不足となる。



120~160 で素数を求める。

130 で倍数か素数か調べ、素数なら 140 で記録、150 で倍数をチェックしている。


170 からは素数が求まった後で、190 で「100を超えない最大の倍数」にして、200 行でそれを掛け合わせている。



長男が求めていた答えは 69720375229712477164533808935312303556800 だった。




後日追記 2015.9.7


こういう計算なら、UBASIC より Ruby がいいと思うよ、という重要な示唆をいただきました。

恥ずかしながら、Ruby に多倍長型があるのを知りませんでした。


Ruby で書き直してみたプログラムを含め、ここら辺の話、別の日記に書いています




同じテーマの日記(最近の一覧)

コンピュータ

家族

関連ページ

プログラム教育に対する誤解【日記 16/03/19】

用語選びの難しさ【日記 15/09/03】

ruby で数値演算【日記 15/09/07】

別年同日の日記

10年 1回忌

16年 「人工知能」の生まれた日(1955)

17年 夏風邪


名前 内容


戻る
トップページへ

-- share --

9000

-- follow --




- Reverse Link -