どうも、lip_of_cygnusです。TSG Advent Calendar 2015の16日目の記事です。
小学生の頃は自由帳に2の累乗ばっかりだけ書いているような子供でした。
今日の話題は高校生の時、担任の先生からもらった問題についてです。
本記事ではこの問題を２つの方法で解きたいと思います。
方法１：上から攻める
$\log_2 10$が無理数であることを用います。
無理数であることの証明は簡単です。
$\log_2 10$が有理数であると仮定すると、
$2^\frac{m}{n}=10$となります。両辺をn乗すると、
$2^m=10^n$
2と5は互いに素なので、右辺は5の倍数になるのにもかかわらず、左辺は5の倍数ではありません。
矛盾しているので、この仮定は不合理であるため$\log_2 10$は無理数です。さてここでクロネッカーの稠密定理を用いたいと思います。
クロネッカーの稠密定理：
任意の無理数xと$0 \leq a < b \leq 1$を満たす任意の実数a,bに対して$a \leq \{nx\} \leq b$を満たす自然数nが存在する。
詳細については、こちらをご覧ください。
クロネッカーの稠密定理とその証明 | 高校数学の美しい物語
2の累乗に現れてほしい自然数をxと置きます。クロネッカーの稠密定理より、
\[
m-\log_2 (x+1-ε)\leq n*\log_2 10\leq m-\log_2 x\\
(mは\log_2 xより大きい整数,0<ε<1とします)\\
m-\log_2 (x+1)< n* \log_2 10 \leq m-\log_2 x\\
\]
各辺を2^(各辺)という感じにすると
\[
\frac{2^m}{x+1}<10^n \leq \frac{2^m}{x}\\
\frac{2^m}{x+1}<10^nより、\\
2^m<(x+1)*10^n\\
10^n \leq \frac{2^m}{x}より、\\
x*10^n \leq 2^m\\
\]
\[x*10^n \leq 2^m<(x+1)*10^n\\
\]
ゆえに、任意の自然数xが2の累乗に現れることが示されました。
方法２：下から攻める
2の累乗に現れてほしい自然数をxと置きます。
まず、xの後ろの方に数字を付け足します。
xの桁数をNとした時に、M桁足してN+M桁が$2^{M+N}$乗の倍数となるようなものを探します。
M=Nとすれば、x'の候補となる数は$10^N$個存在するのでその中に必ず$2^{M+N}=4^N$の倍数となるものは存在します。そしてこのようなx'は必ずある2の累乗中に存在するのです。証明にうつる前に補題を示します。
補題: 数列 $2^0,2^1,...,2^{5^t-1}$を考える。これを$5^t$で割った余りは全て異なる。
背理法で示す。余りが同じになる組があると仮定し、これを$2^i,2^{i+j}$(jは$j<5*t-1$を満たす自然数)とおく。
$2^{i+j}-2^i=2^i*(2^j-1)$2と5は互いに素であるので、$2^j-1$は$5^t$の倍数になります。(すみませんこのあとの証明思いつきません)
証明:上の桁がk(ない場合は0)で、下M+N桁がx'であるような自然数Pを考えます。
P=k*10^(M+N)+x'=2^(M+N)*(k*5^(M+N)+x'')
この時、x''は必ず5^(M+N)の倍数ではない自然数になります。(x'が自然数でM+N桁であることから分かる)ところで、t=M+Nとすれば補題より(k*5^(M+N)+x'')は2の累乗で表すことができます。従ってPも2の累乗で表すことができます。ゆえに、任意の自然数xが2の累乗に現れることが示されました。
せっかくなんで、両方の方法で自然数xが含まれる2の累乗を出力するプログラムを作りました。言語はPythonでpython log2.py 数字 という感じで入力すると結果が返ってきます。
例えば今日の日付にちなんで1216を入力すると
$1442$ $121689679549848296476284539719833956128172746808983983951831652023347365468864269429292576963439508278182027446718540810569381644337220853815156314657613612239712834757924740882197032736054344801343165356558510233936904806426545855737390911634598080775602523511373106777607060088046178460822014203870855117130108554646318067801134685013852825258691387386426550771312213642678910868232892059330844780618615710006156570567711150890287104$
$424$ $43322963970637732180912721627235682866194329302747133987038743447103457934462900359999600095377180907771737671271930809827721216$
と出力されます。
小学生の頃は自由帳に2の累乗ばっかりだけ書いているような子供でした。
今日の話題は高校生の時、担任の先生からもらった問題についてです。
「すべての自然数は2の累乗に現れる」
本記事ではこの問題を２つの方法で解きたいと思います。
方法１：上から攻める
$\log_2 10$が無理数であることを用います。
無理数であることの証明は簡単です。
$\log_2 10$が有理数であると仮定すると、
$2^\frac{m}{n}=10$となります。両辺をn乗すると、
$2^m=10^n$
2と5は互いに素なので、右辺は5の倍数になるのにもかかわらず、左辺は5の倍数ではありません。
矛盾しているので、この仮定は不合理であるため$\log_2 10$は無理数です。さてここでクロネッカーの稠密定理を用いたいと思います。
クロネッカーの稠密定理：
任意の無理数xと$0 \leq a < b \leq 1$を満たす任意の実数a,bに対して$a \leq \{nx\} \leq b$を満たす自然数nが存在する。
詳細については、こちらをご覧ください。
クロネッカーの稠密定理とその証明 | 高校数学の美しい物語
2の累乗に現れてほしい自然数をxと置きます。クロネッカーの稠密定理より、
\[
m-\log_2 (x+1-ε)\leq n*\log_2 10\leq m-\log_2 x\\
(mは\log_2 xより大きい整数,0<ε<1とします)\\
m-\log_2 (x+1)< n* \log_2 10 \leq m-\log_2 x\\
\]
各辺を2^(各辺)という感じにすると
\[
\frac{2^m}{x+1}<10^n \leq \frac{2^m}{x}\\
\frac{2^m}{x+1}<10^nより、\\
2^m<(x+1)*10^n\\
10^n \leq \frac{2^m}{x}より、\\
x*10^n \leq 2^m\\
\]
\[x*10^n \leq 2^m<(x+1)*10^n\\
\]
ゆえに、任意の自然数xが2の累乗に現れることが示されました。
方法２：下から攻める
2の累乗に現れてほしい自然数をxと置きます。
まず、xの後ろの方に数字を付け足します。
xの桁数をNとした時に、M桁足してN+M桁が$2^{M+N}$乗の倍数となるようなものを探します。
M=Nとすれば、x'の候補となる数は$10^N$個存在するのでその中に必ず$2^{M+N}=4^N$の倍数となるものは存在します。そしてこのようなx'は必ずある2の累乗中に存在するのです。証明にうつる前に補題を示します。
補題: 数列 $2^0,2^1,...,2^{5^t-1}$を考える。これを$5^t$で割った余りは全て異なる。
背理法で示す。余りが同じになる組があると仮定し、これを$2^i,2^{i+j}$(jは$j<5*t-1$を満たす自然数)とおく。
$2^{i+j}-2^i=2^i*(2^j-1)$2と5は互いに素であるので、$2^j-1$は$5^t$の倍数になります。(すみませんこのあとの証明思いつきません)
証明:上の桁がk(ない場合は0)で、下M+N桁がx'であるような自然数Pを考えます。
P=k*10^(M+N)+x'=2^(M+N)*(k*5^(M+N)+x'')
この時、x''は必ず5^(M+N)の倍数ではない自然数になります。(x'が自然数でM+N桁であることから分かる)ところで、t=M+Nとすれば補題より(k*5^(M+N)+x'')は2の累乗で表すことができます。従ってPも2の累乗で表すことができます。ゆえに、任意の自然数xが2の累乗に現れることが示されました。
せっかくなんで、両方の方法で自然数xが含まれる2の累乗を出力するプログラムを作りました。言語はPythonでpython log2.py 数字 という感じで入力すると結果が返ってきます。
例えば今日の日付にちなんで1216を入力すると
$1442$ $121689679549848296476284539719833956128172746808983983951831652023347365468864269429292576963439508278182027446718540810569381644337220853815156314657613612239712834757924740882197032736054344801343165356558510233936904806426545855737390911634598080775602523511373106777607060088046178460822014203870855117130108554646318067801134685013852825258691387386426550771312213642678910868232892059330844780618615710006156570567711150890287104$
$424$ $43322963970637732180912721627235682866194329302747133987038743447103457934462900359999600095377180907771737671271930809827721216$
と出力されます。
