3の33乗はどうやって計算すべきか？

果たして自分に解けるだろうか？やってみた。

• 3の33乗は何桁の整数か？
• 3の33乗の最高位の数字は何か？
  • log10(2)=0.3010
  • log10(3)=0.4771

数学教師「バカ正直に計算して合ってたのはお前だけだ」... on Twitpic

根性

3
9
27
81
243
729
2187
6561
19683
59049
177147
531441
1594323
4782969
14348907
43046721
129140163
387420489
1162261467
3486784401
10460353203
31381059609
94143178827
282429536481
847288609443
2541865828329
7625597484987
22876792454961
68630377364883
205891132094649
617673396283947
1853020188851841
5559060566555523

バイナリ法

手計算でやるにしても、素晴らしく賢い方法があった！

• コメントで教えていただいた。（aさん、ありがとう！）
• 3の33乗を以下のように変形すれば良いのだ。

3^33 = (3^32)×3 = ((3^16)^2)×3 = (((3^8)^2)^2)×3 = ((((3^4)^2)^2)^2)×3 = (((((3^2)^2)^2)^2)^2)×3

• 計算してみる。

3^2 = 9
9^2 = 81
81^2 = 6561
6561^2 = 43046721
43046721^2 = 1853020188851841
1853020188851841×3 = 5559060566555523

• 43046721^2の計算はちと辛いが、これなら十分テスト時間中に対応できる計算量かもしれない。

素晴らしい方法だ！

æ•°å­¦

logについて

• log10(2)は、10ã‚’n乗したら2になると考えて、そのnを求める関数。
• log10(3)は、10ã‚’n乗したら3になると考えて、そのnを求める関数。

つまり...

• log10(2)=0.3010
• log10(3)=0.4771

であれば....

• 10^0.3010=2
• 10^0.4771=3

指数計算の性質

• 10^2×10^2＝10^4
• 10^4÷10^2=10^2

つまり...

• 累乗同士の掛算は、指数の足し算になる。
• 累乗同士の割算は、指数の引き算になる。

• (10^3)^3=1000^3=1000 000 000=10^9

つまり...

• 累乗の累乗は、指数の掛算になる。

計算過程

以上の知識を使って計算してみる。

　3^33 ＝ (10^0.4771)^ 33 ＝ 10^(0.4771×33) ＝ 10^15.7443
＝10^0.7443 × 10^15

• 10^1未満は必ず10未満の数になるので、1桁。
• 上記に10^15を掛算すると0が15個追加され16桁になる。

ゆえに...

• 3の33乗は何桁の整数か？

16桁の整数。

• ここで、10^0.7443 がいくつになるかを考えてみる。

2 ＝ 10^0.3010
3 ＝ 10^0.4771
4 ＝ 10^(0.3010+0.3010) ＝ 10^0.6020
5 ＝ ？
6 ＝ 10^(0.3010+0.4771) ＝ 10^0.7781

• 4以上6未満の数であることは確認できた。
• しかし、4.xなのか、5.xなのかは、まだ不明。

2 ＝ 10^0.3010
3 ＝ 10^0.4771
1.5 ＝ 10^(0.4771-0.3010) ＝ 10^0.1761
2.25 ＝ 10^(0.1761+0.1761) ＝ 10^0.3522
5.0625 ＝ 10^(0.3522+0.3522) ＝ 10^0.7044
6 ＝ 10^(0.3010+0.4771) ＝ 10^0.7781

つまり...

• 10^0.7443は、5.0625以上6未満、5.xな数であることが確認できた。

ゆえに...

• 3の33乗の最高位の数字は何か？

5

より簡単なlog10(5)の求め方

• 与えられたlog10(2)とlog10(3)しか見えてなくて、
• log10(1.5×1.5×1.5×1.5) ＝ log10(5.0625)を求めるという荒技になってしまっていたが...

よりスマートな方法があった！

• log10(10) ＝ 1は自明なわけなので、（10^1 ＝ 10）

2 ＝ 10^0.3010
10 ＝ 10^1
5 = 10^(1-0.3010) ＝ 10^0.6990

追加

• 先生はちょっと意地悪になった。さらなる問題を出してきた。

では、3の333乗の全桁を正確に求めなさい。何を使っても構いません。

• もはや根性は通用しない。
• 数学の技を駆使しても、全桁を正確に求めるには計算するしかない。
• 普通の電卓で、果たして桁数が足りるのだろうか。

google

• 桁数が不足...。

iPhoneの電卓

• 電卓を横向きにしても16桁までしか表示できない。

• 桁数が不足...。

OSXの計算機

• 科学計算にして42桁表示できる。
• 普通はこれで十分。でも今回は足りない。

• 数値ではありません、と。（いやいや、数値ですから。電卓のくせに、すごい言い訳）

AppleScript

• 桁数が不足...。
• ならば、自分でコードを書いて計算してみた。

 math_power(3, 333) 

 on math_power(base, exponent)   set digit to 100000000

   set num_list to {1}   set carry to 0

   repeat exponent times

     if num_list's last item ≠ 0 then

       set num_list's end to 0

     end if

          repeat with num in num_list

       set num's contents to num * base + carry

       if num ≥ digit then

         set carry to round num / digit rounding down

         set num's contents to num mod digit

       else

         set carry to 0

       end if

     end repeat

   end repeat

   num_list's reverse as text

 end math_power

• 果たして、合っているのだろうか？まだ確認する術がない...。

結果：
"076098802313205980972042586726503278072789635637207786511701003735791631439306199613044145649378522557935351570949952011833769302566531786879537190794573523"

• 上記の結果は間違っていたので修正版

 math_power(3, 333) 

 on math_power(base, exponent)   set digit to 100000000

   set num_list to {1}   set carry to 0

   repeat exponent times

     if num_list's last item ≠ 0 then

       set num_list's end to 0

     end if

          repeat with num in num_list

       set num's contents to num * base + carry

       if num ≥ digit then

         set carry to round num / digit rounding down

         set num's contents to num mod digit

       else

         set carry to 0

       end if

     end repeat

   end repeat

      repeat with num in num_list

     set str to num + digit as text

     set num's contents to str's items 2 thru -1 as text

   end repeat

   num_list's reverse as text

 end math_power

結果：
"000000000760988023132059809720425867265032780727896356372077865117010037035791631439306199613044145649378522557935351570949952010001833769302566531786879537190794573523"

Perl

$ perl -e 'use Math::BigInt;print 3**333,"\n"'
7.6098802313206e+158

• やはり桁数が不足か...。

もとい！

$ perl -e 'use Math::BigInt;$num=Math::BigInt->new(3);print $num**333,"\n"'
760988023132059809720425867265032780727896356372077865117010037035791631439306199613044145649378522557935351570949952010001833769302566531786879537190794573523

#より簡潔に書けるのであった

$ perl -Mbignum -e 'print 3**333,"\n"'
760988023132059809720425867265032780727896356372077865117010037035791631439306199613044145649378522557935351570949952010001833769302566531786879537190794573523

できた！

• AppleScriptの結果と一致した！

Ruby

$ ruby -e 'puts 3**333'
760988023132059809720425867265032780727896356372077865117010037035791631439306199613044145649378522557935351570949952010001833769302566531786879537190794573523

恐るべし！

• 普通に書いて計算できてしまった！

Python

$ python -c 'print 3**333'
760988023132059809720425867265032780727896356372077865117010037035791631439306199613044145649378522557935351570949952010001833769302566531786879537190794573523

• Pythonも当然の如く出力した！