コラッツ木のノード番号を16進表示してわかったこと

コラッツ木をゼルコバの木にインポート→描画がかなり容易にできるようになってきた.コラッツ木のダンプ出力は巨大数の羅列であり,これを眺め回してもほとんど何もつかめないが,系図木として画面上に表示できると,かなりのことがわかってくる.特に,ノード番号を16進表示してやると,これまで見えていなかったことが鮮明に見えてくる.かなり重要なポイントなので多少回り道にはなるが,追求してみたい.

一つ断定的に言えることとして,「非長子ノードの最右桁はつねに5ないしDである」という点がある.逆に言えば「もし,16進表示のノード番号の最右桁が5でもDでもないとすれば,そのノードは長子ノードである」と言える.もう少し端的に表現すれば,「2進表示の最右2ビットが11ならば長子ノード,01ならば非長子ノードである」と判定できる.

長子ノードNの2進表示をb…bとするとき,左隣の兄弟ノードはb…b01,その左はb…b0101のようになるから,長子ノードNの兄弟ノードは,b…b{01}*のように表現することができる.従って,長子ノードNの親ノードのビット列はb…bとはほとんど類似性を持たないが,すべての兄弟に共通するビット列として,これを親ノードPから引き継いだDNAのようなものとみなしてもよい.つまり,すべての奇数ノードはこのDNA配列によって特徴付けられると言ってよいだろう.

DNAというより,Y染色体と呼んだ方が当たっているかもしれない.この意味で奇数ノードは水平方向にはハプログループをなしているとも言えるが,垂直方向ではある意味で「暗号化」されてしまうため,追跡は困難であるように見える.奇数ノードのY染色体はビット列の上位部分に現れるが,観察した限りでは下位ビットでも似たようなコードが高い頻度で出現することが確認されている.この理由について知りたい.

3倍数ノードがコラッツ木上でどのように分布しているか?という点にも興味がある.少なくとも兄弟枠内では3倍数は3つ置きに出現することが確認されているが,兄弟枠外ないし,血統木全体を見たときにどうなっているかを知りたい.これがわかるとノードの値を計算するのもかなり容易なものになる可能性がある.少なくとも3倍数の検出には役立つかもしれない…長子ノードとその次のノードをチェックすれば3倍数がどの位置に出現するかは確定できるので,実際には,3倍数の検出と言ってもそれほどのコストが掛かっている訳ではないが…

▲一覧画面上で行クリックすると画面全体が更新・描画される.

▲CollatzTree 1-6-4 511.zelを少し操作したあと,クローズしようとしてフェーズ遷移エラーが起きた.

上位ビットの共通部分とは,Y染色体のDNAであると言えるとして,下位ビットの共通部分というのがどういう性質のものか?少し調べてみよう.511点のコラッツ木で16進4桁以上の下位共通部を持つノードを拾い出してみよう.以下では16進数を右から左に表記している.つまり,最下位ビットが最上位に表示されるような形式だ.たとえば,3A2B1CならC1B2A3と表示される.

  1. 1748 x2
  2. 1790 x2
  3. 17C5 x5,17C52 x4
  4. 17CB4  x3
  5. 17CE5  x3,17CE52 x2
  6. 1B79    x2
  7. 1F21    x2
  8. 36F2    x2
  9. 3E21    x3
  10. 3E52    x3
  11. 3E80    x2
  12. 3E8DB x3
  13. 5170    x2
  14. 5174    x4,57148 x2
  15. 51790  x2
  16. 51C5    x5,51C52 x4
  17. 517CB  x4,517CB4 x3
  18. 517CE5 x3,517CE52 x2
  19. 51B7    x3,51B79 x2
  20. 51F2    x4,51F21 x2
  21. 5324 x2
  22. 536F2  x3
  23. 53E0 x2
  24. 53E2 x5,53E21 x3
  25. 53E5 x4,53E52 x3
  26. 53E8 x7,53E80 x2,53E8DB x3
  27. 5511 x2
  28. 5514 x2
  29. 5517 x26,55170 x2,55174 x4,551748 x2,55179 x4,551790 x2,5517C x13,5517C5 x5,5517C52 x4,5517CB x4,5517CB4 x3,5517CE5 x3,5517CE52 x2
  30. 551B7 x3,551B79 x2
  31. 551F2 x4,551F21 x2
  32. 5532 x4,55324 x2
  33. 5536F2 x3
  34. 5538 x2
  35. 553E x21,553E0 x2,553E2 x5,553E21 x3,553E52 x3,553E8 x7,553E80 x2,553E8DB x3,553E8DB4 x2
  36. 5548 x2
  37. 5550 x2
  38. 5554 x4,55548 x2
  39. 555C x34,555C1 x20,555C11 x3,555C14 x2,555C17 x6,555C179 x4,555C1790 x2,555C1B7 x3,555C1B79 x2,555C1F2 x3,555C1F21 x2,555C5 x5,555C52 x4,555C524 x2,555C9 x2,555CB x4,555CB4 x3,555CE5 x3,555CE52 x2
  40. 5579 x3
  41. 55B4 x4,55B48 x2
  42. 55C1 x20,55C11 x3,55C14 x2,55C17 x6,55C179 x4,55C1790 x2,55C1B7 x3,55C1B79 x2,55C1F2 x4,55C1F21 x2
  43. 55C5 x5,55C52 x4,55C524 x2
  44. 55C9 x2
  45. 55CB x4,55CB4 x3
  46. 55CE5 x3,55CE52 x2
  47. 55D0 x2
  48. 55D2 x5,55D21 x3
  49. 55D5 x4,55D52 x3
  50. 55D8 x28,55D80 x2,55D83 x12,55D832 x4,55D836 x3,55D838 x2,55D879 x3,55D8B x5,55D8B4 x4,55D8B48 x2,55D8DB x3,55D8DB4 x2
  51. 5B48 x2
  52. 5C11 x3
  53. 5C14 x2
  54. 5C17 x6,5C179 x4,5C1790 x2
  55. 5C1B7 x3,5C1B79 x2
  56. 5C1F2 x4,5C1F21 x2
  57. 5C52 x4,5C524 x2
  58. 5CB4 x3
  59. 5CE5 x3,5CE52 x2
  60. 5D21 x3
  61. 5D52 x3
  62. 5D80 x2
  63. 5D83 x12,5D832 x4,5D8324 x2,5D836F2 x3,5D838 x2
  64. 5D87 x4,5D879 x3
  65. 5D8B x5,5D8B4 x4,5D8B48 x2
  66. 5D8DB x3,5D8DB4 x2
  67. D832 x3,D8324 x2
  68. D836F2 x3
  69. D838 x2
  70. D879 x2
  71. D8B4 x4,D8B48 x2
  72. D8DB x3,D8DB4 x2

こんなにあった!16進4桁ということは,2進で16ビットだから,同一ビット列となる確率は1/2^15としても1/32768=0.00003しかない.このような共通ビット列はなんらかのファミリーのようなものの標識であると見てよいのではないだろうか?よく見ると,このような標識の末尾(上記リストでは先頭)は圧倒的に5ないしDが多い.これは上記したように非長子ノードであるということを意味するので,頻繁に現れるのはそれほど奇異なことではない.しかし,同じ標識を持つ2つのノードが兄弟である可能性はほとんどないのではないか?試みに,最大ファミリーである「55D8」グループをグラフでカラー表示してみよう.

直接親子関係にあるノードが2組ある.9932117→6780325205と79531349→54293400917だ.16進で表記すると,978D55→194238D55,4BD8D55→CA4238D55のようになる.図面で見るとこれらのノード(赤で着色)はすべて例外なく6-正則木の6番目の枝にあるノードだ.

image

これから類推されることは,16進ないし,2進数表示された数値の下位ビット列はそのノードの枝番と強い関連性を持っていると言えるのではないだろうか?いや,これはそれほど驚くには当たらない.つまり,上記したようにすべての奇数ノードMのノード番号はビット列で表せば,b…b{01}*のように表記されるのだから,

M={長子ノードのビット列}+{枝番号を示すビット列}

という構成になる.8D55=100011-0101010101で確かに6番目の枝に位置することは明らかだ.{枝番号を示すビット列}の直上の2ビットが11でなくてはならないことも明らかだ.もしこれが,00ないし10なら長子ノードが偶数になってしまうし,もし,01なら6番目のノードではなく,7番目のノードということになる.

ノードの直上の親ノードを求めるにはどうすればよいか?任意のノードの長兄ノードを求めるのは簡単だ.右から2ビットづつ削除を11というビット列が現れるまで繰り返せばよい.今の場合は,100011B=23H=35に到達する.親ノードは35×3+1=106→53=35H=110101Bだ.バイナリで計算すれば,100011を左シフトして1000110+100011=1101001,これに1を加えて,1101010.末尾の0をすべて除去して,110101を得る.

親ノードNから長子ノードSを得る方法はあるだろうか?今の場合で言えば,110101から100011を得る方法だ.N*2^c=3S+1となるようなcを決定できればよいのだが,3で割り切れるかどうかを判定する効率的な方法がないので,このステップをバイナリ化するのは難しそうだ.c>0であり,おそらくc≦2であるような気がするのだが,違うだろうか?それよりも大きなcは見た記憶がない.いずれにしても,cは高々1ないし2と推定されるので,試行コストはそれほど高くつくものではない.

上記の説明には誤りがある.長子ノードを求めるのに,「右から2ビットづつ削除を11というビット列が現れるまで繰り返せばよい」としているが,これは長子ノードの定義に反している.というか,定義を満たしていない.長子ノードとは,これまでコラッツ数と呼んできたものであり,「奇数Nから1を減じて4で割った値が奇数とならないもの」と定義される.従って,コラッツ数とは「奇数Nから1を減じて4で割り切れないか,ないし商が偶数となるもの」である.

これをバイナリ計算として表現すれば,「末尾が101なら右に2ビットシフトする」となる.従って,コラッツ数の末尾はつねに11であるとは限らない.001という場合があり得る.100000010101という数を考えてみよう.右端の01をすべて取り除くと偶数になってしまうから,このノードは10000001=129という数を長兄として持つことになる.

しかし,いずれの場合でも長子ノードの親を求める計算では,3N+1を2回以上割ることはないということを示すことができる.まず,末尾が11である場合を考えよう.この数Nのビット列を…b11とすると,3N+1=…b110+…b11+1=…x10となり,2で1度割り込むだけで奇数になってしまう.Nが…b001と表示される場合には,3N+1=…b0010+…b001+1=…x100となって,やはり2度続けて2で割ることで奇数になる.従って,任意の奇数の長子ノードを求め,さらにその親ノードを求める計算は十分短い時間で完了すると言える.この逆演算ももちろん有限のきわめて短い時間で実行可能であると言えるから,コラッツ木の垂直関係はこれによってほぼ確立できたと言って間違いないだろう.

モヒティが盛んに主張していた,「binary formula」というのは確かにこのことであったに違いない.彼は結局自力ではそれを突き止めることはできなかったのだが…確かに,この洞察を得ることでようやく証明に至る道が見えてきたと言えるだろう.このように見てくると我々の方法の中でもっとも重要なポイントはやはり「長子ノードの発見」ということにあるのではないだろうか?

我々の提案の中には,①一般コラッツ木,②コラッツ長子木,③コラッツ完全木という三種の木構造が含まれているが,これらのうちのどの一つも説明/証明に欠かすことはできないように思われる.この意味では,今回の修正でB面から一般コラッツ木を排除してコラッツ完全木に一本化してしまったというのは早まった措置と言わざるを得ない.もう一度これらを一から整備し直すというのもかなり難儀ではあるが,やるしかないような気がする.

上の説明でまだ一つだけ欠けている点がある.長子ノードのビット列末尾は11ないし001のいずれかとしているが,もう一つの場合がある.101B=5という場合だ.この値の場合,01を除けば1という奇数になるのだから,コラッツ数の条件を満たしているが,この場合に限っては3N+1を2で割る回数は4回になる.このノード5という数の特殊性に関してはやはり,長子木を示して説明する必要があるように思われる.(上記の手順では5を例外としないと長子ノード5をスルーしてしまう…)

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA