整数問題bot②　解答集
整数問題bot②　解答集

けんけん氏の自作問題　bot主による別解

n!=2^a+2^{a+1}+ \cdot \cdot \cdot +2^b\,(a<b)を満たす正の整数の組(a,b,n)をすべて求めよ.
(けんけん氏　作)



[解答]

以下,正の整数a,bに対して,aがbを割り切ることをa \mid b,
aがbを割り切らないことをa \nmid bと表す.

まず,次の2つの補題を示す.
補題１
任意の0以上の整数m,k(3 \nmid k)に対して,
3^{m+2} \nmid 2^{3^mk}-1
補題２
任意の14以上の整数nに対して,
n!<2^{2^{\frac{n-3}{2}}}



補題１の証明
mに関する帰納法で示す.
m=0のとき,
3 \nmid k,2^6-1 \equiv 0 \,\pmod{6}より,
k \equiv 1,2,4,5 \,\pmod{6}のときそれぞれ
2^k-1 \equiv 1,3,6,4\,\pmod{9}なので,
3^2 \nmid 2^k-1となって,よい.
m=sのとき成り立つと仮定する.
m=s+1のとき,
2^{3^{s+1}k}-1=(2^{3^sk}-1)\{(2^{3^sk})^2+2^{3^sk}+1\}・・・(☆)
簡単のために,r=2^{3^sk}とおく.
3 \nmid rよりr \equiv 1,2\,\pmod{3}である.
r \equiv 1\,\pmod{3}のとき,
r=3r^,+1(r^,は整数)とおくと,
r^2+r+1 \equiv (3r^,+1)^2+(3r^,+1)+1 \equiv 3\,\pmod{9}より
9 \nmid r^2+r+1
r \equiv 2\,\pmod{3}のとき,
r^2+r+1 \equiv 1 \,\pmod{3}より
3 \nmid r^2+r+1ゆえに9 \nmid r^2+r+1
また,帰納法の仮定より
3^{s+2} \nmid 2^{3^sk}-1なので,(☆)より
3^{(s+1)+2} \nmid 2^{3^{s+1}k}-1
よってm=s+1のときも成り立つ.
以上より示された.



補題２の証明
nに関する帰納法で示す.
n=14のとき,
14!<2 \cdot 4^2 \cdot 8^4 \cdot16^6=2^{41}であり,
1681=41^2=2^{11}=2048より
14!<2^{2^{\frac{11}{2}}}なので,よい.
n=15のとき,
15!<2 \cdot 4^2 \cdot 8^4 \cdot16^7=2^{45}<2^{2^6}なので,よい.
k \geqq 14とし,n=kのとき成り立つと仮定する.
n=k+2のとき,k(k-1)(k-2)-(k+1)(k+2)=k\{(k-2)^2-5\}-2>0より
(k+1)(k+2)<k(k-1)(k-2)<k!なので,帰納法の仮定より,
(k+2)!=k! \cdot (k+1)(k+2)<(k!)^2<(2^{2^{\frac{k-3}{2}}})^2=2^{2^{\frac{(k+2)-3}{2}}}
よってn=k+2のときも成り立つ.
以上より示された.

さて,本題に移る.
c=b-a+1とおくと,与式は
n!=2^a(2^c-1)
a<bよりc \geqq 2である.
n \geqq 14のとき,
1以上n以下の3の倍数の個数をtとすると,
\frac{n-2}{3} \leqq t・・・①が成り立つ.
また,n \geqq 14と9=3^2より
3^{t+1} \mid n!・・・②が成り立つ.
ここで,0以上の整数m,k(3 \nmid k)を用いてc=3^mkと表すと,
補題１より3^{m+2} \nmid 2^c-1
これと3 \nmid 2^aより3^{m+2} \nmid n!・・・③
②,③よりt+1<m+2これと①より
\frac{n-5}{3} \leqq m・・・④
また,3 \mid n!より3 \mid 2^c-1であり
,2^c-1 \equiv (-1)^c-1 \,\pmod{3}なので
2 \mid cこれと3^m \mid cより2 \cdot 3^m \mid c
よって2 \cdot 3^m \leqq c
これと④より
2^{2 \cdot 3^{\frac{n-5}{3}}} \leqq 2^{2 \cdot 3^m} \leqq 2^c=2(2^c-\frac{1}{2} \csor 2^c) \leqq 2^a(2^c-1)=n!
また,補題２よりn!<2^{2^{\frac{n-3}{2}}}なので,
2^{2 \cdot 3^{\frac{n-5}{3}}}<2^{2^{\frac{n-3}{2}}}
よって{2 \cdot 3^{\frac{n-5}{3}}}<{2^{\frac{n-3}{2}}}より3^{\frac{n-5}{3}}}<{2^{\frac{n-5}{2}}}
両辺を6乗して9^{n-5}<8^{n-5}
これはn \geqq 14において不成立.
n \leqq 13のとき,順に調べることで,
(a,c,n)=(1,2,3),(3,2,4),(3,4,5)
すなわち(a,b,n)=(1,2,3),(3,4,4),(3,6,5)を得る.
これが求める組である.




-
「けんけん氏の自作問題　bot主による別解」をウィキ内検索
最終更新：2015年03月19日 06:33