証明課題の確認
以下レポートで証明したのですが、提出前に間違いないかご確認頂けますと幸いです。
予想X
--------------------------------------------------
任意の自然数は以下X,Yの操作を繰り返す事で最終的に1となる。
X 偶数なら2で割る
Y 奇数なら3倍して1を足す
(偶数:奇数に1加えた数の事
奇数:2以外の素数及びその積の事)
--------------------------------------------------
補題A
自然数nがn=2i(i=1,2,3,…)の時、2ⁿ−1は3の倍数である。
i=1の時は2⁴−1=3より正しい。
2²ⁱ−1=4ⁱ-1=3kと仮定すると
4ⁱ⁺¹-1=4×4ⁱ-1= 4×(3k+1)-1=3(4k)+3=3(4k+1)
より数学的帰納法より命題は正しい
----------------------------------------------------------
任意の自然数は素因数分解により、
2以外の素数pᵥとaᵢ∈{0,1,2,…,}に対して2ᵃ⁰3ᵃ¹5ᵃ²…pᵥ₋₁ᵃᵐ⁻¹pᵥᵃᵐと書ける。
すなわち、
全ての自然数はⒶ偶数積のみ、Ⓑ奇数積のみ、Ⓒ混合積の3つに分類される。
Ⓐは2ⁿだからXをn回繰り返す
ⒸはYを適当に繰り返せばⒷになる。
よって奇数積のみの場合に操作を程す事を考えればよい。
また、奇数について、Yを施した後は必ず偶数なのでXを施す事になり、施す操作は以下のようになる。
Y⇒Xⁱ¹⇒Y⇒Xⁱ²⇒Y⇒Xⁱ³⇒…(iⱼ=1,2,3,…)
(※Xⁱʲは2ⁱʲで割るという意味で、iⱼは該当の奇数に対して施せる操作Xの最大回数)
奇数p≠1にYを施した際について、3p+1=2ⁿを満たすpはp=(2ⁿ−1)/3より、
補題Aからn=2k(k=2,3,4,…)の時である。
従って、任意の奇数pに対してw回目のXの操作によりp=(2²ᵏ−1)/3 (k=2,3,4,…)
(p=5, 21 ,85 ,341 ,…)となる事が示されれば残りの操作はY⇒X²ᵏ⇒1に定まる。
写像fᵢⱼ:{2t−1|t=1,2,3,…}→{2t−1|t=1,2,3,…}
を値域が操作Y⇒Xⁱʲにより得られる奇数と定義する。
奇数r(=2t−1)(t=2,3,4,…)と iⱼ₁, iⱼ₂, iⱼ₃,…∈{1,2,3,…,}に対して
●fᵢⱼ₁(r)=q=(3r+1)/2ⁱʲ¹=と書く。
一般形は
fᵢⱼᵤ₊…₊ᵢⱼ₄₊ᵢⱼ₃₊ᵢⱼ₂₊ᵢⱼ₁(r)=
fᵢⱼᵤ(…(fᵢⱼ₄(fᵢⱼ₃(fᵢⱼ₂(fᵢⱼ₁(r))))
=[(3ᵘr+3ᵘ⁻¹)+3ᵘ⁻²×2ⁱʲ¹+3ᵘ⁻³×2ⁱʲ¹⁺ⁱʲ²+…+3×2ⁱʲ¹⁺ⁱʲ²…⁺ⁱʲᵘ⁻²+2ⁱʲ¹⁺ⁱʲ²⁺…⁺ⁱʲᵘ⁻¹]
/2ⁱʲ¹⁺ⁱʲ²⁺ⁱʲ³⁺…⁺ⁱʲᵘ
である。
この一般形について以下考察する。
★★★相異なる値である事★★★★
fᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)=fᵢⱼ₍ᵤ₊₁₎₊ᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)を満たすものについて考える。
fᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)=qに対して
fᵢⱼ₍ᵤ₊₁₎₊ᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)
=fᵢⱼ₍ᵤ₊₁₎(q)=(3q+1)/2ⁱʲ⁽ᵘ⁺¹⁾
=q
となるが、qは正の奇数であり、
3q+1=2ⁱʲ⁽ᵘ⁺¹⁾q
⇔
q=1/(2ⁱʲ⁽ᵘ⁺¹⁾−3)
ⁱᵢⱼ₍ᵤ₊₁₎>2ならば2ⁱʲ⁽ᵘ⁺¹⁾>3なのでⁱᵢⱼ₍ᵤ₊₁₎=2の時のq=1のみである。
次に複数繰り返し操作を施しても同じ値が出る事は無いことを数学的帰納法より証明する。
★★★★★★★★★★★★★★★★★
以下m−1≧2とする。
fᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)=fᵢⱼ₍ᵤ₊₍ₘ₋₁₎₎₊…₊ᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)(=fᵢ₍ᵤ₊₍ₘ₋₁₎₎₊…₊ᵢⱼ₍ᵤ₊₁₎(q))=qを満たすとした時、
fᵢⱼ₍ᵤ₊₍ₘ₋₁₎₎₊…₊ᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)=fᵢ₍ᵤ₊₍ₘ₋₁₎₎₊…₊ᵢⱼ₍ᵤ₊₁₎(q)
={(3⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾q+3⁽ᵘ⁺⁽ᵐ⁻²⁾⁾)+3⁽ᵘ⁺⁽ᵐ⁻³⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾+3⁽ᵘ⁺⁽ᵐ⁻⁴⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾+…
+3×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻³⁾⁾+2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻²⁾⁾}
/2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾
であり、
qについて解くと、
q=
{3⁽ᵘ⁺⁽ᵐ⁻²⁾⁾+3⁽ᵘ⁺⁽ᵐ⁻³⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾+3⁽ᵘ⁺⁽ᵐ⁻⁴⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾+…
+3×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻³⁾⁾+2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻²⁾⁾}
/{2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾－3⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾}
である。
この時、
2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾>3⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾を満たす最小のiʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾=sについて、iʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾≧sならば
{3⁽ᵘ⁺⁽ᵐ⁻²⁾⁾+3⁽ᵘ⁺⁽ᵐ⁻³⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾+3⁽ᵘ⁺⁽ᵐ⁻⁴⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾+…
+3×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻³⁾⁾+2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻²⁾⁾}
＜{2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾－3⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾}
となると仮定する。[→本仮定]
簡単のため
A=3⁽ᵘ⁺⁽ᵐ⁻²⁾⁾+3⁽ᵘ⁺⁽ᵐ⁻³⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾+3⁽ᵘ⁺⁽ᵐ⁻⁴⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾+…+3×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻³⁾⁾
B=2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻²⁾⁾
C=2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾(※)
D=3⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾
とおく。
(※)
(C=2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻²⁾⁾⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾
=2ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾×Bである。)
つまり、
iʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾≧sならば
(A+B)<(C−D)
という仮定である。
★fᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)=fᵢⱼ₍ᵤ₊ₘ₎₊…₊ᵢⱼᵤ₊…₊ᵢⱼ₂₊ᵢⱼ₁(r)(=fᵢ₍ᵤ₊ₘ₎₊…₊ᵢⱼ₍ᵤ₊₁₎(q))=qを満たすものについて考える。
qについて解くと、
[(3⁽ᵘ⁺ᵐ⁾q+3⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾)+3⁽ᵘ⁺⁽ᵐ⁻²⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾+3⁽ᵘ⁺⁽ᵐ⁻³⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾+…
+3×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻²⁾⁾+2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾]
=2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾×q
⇔
q=
{(3⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾)+3⁽ᵘ⁺⁽ᵐ⁻²⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾+3⁽ᵘ⁺⁽ᵐ⁻³⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾+…
+3×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻²⁾⁾+2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾}
/(2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺ᵐ⁾－3⁽ᵘ⁺ᵐ⁾)
であり、
右辺=
{3×3⁽ᵘ⁺⁽ᵐ⁻²⁾⁾+3×3⁽ᵘ⁺⁽ᵐ⁻³⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾+3×3⁽ᵘ⁺⁽ᵐ⁻⁴⁾⁾×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾+…
+3×3×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻³⁾⁾+2ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾
×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻²⁾⁾}
/{2ⁱʲ⁽ᵘ⁺ᵐ⁾×2ⁱʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾－3×3⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾}
=(3A+2ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾×B)/(2ⁱʲ⁽ᵘ⁺ᵐ⁾×C−3×D)
が得られる。
本仮定から
iʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾≧sならば
C>Dなので
iʲ⁽ᵘ⁺ᵐ⁾≧2ならば2ⁱʲ⁽ᵘ⁺ᵐ⁾×C>3×Dである。
すなわちs+2=iʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾が
2ⁱʲ⁽ᵘ⁺ᵐ⁾×C>3×Dを満たす最小の数である。
いま、
iʲ⁽ᵘ⁺¹⁾⁺ⁱʲ⁽ᵘ⁺²⁾⁺…⁺iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾≧sかつiʲ⁽ᵘ⁺ᵐ⁾≧2において、本仮定から
(A+B)<(C−D)であり、
また、
2ⁱʲ⁽ᵘ⁺ᵐ⁾>3
2ⁱʲ⁽ᵘ⁺ᵐ⁾×C>3C
2ⁱʲ⁽ᵘ⁺ᵐ⁾×C>3D(-3D>-2ⁱʲ⁽ᵘ⁺ᵐ⁾×C)
である。
☆☆iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾=1の場合
3A+2ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾×B=3A+2Bなので
(3A+2B)<3(A+B)<3(C−D)<2ⁱʲ⁽ᵘ⁺ᵐ⁾C−3Dである。
☆☆以下iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾≧2の場合を考える。
●iʲ⁽ᵘ⁺ᵐ⁾≧sの場合
iʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾<sなので
(3A+2ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾×B)<2ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾(A+B)
<2ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾(C−D)<2ⁱʲ⁽ᵘ⁺⁽ᵐ⁻¹⁾⁾C−3D
<2ⁱʲ⁽ᵘ⁺ᵐ⁾C−3D
である。
●iʲ⁽ᵘ⁺ᵐ⁾<sの場合
↓続く
お礼
大変参考になりました。ありがとうございます。