Fussy's Diary

四月というのに、また急に寒くなりました。

先週から桜が満開です。朝の出勤時に川沿いの桜並木を通るので、いい目の保養になります。夜になると控えめにライトアップされた夜桜を見ることもできるので、遠出しなくても桜を楽しめるというのはいい環境に住んでいるなと感じます。
「アルゴリズムのコーナー」の次の内容がだいたい固まってきて、現在作成中です。しかし、まだ時間は掛かりそうです。今年に入ってからの更新頻度はあまりよくない状況が続いています。今は内容を理解しながら作成することが多いので、どうしても時間が掛かってしまいます。それでも気力の続く限りは継続しますけどね。

で、また現実逃避で「数学問題 bot」から一部だけ解いてみました。正解しているという保証は相変わらずありません。

■ 0 でない自然数の最右端の数字を、最左端に移動する操作を考える。

(i) この操作によってもとの数の 2 倍になる最小の自然数を求めよ
(ii) k = 3, ... , 9 に対して、この操作で k 倍になる最小の自然数を求めよ。

とりあえず (i) だけ解いています。おそらくもっと簡単な解法があると思いますが、もし見つかったらまた公開します。

(解法)

元の数を 10M + N とします。N が最右端の数で、M は残りの数です。N を最左端に移動すると、元の数の桁数が K ならばその数は 10^K x N + M になります。これが元の数の 2 倍なので

2( 10M + N ) = 10^K x N + M より

( 10^K - 2 )N = 19M

が成り立ちます。但し、N は一桁の数であること、また M は K 桁 ( 10^K-1 のオーダー ) の数であることが制約事項となります。

N < 10 なので、N は 19 では割りきれません。したがって、10^K - 2 は 19 で割り切れる必要があり、10^K を 19 で割った余りは 2 となります。K を 1 から順に増やしていくと

1 : 10 / 19 = 0 ... 10
2 : 10² / 19 = 5 ... 5
3 : 5 x 10 / 19 = 2 ... 12
4 : 12 x 10 / 19 = 6 ... 6
5 : 6 x 10 / 19 = 3 ... 3
6 : 3 x 10 / 19 = 1 ... 11
7 : 11 x 10 / 19 = 5 ... 15
8 : 15 x 10 / 19 = 7 ... 17
9 : 17 x 10 / 19 = 8 ... 18
10 : 18 x 10 / 19 = 9 ... 9
11 : 9 x 10 / 19 = 4 ... 14
12 : 14 x 10 / 19 = 7 ... 7
13 : 7 x 10 / 19 = 3 ... 13
14 : 13 x 10 / 19 = 6 ... 16
15 : 16 x 10 / 19 = 8 ... 8
16 : 8 x 10 / 19 = 4 ... 4
17 : 4 x 10 / 19 = 2 ... 2

K = 17 のときに剰余が 2 になりました。但し、A x B の剰余が A の剰余と B との積から求められることを利用しています。

この結果から、10¹⁷ - 2 は 19 で割り切ることができて、その商はすでに上の結果から 5,263,157,894,736,842 となることがわかります (上の結果の商を順番に並べるだけです)。しかし、これは 10¹⁵ のオーダーなので、10¹⁶ のオーダーにするために N = 2 として M = 10,526,315,789,473,684 とします。

したがって、求める自然数は 105,263,157,894,736,842 となります。

この方法の場合、k = 4 のときは

( 10^K - 4 )N = 39M

なので、N が 3 の倍数のときは 10^K - 4 は 13 で割り切ることができればよいことになり少々面倒になります。求めた数を見ると、ある位の数の二倍の一桁目が次の位の数になるので、これを利用すればもっと簡単な解法が見つかるのかもしれません ( それより前に正解している保証もないです )。