どちゃ楽 Q.125 「f(5^p)=2^q」
Q.125 ☆10 [BotBot07080546 様]
10進法で末尾が0でない正の整数 $n$ の末尾を首位へと移し,新しい整数 $f(n)$ を作る。たとえば,$f(334)=433, f(893)=389$ である。$f(5^{p})=2^{q}$ を満たす3以上の整数の組 $(p,q)$ を求めよ。
この問題のツイート: https://twitter.com/so_easy_math/status/936118615224414208?s=09
解答
$5^{p}, 2^{q}$ の10進法における桁数が等しいことが必要であり,両者が $k$ 桁であるとする。$5^{p}\ge 125$ より $k\ge 3$ である。
$5^{p}$ の末尾は$5$であるから,$5^{p}$ の末尾を除いた $k - 1$ 桁の整数は $\dfrac{5^{p}-5}{10}=\dfrac{5^{p-1}-1}{2}$ と表される。
$f(5^{p})$ も$k$桁の整数であり,首位が5であるから
$f(5^{p})=5\cdot 10^{k - 1}+\dfrac{5^{p-1}-1}{2}$
となる。ここから,
$2^{q}=f(5^{p})\ge \dfrac{5^{p-1}}{2}>2^{2p-3} $
として $q>2p-3$ より$\dfrac{q+1}{2}>p-1$ を得る。（後の方で使います）
整数$N$に対して,$N$が素数$P$で割り切れる最大の回数を $v_{P}(N)$ とおいて,整数 $\dfrac{5^{p-1}-1}{2}=M $ について,次の 補題 を示す。
補題 $v_{2}(M)= v_{2}(p-1) + 1$ である。
証明. ある正の奇数$t$がただ一つ存在して $p-1=2^{v_{2}(p-1)}t $ と表される。このとき,
$M=\dfrac{5^{t}-1}{2}\displaystyle\prod_{i=0}^{v_{2}(p-1) -1} (5^{2^{i}t}+1)$
と因数分解される。ただし,$ p $ が偶数,すなわち $v_{2}(p-1) = 0 $ である場合は $\displaystyle\prod_{i=0}^{v_{2}(p-1) -1} (5^{(2^{i}t)}+1) =1 $ であるものとする。
このとき,$t$が奇数であることから
$5^{t}-1\equiv 4 (\mbox{mod} 8)$, $5^{(2^{i}t)}+1\equiv 2 (\mbox{mod} 4)$ $(i=0,1,\cdots v_{2}(p-1) -1)$ となるため,
$\displaystyle\prod_{i=0}^{v_{2}(p-1) -1} (5^{(2^{i}t)}+1)$ は 2で$v_{2}(p-1)$ 回(これは$p$が偶数のときも成立する), $\dfrac{5^{t}-1}{2}$ は 2で1回まで割れるから,$M$は2で最大 $v_{2}(p-1) +1$ 回まで割れる。
すなわち,$v_{2}(M)= v_{2}(p-1) + 1$ である。(証明終)
( i ) $k - 1 \neq v_{2}(M)$ であるとき…
$v_{2}(f(5^{p})) = \min\{k - 1, v_{2}(M)\}$ であり,これが $v_{2}(2^{q}) =q $ に等しい。
$f(5^{p})>5\cdot 10^{k - 1}>2^{(k - 1)}$ であるから,
$2^{k - 1} < 2^{q}$ より $k - 1<q=\min\{k - 1, v_{2}(M)\}$
従って $k - 1 > v_{2}(M)$ であることが必要で,補題 より $q = v_{2}(M)=v_{2}(p-1) +1$
このとき,$\dfrac{q+1}{2}>p-1$ を用いて $q =v_{2}(p-1) +1\le (p-1)+1 < \dfrac{q+1}{2}+1 $ より
$0<1-\dfrac{q-1}{2} \Leftrightarrow q<3$ となり不適。
( ii ) $k - 1 = v_{2}(M)$ であるとき…
補題から $k=v_{2}(p-1)+2$ である。
右辺 $v_{2}(p-1)+2$ について,次のような評価ができる。
$ v_{2}(p-1) + 2 \le v_{2}(p-1) + 2 + \log_{2}(t) < \log_{2}(p-1) + 2$
左辺 $k$ について,$5^{p}$は $k$ 桁で,$5^{p} < 10^{k}$ が成り立ち,10を底に対数を取って $\dfrac{p}{2}<p\log_{10}{5} < k $ という評価ができる。これらから,$p$について
$ 2^{\frac{p}{2}}<4(p-1) \Leftrightarrow 2^{p}<16(p-1)^{2} $
が成り立つことが必要となる。また,$k\ge 3$ より $v_{2}(p-1) \ge 1$ で, $p$は奇数であることが必要となる。$p$についてのこの不等式を満たし,かつ3以上の奇数であるようなものは$3,5,7,9$ に限られる。(11以上は数学的帰納法で$2^{p}$が上回ることを示す(省略))
このうち,$p=7,9$では $k=v_{2}(p-1)+2$ から それぞれ$k=3,5$ となるが,いずれも$5^{p}$の桁数($k$)に一致しないので不適。$p=5$ のとき,$2^{12}<f(5^{5})=5312 <2^{13}$ で不適。
$p=3$のとき,$f(5^{3})=512$ で$q=9$だからよい。
以上より $(p,q)=(3,9)$.
コメント
もう少し効率よく不等式評価できたような気がしますが、ひとまずこれを解答とします。整数問題ではある素数で割り切れる最大の回数に注目することがよくあります。特に数オリではそのような問題が人気で,LTEの補題(https://twitter.com/so_easy_math/status/935137196599787521) が使われることもあります。この問題の場合は2に注目し,割り切れる回数を評価し,更に不等式により$p,q$の条件を絞っていくという如何にも数オリらしい難問ですね。(数オリの問題でもこのような「割り切れる回数の評価」→「不等式で絞る」という流れの問題は結構あります) 補題は数学的帰納法で示すことも可能で,京大の問題にこの補題の類題もあります。
