■ディオファントス・モーデル・マチアセビッチ(その60)

【2】初等的整数論的アプローチ

  3n+1=2^m

は,modnあるいはmod3として,

  1=2^m

を得るが,m=0,n=0となり,これらはあまり有効ではない.

 そこで,mod2として

  3n+1=0

を得る.この場合,nは奇数になるから,mod4として

  m>1のとき,3n+1=0→nは4k+1となることが必要

  (n,m)=(5,4)では,5→16→8→4→2→1

  m=1のとき,3n+1=2→NG

  m=0のとき,3n+1=1→n=0

 mod8として

  m>2のとき,3n+1=0→nは8k+5となることが必要

  m=2のとき,3n+1=4→n=1

  m=1のとき,3n+1=2→NG

  m=0のとき,3n+1=1→n=0

 mod16として

  m>3のとき,3n+1=0→nは16k+5となることが必要

  m=3のとき,3n+1=8→NG

  m=2のとき,3n+1=4→n=1

  m=1のとき,3n+1=2→NG

  m=0のとき,3n+1=1→n=0

これより

 3n+1=2^m

を満たすための必要条件は,nが4k+1,8k+5,16k+5・・・型整数であることである.(n,m)=(5,4)はひとつの解であるが,他の解を探してみよう.

[1]3n+1=12k+4 (k=0は除く)

 k=1,n=5→16=2^4,m=4

 k=5,n=21→64=2^6,m=6

 k=21,n=85→256=2^8,m=8

 k=85,n=341→1024=2^10,m=10

 k=341,n=1365→4096=2^12,m=12

[2]3n+1=24k+16 (k=0は除く)

 k=2,n=21→64=2^6,m=6

 k=10,n=85→256=2^8,m=8

 k=42,n=341→1024=2^10,m=10

 k=170,n=1365→4096=2^12,m=12

 k=682,n=5461→16384=2^14,m=14

[3]3n+1=48k+16 (k=0は除く)

 k=1,n=21→64=2^6,m=6

 k=5,n=85→256=2^8,m=8

 k=21,n=341→1024=2^10,m=10

 k=85,n=1365→4096=2^12,m=12

 k=341,n=5461→16384=2^14,m=14

以上より,

  3n+1=2^m

の解が(n,m)=(5,4),(21,6),(85,8),(341,10),(1365,12),(5461,14),・・・となる.

 すなわち,m=2kのとき,

  3n+1=2^m=2^2k

  3n=2^2k−1=(2^2−1)(2^2k-2+2^2k-4+・・・+2^0)

  n=2^2k-2+2^2k-4+・・・+2^2+2^0=(2^2k−1)/3

 nは2進数表示で,1010・・・0101と表されることがわかる.

 52=101

 212=10101

 852=1010101

 3412=101010101

 13652=10101010101

 54612=1010101010101

===================================