「拡張コラッツ問題」は一般には成立しない

前稿(2022/04/06)には,2つの式が記載されている.

ノード番号:={長子ノード番号}.{兄弟順位}      (1)
長子ノード番号:={親ノード番号}.{長子識別子}    (2)

これら2式が正しければ,

ノードN:={地番1}.{地番2}.{地番3}…{地番k}

のようなアドレスコードが可能となり,すべての自然数はその内部にコラッツ木の(暗号化された)アドレスコードを持っているということになると予測される.前稿ではこれら2式について,

『(1)式はNの4進数表記からデコードされ,(2)は3N+1の2進数表記によってデコードされる.3N+1という計算は3進表記した値を1左シフト(した上で1をプラスする,つまり1を右端に連結)することによって得られるから,「演算(代数的操作)」というよりは,「文字列操作」として(形式的に)実行可能であると推定される.』

としているが,果たしてそう言い切れるのだろうか?『(1)式はNの4進数表記からデコードされる』という部分は,3月3日付けのログ「コラッツ国の公用語は4進数である」で説明しているように,ほぼ確実であると言えるが,『(2)は3N+1の2進数表記によってデコードされる』とすれば,以下のような類似問題が成立することが予想される.

拡張コラッツ問題:kを任意の奇数(定数)であるとする.任意の自然数Nについて,Nが偶数ならば2で割り,奇数であればk倍して1を加える操作を反復すると,かならず1に帰着する

この問題は,Wikiの「コラッツの問題」というページの「類似の問題」という項目に以下のような形式で採り上げられている.

「任意の正の整数 n に対して

  • n が偶数の場合、n を 2 で割る
  • n が奇数の場合、n に 2m – 1 (m ≥ 1)をかけて 1 を足す

という操作を繰り返すと、有限回で 1 に到達する」

m=1の場合,この命題が成立することは容易に示すことができる.m=2の場合がコラッツ問題だが,m=3の場合,つまりk=5の場合には

13→ 66→ 33→ 166→ 83→ 416→ 208→ 104→ 52→ 26→ 13

のような反例が存在し,成立しない.つまり,「拡張コラッツ問題」は一般には成立しない.上記数列から偶数を除去すると,

13→ 33→ 83→ 13

これを5進で表示すると,23, 113, 313 となる.これらの数字に左シフト+1の操作を施すと,

231, 1131, 3131

のような5進数が得られる.これを10進表記すれば,66, 166, 416 だから,確かに循環している.これをどう解釈すればよいのだろう?少なくとも,k=5の場合には,(2)式のようなものは成立していないことは確かだろう.そもそもk>3の場合に,「長子木」のようなものが構成可能であるかどうかは,まったく自明ではない.というか,おそらく,k>3の場合には「長子木」のようなものは存在していないのではないだろうか?逆に言えば,長子木のようなものが構成可能であるのは,k=3の場合に限定されるのではないだろうか?いずれにしても,「長子木とは何か?」ということが追求されなくてはならないだろう.

Wikiには「コラッツ予想の他の形式」として,「ボトムアップ方式」という提案が記載されている.「ボトムアップ方式」というのは,いままさに我々がやっている方式そのもので,コラッツ写像の逆演算からボトムアップに木を構成しようとする試みである.この記事では21ステップまでのコラッツグラフのSVG画像↓が紹介されているが,この図版の数値は偶数を含むものであるため,かなり狭い領域しか表示できていない.「完全正則」という概念にも達していないため,証明にはまだほど遠い段階にあり,「予測」の域を脱していない.

image

拡張コラッツ問題で生成されるようなグラフを拡張コラッツ木ないし,k-コラッツ木と呼ぶことにしよう.上記で見たようにk-コラッツ木は必ずしも「木」にはならないが,そのトポロジーがどのようなものになるのかは興味がある.しかし,ここではこれ以上深入りしないで,先に進むことにする.さて,懸案の仮想木上の拡張アドレスコードに掛かることにしよう.本システムでは偶数は扱わないとしたので,非長子ノード用の書式を追加するだけだ.

区切り文字として「:」を追加する.完全木では区切り文字として,3倍数には「-」を割り当て,2倍数(偶数)を識別するために「*」を追加しているが,「:」と「-」は方式的にはかなり異なる.{x-y}は{x}-{y}であり,「-」で区切られた2つの枝番(XとYは親子関係)だが,{x:y}は全体で1個の一般木上の枝番(x:y)を示している(XとYは兄弟でXはコラッツ数列には表示されない).

B面ではMax branchesという値を表示している.拡張アドレスの場合はどういうことになるか?仮想木上にないノード(非長子ノード)の枝番は無視するしかないのではないか?というか,長兄ノードは仮想木上にあるので,その枝番を適用でよいと思う.というか,それしか方法がない.幸い非長子ノードはつねに終端に来るので問題ないだろう.⇒とりあえず,アドレス→番号変換は動作するようになった.

幹線木にも対応修正を入れておこう.幹線木をどう英訳するかでいろいろな候補が挙がっている.①Truncated tree, ②Stem tree,③Minimal regular tree などなど…Nを含む極小な正則木という意味では,③が一番正確であるような気もするのだが…Stem treeでも悪くないような気もする…幹線木というオプションが存在する意義自体がよくわからないという向きには,「極小正則木」という命名は説明になっているような気もする…⇒幹線木も動作している.あとは,コラッツ数列だけだ.

既存コードの出力は,仮想木上の経路だけで止まっている.たとえば,非長子ノードの19397では

4849    19397
227 (2)    3637 [2]
5 (3)    341 [3]
1 (1)    1 [4]

が出力される.左列が仮想木,右列が一般木だが,左列にはターゲットの19397は表示されていない.19397の仮想木上の経路は1. 3. 2:1で,アドレス変換では

1 [1]
5 [3]
227 (2:1)
19397

のように表示される.これを天地逆転したものが表示されるようにしなくてはならない.つまり,

19397
227 (2:1)
5 [3]
1 [1]

のようにならなくてはならない.⇒大体動作するようになった.

▲幹線木でアドレスに1. 2. 2. 2:1を設定すると,206277の代わりに825109という数字が出てくる.この数字は少なくともダンプ出力の中には見当たらない.successorという変数におかしな値が入ってくる.ループの中で余分なことをやっているようだ.幹線木ではDumpSuccessorsで実行している処理をループ中で重複実行していた.

隣接リストの内容をチェックしておこう.⇒アドレス変換はよいが,他の2つは間違っている.


コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA