Fussy's Diary

だんだんと湿度が上がってきて蒸し暑い日が続くようになりました。もうすぐ梅雨が始まりますね。

少し前ですが、「アルゴリズムのコーナー」を更新しました。今回も新規ではなく内容の見直しになります。

「算術符号化」
「EBCOTとMQ-Coder」

「EBCOTとMQ-Coder」はほぼ全てのサンプル・プログラムをページに載せたので、分量が多くなってしまいました。
次回は何にするか、少々悩んでます。新たなネタが一つあって現在まとめ中ですが、まだ理解不足のところが多々あり時間がかかりそうです。その間に過去の内容の見直しをするかもしれません。

さて、「数学問題bot」さんから拾った問題です。かなり悩みました ( 特に 2 番)。例によって合っている保証はありません。

-----

1) 3ⁿ = k³ + 1 をみたす正の整数の組 ( k, n ) を全て求めよ。
2) 3ⁿ = k² - 40 をみたす正の整数の組 ( k, n ) を全て求めよ。( 10 千葉 )

1)

k³ + 1 = ( k + 1 )³ - 3k( k + 1 ) より

3ⁿ + 3k( k + 1 ) = ( k + 1 )³

を満たす ( k, n ) の組を見つければいいことになります。n > 0 より

3・[ 3^n-1 + k( k + 1 ) ] = ( k + 1 )³

となるので k + 1 は 3 の倍数であり、k + 1 = 3m とすれば

3・[ 3^n-1 + 3m( 3m - 1 ) ] = ( 3m )³ = 27m³

となり、両辺を 3 で割って

3^n-1 + 3m( 3m - 1 ) = 9m³

となります。式を変形して

3^n-1 = 3m・[ 3m² - ( 3m - 1 ) ]

なので、右辺は 3 のみを素因数として持たねばなりません。

m = 1 のとき、(右辺) = 3 で、( k, n ) = ( 2, 2 ) が該当します。

m > 1 のとき、m は 3 のべき乗でなければなりませんが、そうすると

3m² - ( 3m - 1 ) = 3m( m - 1 ) + 1

は 3 の倍数になりません。

従って、( k, n ) = ( 2, 2 ) のみが該当することになります。

2)

k² = 3ⁿ + 40 として n = 1 の場合から実際に計算してみます。

n	k2	k
1	43	-
2	49	7
3	67	-
4	121	11
5	283	-
6	769	-
7	2227	-
8	6601	-

まず、n が奇数の時に着目すると、k² の下一桁めは 3 か 7 のいずれかになります。n = 1 のとき 3ⁿ = 3 であり、40 を加えても下一桁は変わりません。n = 3 では 9 を掛けることになり 3ⁿ = 27 ≡ 7 ( mod 10 ) です。n = 5 ではまた 9 を掛けることになるので 3ⁿ = 243 ≡ 3 ( mod 10 ) で、以下 3 と 7 を繰り返すことになります。ところで、二乗数の下一桁は、計算すればすぐわかるように 1, 4, 5, 6, 9 のいずれかしか現れません。従って、n が奇数のときは二乗数になり得ないことになります。
n が偶数のとき、n = 4 までは k が得られていますが、それ以降は新たな k は見つかっていません。n が偶数ならば、3ⁿ は必ず二乗数になります。例えば n = 6 のとき、3ⁿ = 27² であり、これにある数を加えて二乗数にしたいとき、次の数は 28² なので、その差は

28² - 27² = ( 28 + 27 )( 28 - 27 ) = 55 > 40

となります。従って、40 を加えても二乗数にすることができません。n = 6 以降の全てに対してそうなので、これ以上は見つからないことを意味します。

よって、得られる組は ( k, n ) = ( 7, 2 ), ( 11, 4 ) の二つです。