kadai78

平成１８年１２月２４日

[流れ星]

　　　　　第1８３回数学的な応募問題解答

　　　　　　＜解答募集期間：１２月３日～１2月２４日

［最高位の数字］

皆さん、今年度早稲田大学（教育学部）の入試問題を参考して出題します。是非チャレンジください。

２^５５５は十進法で表すと１６８桁の数で、その最高位（先頭）の数字は１である。集合｛２^ｎ｜ｎは整数で１≦ｎ≦５５５｝の中に、十進法で表した最高位の数字Ｎについて、

問題：Ｎ＝４は何回現れるか。

追加問題、Ｎ＝１，２，３，５，６，７，８，９はそれぞれ何回現れるか気になります。誰か教えてください。

＜独り言：まだ、正解に至っていません。法則性がないのかもしれませんが・・・＞

NO1「uchinyan」12/03 17時33分受信

「uchinyan」12/03 18時32分受信

「uchinyan」12/05 16時07分受信

「uchinyan」12/07 15時44分受信更新12/24

＜水の流れ：最後に受信したものをアップさせて頂きます＞

第１８３回数学的な応募問題
［最高位の数字］

問題：Ｎ＝４は何回現れるか。

最上位桁の数字の出現は、繰り上がりの有無を考慮すると、繰り上がりは高々 +1 なので、
次のパターン、ループ、が考えられます。
1 -> 2 -> 4 -> 8 -> 1 : 全く繰り上がりなし
1 -> 2 -> 4 -> 9 -> 1 : 4 * 2 のところで繰り上がり
1 -> 2 -> 5 -> 1 : 2 * 2 のところで繰り上がり
1 -> 3 -> 6 -> 1 : 1 * 2 のところだけで繰り上がり
1 -> 3 -> 7 -> 1 : 1 * 2, 3 * 2 のところで繰り上がり
そして、1 に戻ったとき、つまり、ループが閉じたときに、桁が一つ増えます。
今、2^555 の最上位桁の数字は 1 なので、これらループをいくつか繰り返し閉じた場合になっています。
さらに、2^555 の桁は 168 桁なので、2^1 から初めて、上記のループが 168 - 1 = 167 個入っていなければなりません。
さて、4 が出現するのは、上記のループのうち、2 倍する回数、-> の個数、
これをループの長さともいうことにします、が 4 回の上二つです。
そこで、4 の出現回数を x とすると、上二つのループが合計 x 個、下三つのループが合計 167-x 個、
あることになります。
さらに、ループの長さだけ 2 のべきが増えるので、次の関係がいえます。
4 * x + 3 * (167 - x) = 555
これを解いて、x = 54、つまり、4 は 54 回出現します。

(別解)
2^555 の与えられた情報を使わない解法です。

取り敢えず、具体的に調べてみます。
2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32,
2^6 = 64, 2^7 = 128, 2^8 = 256, 2^9 = 512, 2^10 = 1024,
2^11 = 2048, 2^12 = 4096, 2^13 = 8192, 2^14 = 16384, 2^15 = 32768,
2^16 = 65536, 2^17 = 131072, 2^18 = 262144, 2^19 = 524288, 2^20 = 1048576, ,,,
ということで、2^(10n+1) ～ 2^(10(n+1)) の間におおよそ一つずつ現れそうですが、
2^10 と 2^20 とを比べると分かるように、少しずつずれていくようです。

まず、4 は一度出現したら 2^10 倍以降でないと再度現れないことを示します。
今、2^(10n+k), 1 <= k <= 10, の最高位の数字が 4 になったとします。
各位の数字は最高でも 9 なので、2 倍したときの桁上がりの数字は、高々 1 です。
(99..99 * 2 = 199..98 だから。)
そこで、最高位の 4 に対して 2 倍していくと、最高位の周辺の数字は、次のように変化します。
4 　
-*2:*2^1->
8, 9
-*2:*2^2->
16, 17, 18, 19
-*2:*2^3->
32, 33, 34, 35, 36, 37, 38, 39
-*2:*2^4->
64 ～ 79
-*2:*2^5->
128 ～ 159
-*2:*2^6->
256 ～ 319
-*2:*2^7->
512 ～ 639
-*2:*2^8->
1024 ～ 1279
-*2:*2^9->
2048 ～ 2559
-*2:*2^10->
4096 ～ 5119
そこで、2^(10n+k) * 2^10 = 2^(10(n+1)+k) になって、初めて再び 4 が現れる可能性があります。
しかし、桁上がりのために 4 をスキップして 5 になってしまう可能性もあります。
つまり、4 は一度出現してから 2^10 倍するまでは出現することはなく、
2^10 倍した時点で、出現するか、スキップして 5 になってしまうか、のいずれかです。
これで、4 は一度出現したら 2^10 倍以降でないと再度現れないこと、が分かりました。
さらにこの後、スキップして 5 になった場合には、
-*2:*2^10->
5
-*2:*2^11->
10, 11
-*2:*2^12->
20, 21, 22, 23
-*2:*2^13->
40, 41, 42, 43, 44, 45, 46, 47
となり、スキップ後、2^3 倍して、再び 4 が現れます。以下同様です。

さて、では、どんな場合にスキップするのでしょうか？
これは同様にして、2^10 = 1024 倍したときの上位の桁の様子を調べることで分かります。
繰り上がりを考慮しながら、最上位の数字が正しくなるように、上位三桁を四捨五入での近似計算で調べていくと、
2^2 =
4
-*2^10:*2^10->
4096
-*2^10:*2^20->
419...
(= 4096 * 1024 -> 4096 + 81.9 + 16.4 = 4194.3)
-*2^10:*2^30->
429...
(= 4194 * 1024 -> 4194 + 83.9 + 16.8 = 4294.7)
-*2^10:*2^40->
439...
(= 4295 * 1024 -> 4295 + 85.9 + 17.2 = 4398.1)
-*2^10:*2^50->
450...
(= 4398 * 1024 -> 4398 + 88.0 + 17.6 = 4503.6)
-*2^10:*2^60->
461...
(= 4504 * 1024 -> 4504 + 90.1 + 18.0 = 4612.1)
-*2^10:*2^70->
472...
(= 4612 * 1024 -> 4612 + 92.2 + 18.4 = 4722.6)
-*2^10:*2^80->
483...
(= 4723 * 1024 -> 4723 + 94.5 + 18.9 = 4836.4)
-*2^10:*2^90->
495...
(= 4836 * 1024 -> 4836 + 96.7 + 19.3 = 4952.0)
-*2^10:*2^100->
507...
(= 4952 * 1024 -> 4952 + 99.1 + 19.8 = 5070.9)
となり、2^2 * 2^100 = 2^102 でスキップします。このとき、2^3 倍で再び 4 が現れ、
2^105 =
4056...
-*2^10:*2^10->
415...
(= 4056 * 1024 -> 4056 + 81.1 + 16.2 = 4153.3)
-*2^10:*2^20->
425...
(= 4153 * 1024 -> 4153 + 83.1 + 16.6 = 4252.7)
-*2^10:*2^30->
435...
(= 4253 * 1024 -> 4253 + 85.0 + 17.0 = 4355.0)
-*2^10:*2^40->
445...
(= 4355 * 1024 -> 4355 + 87.1 + 17.4 = 4459.5)
-*2^10:*2^50->
456...
(= 4460 * 1024 -> 4460 + 89.2 + 17.8 = 4567.0)
-*2^10:*2^60->
467...
(= 4567 * 1024 -> 4567 + 91.3 + 18.3 = 4676.6)
-*2^10:*2^70->
478...
(= 4677 * 1024 -> 4677 + 93.5 + 18.7 = 4789.2)
-*2^10:*2^80->
490...
(= 4789 * 1024 -> 4789 + 95.8 + 19.2 = 4904.4)
-*2^10:*2^90->
502...
(= 4904 * 1024 -> 4904 + 98.1 + 19.6 = 5021.7)
となり、2^105 * 2^90 = 2^195 でスキップします。このとき、2^3 倍で再び 4 が現れ、
2^198 =
4017...
...
計算が面倒なので省略しますが、以下同様の計算をすると、
2^298 = 509... でスキップし、2^301 = 407... で 4 が復活。
2^391 = 504... でスキップし、2^394 = 403... で 4 が復活。
2^494 = 511(4)... し、2^497 = 409... で 4 が復活。
2^587 = 506... でスキップする。
となるようです。

以上をまとめると、最上位での 4 の出現は、
・一度出現したら 2^10 倍以降でないと再度現れない。
・原則、2^2 = 4 以降 2^10 倍ごとに現れるが、
　2^102, 2^195, 2^298, 2^391, 2^494, 2^587 でスキップする。
　(スキップの仕方は、2^90 倍又は 2^100 倍で、これは、スキップ後初めて 4 が出現する際の
　上位桁 40X... の X の値によりそう。)
・一度スキップしたら、その後、2^3 倍で再び 4 が現れる。
となります。
そこで、2^1 ～ 2^555 では、4 は、
　(102 - 2)/10 + (195 - 105)/10 + (298 - 198)/10 + (391 - 301)/10 + (494 - 394)/10 + (457 - 497)/10
　= 10 + 9 + 10 + 9 + 10 + 6 = 54 回
出現することになります。

(考察)
最初、2^555 に関する情報を使うのを忘れており、(別解)で答えを得ました。
ただ、(別解)は、何とか答えは出るものの、スキップの評価がうまくいかず、非常に泥臭く、
計算も大変です。とても、試験場では答えは出ないでしょう。
ただ、かなり一般的で、それなりに強力な手法のようです。後の追加問題でも使えます。
なお、規則性という意味では、どうやら、スキップの間隔が 2^100 倍と 2^90 倍を繰り返している様子なので、
それを基に出現回数の類推はできますが、証明はできていません。
いずれにせよ、(別解)は、受験ではダメですね。
入試問題で解けるためには、やはり、2^555 に関する情報をうまく使わないとダメなようです。

追加問題：
Ｎ＝１，２，３，５，６，７，８，９はそれぞれ何回現れるか気になります。誰か教えてください。

(解法1)
N = 4 は、うまく 2 倍する回数が 4 回のループに分離できたのですが、
N = 1 以外の一般の場合は、そう簡単ではなさそうです。
なお、N = 1 の場合は、ループの個数なので、明らかに 167 回です。
取り敢えず、十進ベーシックでプログラムを組んで調べました。

OPTION ARITHMETIC DECIMAL_HIGH

DIM c(9)

FUNCTION check(x)
　DO WHILE x > 0
　　IF x <= 9 THEN
　　　LET check = x
　　END IF
　　LET x = INT(x/10)
　LOOP
END FUNCTION

MAT c = ZER
LET a = 1
FOR i = 1 TO 555
　LET a = a * 2
　REM PRINT i; a
　LET k = check(a)
　LET c(k) = c(k) + 1
NEXT i
REM PRINT
FOR i = 1 TO 9
　PRINT "N ="; i; ","; c(i); "回"
NEXT i
END

結果は、

N = 1 , 167 回
N = 2 , 99 回
N = 3 , 68 回
N = 4 , 54 回
N = 5 , 45 回
N = 6 , 37 回
N = 7 , 31 回
N = 8 , 30 回
N = 9 , 24 回

となりました。

(解法2)
問題：における(別解)の手法を拡張します。

問題：の冒頭で書いたように、最上位桁の数字の出現は、繰り上がりの有無を考慮すると、
繰り上がりは高々 +1 なので、次のパターン、ループ、が考えられます。
1 -> 2 -> 4 -> 8 -> 1 : 全く繰り上がりなし
1 -> 2 -> 4 -> 9 -> 1 : 4 * 2 のところで繰り上がり
1 -> 2 -> 5 -> 1 : 2 * 2 のところで繰り上がり
1 -> 3 -> 6 -> 1 : 1 * 2 のところだけで繰り上がり
1 -> 3 -> 7 -> 1 : 1 * 2, 3 * 2 のところで繰り上がり
これをよく見ると、5, 6, 7, 8, 9 は、各ループだけにそれぞれ 1 回ずつ出現します。
そこで、これらの出現回数が分かれば、
1 の出現回数 = 5 の出現回数 + 6 の出現回数 + 7 の出現回数 + 8 の出現回数 + 9 の出現回数
2 の出現回数 = 5 の出現回数 + 8 の出現回数 + 9 の出現回数
3 の出現回数 = 6 の出現回数 + 7 の出現回数
4 の出現回数 = 8 の出現回数 + 9 の出現回数
で、すべて分かります。
そこで、以下では、5, 6, 7, 8, 9 の出現回数を考えます。
これには、問題：における(別解)の手法を使えます。

まず、5, 6, 7, 8, 9 は、それぞれ、一度出現したら 2^10 倍以降でないと再度現れません。
これは、(別解)の場合と同様にして、桁上がりを考慮して *2 をしていくと、
・5 の場合
5
-*2:*2^1-> 10, 11 -*2:*2^2-> 20 ～ 23 -*2:*2^3-> 40 ～ 47
-*2:*2^4-> 80 ～ 95 -*2:*2^5-> 160 ～ 191 -*2:*2^6-> 320 ～ 383
-*2:*2^7-> 640 ～ 767 -*2:*2^8-> 1280 ～ 1535 -*2:*2^9-> 2560 ～ 3071
-*2:*2^10-> 5120 ～ 6143
・6 の場合
6
-*2:*2^1-> 12, 13 -*2:*2^2-> 24 ～ 27 -*2:*2^3-> 48 ～ 55
-*2:*2^4-> 96 ～ 111 -*2:*2^5-> 192 ～ 223 -*2:*2^6-> 384 ～ 447
-*2:*2^7-> 768 ～ 895 -*2:*2^8-> 1536 ～ 1791 -*2:*2^9-> 3072 ～ 3583
-*2:*2^10-> 6144 ～ 7167
・7 の場合
7
-*2:*2^1-> 14, 15 -*2:*2^2-> 28 ～ 31 -*2:*2^3-> 56 ～ 63
-*2:*2^4-> 112 ～ 127 -*2:*2^5-> 224 ～ 255 -*2:*2^6-> 448 ～ 511
-*2:*2^7-> 896 ～ 1023 -*2:*2^8-> 1792 ～ 2047 -*2:*2^9-> 3584 ～ 4095
-*2:*2^10-> 7168 ～ 8191
・8 の場合
8
-*2:*2^1-> 16, 17 -*2:*2^2-> 32 ～ 35 -*2:*2^3-> 64 ～ 71
-*2:*2^4-> 128 ～ 143 -*2:*2^5-> 256 ～ 287 -*2:*2^6-> 512 ～ 575
-*2:*2^7-> 1024 ～ 1151 -*2:*2^8-> 2048 ～ 2303 -*2:*2^9-> 4096 ～ 4607
-*2:*2^10-> 8192 ～ 9215
・9 の場合
9
-*2:*2^1-> 18, 19 -*2:*2^2-> 36 ～ 39 -*2:*2^3-> 72 ～ 79
-*2:*2^4-> 144 ～ 159 -*2:*2^5-> 288 ～ 319 -*2:*2^6-> 576 ～ 639
-*2:*2^7-> 1152 ～ 1279 -*2:*2^8-> 2304 ～ 2559 -*2:*2^9-> 4608 ～ 5119
-*2:*2^10-> 9216 ～ 10239
となることから、明らかです。
また、4 の場合と同様に、2^10 倍して再度出現するか、一つずれてスキップするかのどちらかです。

では、スキップした場合にはその後どうなるのでしょうか？
これは、上記の計算を見れば分かるように、スキップした際に出現する数のより下位の桁に依存して、
様々な可能性があるようで、残念ながら、4 の場合のように簡単ではないようです。
そこで、詳しく調べてみると、2^10 倍の間で次のようになっているのが分かります。
ただし、9 -> 10 のスキップは、一つ前の 9 -> 5 と等価、ただし 2 倍ずれる、なので、
それで表示してあります。
・5 -> 6：上位桁が 625 未満では 5 は出現せず、625 以上では 2^3 倍で 5 が出現する。
・6 -> 7：上位桁が 75 未満では 6 は出現せず、75 以上では 2^3 倍で 6 が出現する。
・7 -> 8：上位桁が 875 未満では 7 は出現せず、875 以上では 2^3 倍で 7 が出現する。
・8 -> 9：8 は、9 -> 5 の後、2^4 倍で出現する。これは、9 のスキップが 10xxx のため。
・9 -> 5：9 -> 5 の後 2^4 倍で 8 が出現し、その後、8 -> 9 で出現する。
ここで、実は面白いことが分かります。それは、例えば、
・5 -> 6 での 5 が再び出現する上位桁が 625 以上は、2^6 する前の状態を考えると、
　最上位桁が 9 又は 10 になっているが、
　10 の場合は、5 が再出現するときから見て 2^10 する前の最上位桁も 5 ということなので、
　5 -> 6 は発生せず、したがって、最上位桁は 9 になっていなければならない。
　つまり、5 の再出現は 9 -> 5 のスキップによる。
ということです。同様にして、
・6 -> 7 での 6 が再び出現する上位桁が 75 以上は、2^7 する前の状態を考えると、
　最上位桁が 5 又は 6 になっているが、
　6 の場合は、6 が再出現するときから見て 2^10 する前の最上位桁も 6 ということなので、
　6 -> 7 は発生せず、したがって、最上位桁は 5 になっていなければならない。
　つまり、6 の再出現は 5 -> 6 のスキップによる。
・7 -> 8 での 7 が再び出現する上位桁が 875 以上は、2^7 する前の状態を考えると、
　最上位桁が 6 又は 7 になっているが、
　7 の場合は、7 が再出現するときから見て 2^10 する前の最上位桁も 7 ということなので、
　7 -> 8 は発生せず、したがって、最上位桁は 6 になっていなければならない。
　つまり、7 の再出現は 6 -> 7 のスキップによる。
・8 -> 9 の後 9 -> 5 を経由しての 8 の再出現は、9 の系列が必ず最上位桁が 7 の場合を経るので、
　この状態から数えて 2^6 * 2^4 = 2^10 倍になっており、これは、7 -> 8 の移行に等しい。
　つまり、8 の再出現は 7 -> 8 のスキップによる。
・9 -> 5 での 9 の再出現は、明らかに、8 -> 9 のスキップによる。
結局、まとめると、
・5 -> 6 後の 5 の出現は、9 -> 5 による。
・6 -> 7 後の 6 の出現は、5 -> 6 による。
・7 -> 8 後の 7 の出現は、6 -> 7 による。
・8 -> 9 後の 8 の出現は、7 -> 8 による。
・9 -> 5 後の 9 の出現は、8 -> 9 による。
これは、かなり興味深い性質です。
また、これ以外の出現は、2^10 の擬似周期によるものなので、
結局、5, 6, 7, 8, 9 の出現は、上記の性質か、2^10 の擬似周期か、のいずれかとなります。
なお、以上の議論は、数字の並びだけに関係するので、小数点がどこにあるかには依存しません。
つまり、2 の正の整数べきだけでなく、0 や負の整数べきでも成立します。
性質は循環的なので、どれか一つをしっかり調べれば、後はこの性質を使って計算が少し楽になります。

さて、いよいよ、この性質を使ってスキップの状況を具体的に調べます。
なお、この問題では、2^1 から開始していることに注意します。
これは、近似計算でもできますが、大変ですし、ここでは、Windows付属の電卓を叩いて調べました。
どの数字から始めてもいいのですが、最初の計算はしっかりとやらないといけないので、
規則が比較的簡単な 8, 9 から始めます。
・8, 9 の場合
出発点なので、これは真面目にやります。最初は、2^3 = 8 です。
2^3 = 8
-*2^10:*2^10-> 8192... -*2^10:*2^20-> 8388... -*2^10:*2^30-> 8589...
-*2^10:*2^40-> 8796... -*2^10:*2^50-> 9007...
2^(3 + 50) = 2^53 = 9007... で 8 がスキップ＆ 9 が出現
計算結果は、単純に上位桁だけを拾っています。最上位の数字だけが問題なので、これで十分です。
この 9 は、実は、2^1 以上では最初の出現です。
これは、電卓を叩いても分かりますが、
先の性質から、9 の出現は、2^10 擬似周期以外は、8 -> 9 だったことからも明らかです。
2^53 = 9007...
-*2^10:*2^10-> 9223... -*2^10:*2^20-> 9444... -*2^10:*2^30-> 9671...
-*2^10:*2^40-> 9903... -*2^10:*2^50-> 10141...
2^(53 + 50) = 2^103 で 9 がスキップ＆ 2^102 = 50706... で 5 が出現
ここで、5 の出現の場所は、5 の場合の計算で使うので、念のために、桁を一つ増やしてあります。
2^102 = 5070...
-*2^4:*2^4-> 8112...
2^(102 + 4) = 2^106 = 8112... で 8 が出現
2^106 = 8112...
-*2^10:*2^10-> 8307... -*2^10:*2^20-> 8507... -*2^10:*2^30-> 8711...
-*2^10:*2^40-> 8920... -*2^10:*2^50-> 9134...
2^(106 + 50) = 2^156 = 9134... で 8 がスキップ＆ 9 が出現
2^156 = 9134...
-*2^10:*2^10-> 9353... -*2^10:*2^20-> 9578... -*2^10:*2^30-> 9807...
-*2^10:*2^40-> 10043...
2^(156 + 40) = 2^196 で 9 がスキップ＆ 2^195 = 50216... で 5 が出現
2^195 = 5021...
-*2^4:*2^4-> 8034...
2^(195 + 4) = 2^199 = 8034... で 8 が出現
2^199 = 8034...
-*2^10:*2^10-> 8227... -*2^10:*2^20-> 8424... -*2^10:*2^30-> 8627...
-*2^10:*2^40-> 8834... -*2^10:*2^50-> 9046...
2^(199 + 50) = 2^249 = 9046... で 8 がスキップ＆ 9 が出現
2^249 = 9046...
-*2^10:*2^10-> 9263... -*2^10:*2^20-> 9485... -*2^10:*2^30-> 9713...
-*2^10:*2^40-> 9946... -*2^10:*2^50-> 10185...
2^(249 + 50) = 2^299 で 9 がスキップ＆ 2^298 = 50925... で 5 が出現
2^298 = 5092...
-*2^4:*2^4-> 8148...
2^(298 + 4) = 2^302 = 8148... で 8 が出現
2^302 = 8148...
-*2^10:*2^10-> 8343... -*2^10:*2^20-> 8543... -*2^10:*2^30-> 8749...
-*2^10:*2^40-> 8958... -*2^10:*2^50-> 9173...
2^(302 + 50) = 2^352 = 9173... で 8 がスキップ＆ 9 が出現
2^352 = 9173...
-*2^10:*2^10-> 9394... -*2^10:*2^20-> 9619... -*2^10:*2^30-> 9850...
-*2^10:*2^40-> 10086...
2^(352 + 40) = 2^392 で 9 がスキップ＆ 2^391 = 50434... で 5 が出現
2^391 = 5043...
-*2^4:*2^4-> 8069...
2^(391 + 4) = 2^395 = 8069... で 8 が出現
2^395 = 8069...
-*2^10:*2^10-> 8263... -*2^10:*2^20-> 8461... -*2^10:*2^30-> 8664...
-*2^10:*2^40-> 8872... -*2^10:*2^50-> 9085...
2^(395 + 50) = 2^445 = 9085... で 8 がスキップ＆ 9 が出現
2^445 = 9085...
-*2^10:*2^10-> 9303... -*2^10:*2^20-> 9526... -*2^10:*2^30-> 9755...
-*2^10:*2^40-> 9989... -*2^10:*2^50-> 10229...
2^(445 + 50) = 2^495 で 9 がスキップ＆ 2^494 = 51146... で 5 が出現
2^494 = 5114...
-*2^4:*2^4-> 8183...
2^(494 + 4) = 2^498 = 8183... で 8 が出現
2^498 = 8183...
-*2^10:*2^10-> 8379... -*2^10:*2^20-> 8580... -*2^10:*2^30-> 8786...
-*2^10:*2^40-> 8997... -*2^10:*2^50-> 9213...
2^(498 + 50) = 2^548 = 9213... で 8 がスキップ＆ 9 が出現
2^548 = 9213...
-*2^10:*2^10-> 9434... -*2^10:*2^20-> 9661... -*2^10:*2^30-> 9893...
-*2^10:*2^40-> 10130...
2^(548 + 40) = 2^588 で 9 がスキップ＆ 2^587 = 50653... で 5 が出現
2^587 = 5065...
-*2^4:*2^4-> 8104...
2^(587 + 4) = 2^591 = 8104... で 8 が出現
以上より、結局、2^555 までで、
8 の出現回数は、最後に注意して、
　(53 - 3)/10 + (156 - 106)/10 + (249 - 199)/10 + (352 - 302)/10
　+ (445 - 395)/10 + (548 - 498)/10
　= 5 + 5 + 5 + 5 + 5 + 5 = 30 回
9 の出現回数は、最後に注意して、
　(103 - 53)/10 + (196 - 156)/10 + (299 - 249)/10 + (392 - 352)/10
　+ (495 - 445)/10 + (558 - 548)/10
　= 5 + 4 + 5 + 4 + 5 + 1 = 24 回
になります。
・5 の場合
まず、最初の出現ですが、これは、実際に計算して 2^9 = 512 です。
このことは、2^0 = 1 のために、2^(-1) = 0.5 なので、10 - 1 = 9 よりも分かります。
次の出現は、9 -> 5 となるところなので、8, 9 の場合から、2^102 = 50706... です。
この間の 5 のスキップは、次の計算から分かります。
2^9 = 512
-*2^10:*2^10-> 5242... -*2^10:*2^20-> 5368... -*2^10:*2^30-> 5497...
-*2^10:*2^40-> 5629... -*2^10:*2^50-> 5764... -*2^10:*2^60-> 5902...
-*2^10:*2^70-> 60446...
2^(9 + 70) = 2^79 = 60446... で 5 がスキップ＆ 6 が出現
計算結果は、単純に上位４桁だけを拾っています。最上位の数字だけが問題なので、これで十分です。
なお、スキップする場所だけ、6 の場合の計算で使うので、念のために、桁を一つ増やしてあります。
以下同様にして、
2^102 = 50706... で 5 が出現
-*2^10:*2^10-> 5192... -*2^10:*2^20-> 5316... -*2^10:*2^30-> 5444...
-*2^10:*2^40-> 5575... -*2^10:*2^50-> 5708... -*2^10:*2^60-> 5846...
-*2^10:*2^70-> 5986... -*2^10:*2^80-> 61299...
2^(102 + 80) = 2^182 = 61299... で 5 がスキップ＆ 6 が出現
2^195 = 50216... で 5 が出現
-*2^10:*2^10-> 5142... -*2^10:*2^20-> 5265... -*2^10:*2^30-> 5391...
-*2^10:*2^40-> 5521... -*2^10:*2^50-> 5653... -*2^10:*2^60-> 5789...
-*2^10:*2^70-> 5928... -*2^10:*2^80-> 60707...
2^(195 + 80) = 2^275 = 60707... で 5 がスキップ＆ 6 が出現
2^298 = 50925... で 5 が出現
-*2^10:*2^10-> 5214... -*2^10:*2^20-> 5339... -*2^10:*2^30-> 5468...
-*2^10:*2^40-> 5599... -*2^10:*2^50-> 5733... -*2^10:*2^60-> 5871...
-*2^10:*2^70-> 60121...
2^(298 + 70) = 2^368 = 60121... で 5 がスキップ＆ 6 が出現
2^391 = 50434... で 5 が出現
-*2^10:*2^10-> 5164... -*2^10:*2^20-> 5288... -*2^10:*2^30-> 5415...
-*2^10:*2^40-> 5545... -*2^10:*2^50-> 5678... -*2^10:*2^60-> 5814...
-*2^10:*2^70-> 5954... -*2^10:*2^80-> 60970...
2^(391 + 80) = 2^471 = 60970... で 5 がスキップ＆ 6 が出現
2^494 = 51146... で 5 が出現
-*2^10:*2^10-> 5237... -*2^10:*2^20-> 5363... -*2^10:*2^30-> 5491...
-*2^10:*2^40-> 5623... -*2^10:*2^50-> 5758... -*2^10:*2^60-> 5896...
-*2^10:*2^70-> 60382...
2^(494 + 70) = 2^564 = 60382... で 5 がスキップ＆ 6 が出現
以上より、5 の出現回数は、出現からスキップまでを繰り返し数えればよく、
この間 2^10 ごとに一つずつなので、2^555 まででは、最後に注意して、
　(79 - 9)/10 + (182 - 102)/10 + (275 - 195)/10 + (368 - 298)/10
　+ (471 - 391)/10 + (564 - 494)/10
　= 7 + 8 + 8 + 7 + 8 + 7 = 45 回
になります。
・6 の場合
5 の場合の結果を使って、同様にして計算します。
2^6 = 64 で 6 が出現
-*2^10:*2^10-> 6553... -*2^10:*2^20-> 6710... -*2^10:*2^30-> 6871...
-*2^10:*2^40-> 70368...
2^(6 + 40) = 2^46 = 70368... で 6 がスキップ＆ 7 が出現
2^79 = 60446... で 6 が出現
-*2^10:*2^10-> 6189... -*2^10:*2^20-> 6338... -*2^10:*2^30-> 6490...
-*2^10:*2^40-> 6646... -*2^10:*2^50-> 6805... -*2^10:*2^60-> 6968...
-*2^10:*2^70-> 71362...
2^(79 + 70) = 2^149 = 71362... で 6 がスキップ＆ 7 が出現
2^182 = 61299... で 6 が出現
-*2^10:*2^10-> 6277... -*2^10:*2^20-> 6427... -*2^10:*2^30-> 6581...
-*2^10:*2^40-> 6739... -*2^10:*2^50-> 6901... -*2^10:*2^60-> 70672...
2^(182 + 60) = 2^242 = 70672... で 6 がスキップ＆ 7 が出現
2^275 = 60707... で 6 が出現
-*2^10:*2^10-> 6216... -*2^10:*2^20-> 6365... -*2^10:*2^30-> 6518...
-*2^10:*2^40-> 6674... -*2^10:*2^50-> 6835... -*2^10:*2^60-> 6999...
-*2^10:*2^70-> 71670...
2^(275 + 70) = 2^345 = 71670... で 6 がスキップ＆ 7 が出現
2^368 = 60121... で 6 が出現
-*2^10:*2^10-> 6156... -*2^10:*2^20-> 6304... -*2^10:*2^30-> 6455...
-*2^10:*2^40-> 6610... -*2^10:*2^50-> 6769... -*2^10:*2^60-> 6931...
-*2^10:*2^70-> 70978...
2^(368 + 70) = 2^438 = 70978... で 6 がスキップ＆ 7 が出現
2^471 = 60970... で 6 が出現
-*2^10:*2^10-> 6243... -*2^10:*2^20-> 6393... -*2^10:*2^30-> 6546...
-*2^10:*2^40-> 6703... -*2^10:*2^50-> 6864... -*2^10:*2^60-> 70293...
2^(471 + 60) = 2^531 = 70293... で 6 がスキップ＆ 7 が出現
2^564 = 60382... で 6 が出現
結局、6 の出現回数は、2^555 まででは、最後に注意して、
　(46 - 6)/10 + (149 - 79)/10 + (242 - 182)/10 + (345 - 275)/10
　+ (438 - 368)/10 + (531 - 471)/10
　= 4 + 7 + 6 + 7 + 7 + 6 = 37 回
になります。
・7 の場合
この場合は、特に計算をする必要はありません！　何故なら、
　7 の出現は 6 のスキップの位置　＆　7 のスキップは 8 の出現の位置
だからです。そこで、今までの計算から、
2^46 で 7 が出現
2^106 で 7 をスキップ
2^149 で 7 が出現
2^199 で 7 をスキップ
2^242 で 7 が出現
2^302 で 7 をスキップ
2^345 で 7 が出現
2^395 で 7 をスキップ
2^438 で 7 が出現
2^498 で 7 をスキップ
2^531 で 7 が出現
2^591 で 7 をスキップ
結局、7 の出現回数は、2^555 まででは、最後に注意して、
　(106 - 46)/10 + (199 - 149)/10 + (302 - 242)/10 + (395 - 345)/10
　+ (498 - 438)/10 + (561 - 531)/10
　= 6 + 5 + 6 + 5 + 6 + 3 = 31 回
になります。

ここまでをまとめると、結局、
・5 の出現回数は 45 回
・6 の出現回数は 37 回
・7 の出現回数は 31 回
・8 の出現回数は 30 回
・9 の出現回数は 24 回
になりました。そこで最初に述べたことから、
・1 の出現回数は 45 + 37 + 31 + 30 + 24 = 167 回
・2 の出現回数は 45 + 30 + 24 = 99 回
・3 の出現回数は 37 + 31 = 68 回
・4 の出現回数は 30 + 24 = 54 回
になります。
これは、(解法1)や、N = 4 の場合と一致しています。

(考察)
(解法2)の方法は地道で泥臭いし、電卓がなければかなり厳しいですが、
興味深い性質を浮き彫りにしてくれています。
基本は、2^10 = 1024 で 2^10 倍ごとに 10^3 から 24 だけずれることがポイントのように思います。
数字の出現パターンは、これに従って、擬似周期的振る舞いをしているようです。
残念ながら、それを明確に掴み切れていないのですが、何か、隠れていそうな感じはありますね。
もう少し詰められないかなぁ．．．

(感想)
久しぶりにかなり奥の深そうな問題です。
しかし、入試となると、私の場合、後回し or 捨てるとなりそうですね (^^;

NO2「浜田明巳」12/04 15時48分受信更新12/24
この手の計算はubasicにまかせるべきだろう．２^５５５もあっという間に計算してしまうプログラムだ．
　このプログラムによると，Ｎ＝１，２，３，・・・，９となるのはそれぞれ，
　　１６７，９９，６８，５４，４５，３７，３１，３０，２４
回となる．<br>
　残念ながら，規則性については，単調減少数列としか見えて来ない．もうすこしｎを増加させるとまた違う数列になるのだろうが．

   10   'asave "m183.ub"
   20   dim B(9)
   30   for J=1 to 9
   40     B(J)=0
   50   next J
   60   A=1
   70   for N=1 to 555<
   80     A*=2
   90     B(val(mid(str(A),2,1)))+=1
100   next N
110   for J=1 to 9
120     print J;B(J)
130   next J
140   print 2^555
150   end<b

NO3「Toru」　 12/07 11時03分受信更新12/24

問題

2^0=1より最高位の数字の数のみを問題にする時は
2^n 　（n=0～554）を考えても同じ
これらは2^nの形の１桁から１６７桁の数を全て含むことになるが、これを小さい方
から見て行くと桁数が上がったあとの最高位の数は必ず１であるから
各桁の数の最高位の数の組合せとしては
(1,2,4,8) (1,2,4,9) (1,2,5) (1,3,6) (1,3,7) の５通りがある。
555個で167桁までをすべて網羅したから、このうち４つの組み合わせ（(1,2,4,8)
(1,2,4,9)）が 555-167x3=54　桁分ある。
４はこのこの数と一致するので　５４回あらわれる。

追加問題

同じような考え方では　１が１６７回という以外は求まりませんです。
どうも簡単には行きそうにないので、とりあえずエクセルでバア－っと計算して数え
ておきました。
　　１：１６７　
　　２：９９
　　３：６８
　　４：５４
　　５：４５
　　６：３７
　　７：３１
　　８：２９
　　９：２５

NO4「三角定規」12/09 13時08分受信更新12/24

お久しぶりでございます。毎回解いてはいるのですが…。さて，今回の問題［最高位の数字］についてです。

以下は，解答ではなく，感想です。

数 N の常用対数を logN として，［logN］＋1 が N の桁数を，10^{logN} ( {logN} は小数部) が仮数を表します。

ここで，

　　log2=0.301029…

　　log3=0.477121…

等だから，例えば

　　0.301029…＜{logN}＜0.477121…

ならば，N の最高位の数は 2 となります。

そこで，本問です。

N＝2^n，logN＝nlog2＝(0.301029…)n　を考えるわけですが，log2 は無理数で 301029… には循環性がありません。
よって，nlog2 の小数部や 2^n の最高位数と n との間に関係性があるとは思えません。

そこで，Excel で力ずくの計算をしてみました。添付した “2^n.xls” がそれです。

これによれば，1≦n≦555 で，2^n の最高位が 4 となるのは 54 回で，1～9 の回数も表の通りです。
最高位数 k が大きいほど回数 m(k) が小さくなるのは，幅 log(k＋1)－logk が小さくなるためでしょう。いくらかの相関性も伺えます。■

	n		nlog2		nlog2 の小数部		桁数		2^n		最高位	最高位 k	m(k)
	1		0.301029996		0.301029996		1		2		2	1	167
	2		0.602059991		0.602059991		1		4		4	2	99	log2＝	0.301029996
	3		0.903089987		0.903089987		1		8		8	3	68	log3＝	0.477121255
	4		1.204119983		0.204119983		2		16		1	4	54	log4＝	0.602059991
	5		1.505149978		0.505149978		2		32		3	5	45	log5＝	0.698970004
	6		1.806179974		0.806179974		2		64		6	6	37	log6＝	0.77815125
	7		2.10720997		0.10720997		3		128		1	7	31	log7＝	0.84509804
	8		2.408239965		0.408239965		3		256		2	8	30	log8＝	0.903089987
	9		2.709269961		0.709269961		3		512		5	9	24	log9＝	0.954242509
	10		3.010299957		0.010299957		4		1024		1	計	555
545		164.0613476		0.061347637		165		1.152E+164		1
546		164.3623776		0.362377633		165		2.303E+164		2
547		164.6634076		0.663407628		165		4.607E+164		4
548		164.9644376		0.964437624		165		9.214E+164		9
549		165.2654676		0.26546762		166		1.843E+165		1
550		165.5664976		0.566497615		166		3.686E+165		3
551		165.8675276		0.867527611		166		7.371E+165		7
552		166.1685576		0.168557607		167		1.474E+166		1
553		166.4695876		0.469587602		167		2.948E+166		2
554		166.7706176		0.770617598		167		5.897E+166		5
555		167.0716476		0.071647594		168		1.179E+167		1

＜水の流れ：受信した添付ファイルは大変長いもので、一部勝手ながら割愛させて頂きました＞

NO5「kiyo」　　12/10 10時49分受信更新12/24

いつもお世話になっています。kiyoです。
問題の解答ではありませんが、規則性があるようなので報告します。

十進ベ－シック
REM Benford's law
REM a(n) = [2^n / 10^([log_10(2^n)])] = [2^n / 10^([n*log_10(2)])]
FOR N=0 TO 100
   LET X=2^N
   LET Y$=STR$(X)
   PRINT VAL(LEFT$(Y$,1));",";
NEXT N
PRINT
FOR N=0 TO 100
   PRINT INT(2^N/10^INT(N*LOG10(2)));",";
NEXT N
PRINT
END

1, 2, 4, 8, 1, 3, 6, 1, 2, 5,
1, 2, 4, 8, 1, 3, 6, 1, 2, 5,
1, 2, 4, 8, 1, 3, 6, 1, 2, 5,
1, 2, 4, 8, 1, 3, 6, 1, 2, 5,
1, 2, 4, 8, 1, 3, 7, 1, 2, 5,
1, 2, 4, 9, 1, 3, 7, 1, 2, 5,
1, 2, 4, 9, 1, 3, 7, 1, 2, 5,
1, 2, 4, 9, 1, 3, 7, 1, 3, 6,
1, 2, 4, 9, 1, 3, 7, 1, 3, 6,
1, 2, 4, 9, 1, 3 (list; graph; listen)

COMMENT Statistically, sequence obeys Benford's law,
           i.e. digit d occurs with probability log_10(1 + 1/d);
           thus 1 appears about 6.6 times more often than 9.
           Lekraj Beedassy (boodhiman(AT)yahoo.com), May 04 2005

LINKS J. Derbyshire, Lead Digit of 2 to the Power of N

FORMULA a(n) = [2^n / 10^([log_10(2^n)])] = [2^n / 10^([n*log_10(2)])]

参考

Benfordの法律

基盤10では、一流ディジットにBenford'sの法律によって次の配分がある:

一流ディジット確率
1 30.1%
2 17.6%
3 12.5%
4 9.7%
5 7.9%
6 6.7%
7 5.8%
8 5.1%
9 4.6%

「kiyo」　　12/10 19時15分受信更新12/24

いつもおせわになっています。kiyo(清川)です。　十進ベ－シック(１０００桁モ－ド)
1 167 30.1
2   99 17.8
3   68 12.3
4   54    9.7
5   45    8.1
6   37    6.7
7   31    5.6
8   30    5.4
9   24    4.3
------------
   555   100