2007/03/28

3の4798乗

問題: 数 3の4798乗の末尾の3つの数字はなんだろうか? (「問題解決への数学」丸善より)

多分、何回か3をかければ下3桁が同じ値を繰り返すようになるんだろうなと思い計算してみました。
ちなみに末尾の一桁は3,9,7,1と4回かけるごとに循環します。
3桁では簡単に見つかりそうにないのでRubyスクリプトで計算させてみたところ、3の100乗でようやく"003"に戻ることが確認できました。
さすがに100乗は手計算では面倒極まりないので、きっともっと良い抜け道があるんだろうなと思うのですが、まだ発見できていません。

ちなみに末尾の2桁は20乗するごとに循環します。
4乗-20乗-100乗 ... とくると、もしかしたら累乗の値が5倍になる毎ってことでしょうか?。
500乗すれば末尾4桁が"0003"に戻り、2500乗すれば末尾5桁が"00003"になるのでしょうか?
そうだとしても理屈が理解できません。なぜ?

その問題はおいておいて、本来の問題の答え合わせがしたいのに、書籍に回答が載っていませんでした。
しょうがないのでRubyに真っ向勝負で3の4798乗をさせてみました。

x = 1
i = 1
for i in 0..4798 1..4798
  x *= 3
  p x
  i += 1
end

答えをはじき出してしまいました。
特別なライブラリを利用することも、かけ算ルーチンを自前で作ることも無しに。

506875616363543879916032533641797669560990746583999999302921895306376266400633026773508112521573067
636403865588246156868982582588885536960623987482026959689937962026776594925792728327028309953065497
593046053431462142459107974111674607241764096136090859185714592403930621843431671255952254699445089
558419084750250781442810452815934357662353499473170532469636502997187212606567403085131567751390247
508524769125524319562819277262010784336075256452049011104423722150229479912843314965494100612467906
175626919776737525139557256491154635217178261003581805123232252121250714353889973910175603967233483
906373653403967078236234105538735257626455633191051268483763776519939676532922968894290809165973462
463682386145658844710392934294962586064977659544105079042036455112549849444488355058060663395700794
581835385881588086880018088665815764185714462108665806065367293710281248797530284561909750274747982
597398157140508585743951532805732206773811470509273089822523733923978604285883458608961326308666481
747291430398802472215254437718543981344679179978365466843766666914403157884645513051212136970443329
244837874509125799917021122025857013425466265500665396560698837650448497362740593815936767710444319
763660833891859792482507260554926580833552382388650101112610105921059786504029084803436997490837451
350649861444474860908072929803501133573112841605420263273407010769566501561563124374826573032029828
177685708096629504717361777889012350276854446323355005993595322255016419302221041636340725515608138
114745809397669463425366950058428122210465316633044929201961289067434501492906919201597801471922521
986080362956506790341255149347831682899945172377608219674813371159152538254860681805214154187340041
800776419859894297108198933484096786109576906464484289390300285929941938529609091021938001241816893
483770904449123758719254360474997891553501047392820015348290203933183201322231731924536857632376399
065907593615595869102406986877291091583691337510319960214478477911034257117507079616331220633732573
703867994104261466325472079333753164589524466321889918877649454605798109855164200381364479564404959
220070347887513052548525226507935888761483739705528456877977602834009322056824655468219806819432491
835779336111910957190369503811463022895836005754274864863383828490628478805575689180969344816360294
2498371018667

2290桁
Rubyすごいです!
頭を使って法則を探していたのがバカらしくなってしまいます。

今時のコンピュータ言語では常識なんでしょうか?
VBScript + WSHで試してみます。

x = 1
For i = 1 To 4798
  x = x * 3
  WScript.Echo x
  i = i + 1
Next

オーバーフローします。
今まで知っていた普通の言語の動作です。
PHPで試してみます。

<?php
$x = 1;
for ($i = 1; $i <= 4798; $i++) {
  $x *= 3;
  echo $x . "\n";
}
?>

止まらないのだけれど、途中から 1.#INF というわけの分からない値が出るようになります。
別途ライブラリが必要らしいです。
繰り返しが自分としては一番落ち着いて早く書けるありがたい文法構造なのですけど。

Rubyが気が利いていると見るのが正しいようです。

力業の結果、500乗で末尾4桁が、2500乗で末尾5桁が循環するというのは正しいことが判明しました。
理屈は分からないけど。
数学的帰納法を使えば証明できるのかな?