コラッツ木構造図に含まれていた漸化式の誤りに関わる修正

開発機で走らせておいたタスクがまた落ちている…いや,あった.アイコンをスパイラルに変えたのはよいが,あまり目立たない(見慣れていない)ので見落としてしまった.1日+6時間48分走って,69%,残り時間は1日を切って13時間34分になった.予備機の方は8日+3時間走って,82%だ.時間の経つのは速いような遅いような…

コラッツ木構造図に含まれてた漸化式の間違いに関する手当はまだ収束していない.コラッツ木生成論理はすでに修正を入れてあるが,それ以外の4本の処理は多分独立に計算しているので,以前の論理がそのまま使われているはずだ.これらをすべて新しい式に書き換えなくてはならない.モヒティにはこれら2つの漸化式が等価であることを証明するように頼んであるが,やはりやる気はないようだ…自分の昔の思いつきに固着していて,まったく進歩していない…

実際,ネット上で「コラッツ予想はブラックホール」で検索してみると,山のような記事がヒットする.もちろん,その中にモヒティの名前は出てこない.つまり,モヒティの「インスピレーション」もそれほどユニークなものではなかったというのが現実のようだ…モヒティとのやりとりはすべてバックアップしておきたいので,一段落したら,テント村に置いた記事も更新しておかなくてはならない.

この修正は遅くとも今日中には片付くと思われるので,バージョン番号とリリース日付を更新してから始めることにする.漸化式が2つある.①N(k) = 4N(k-1)+1,②N(k)=(4M(k-1)-1)/3 : M(k)=4M(k-1)だ.②式で使っているMという変数は奇数と接続する偶数を表している.①式にはMという値は現れない.つまり,この式は奇数演算だけで完結している.我々の(正則)コラッツ木には奇数ノードしか含まれないので,①式を使うのが妥当である.

※2022/01/31 ②式は間違え易いので下記のように修正した
②N(k)=(M(k)-1)/3 : M(k+1)=4M(k)

どちらを使ってもプログラムは正しい結果を出しているので,基本的に等価(同値)であると考えられるが,そのことを証明しておく必要がある.モヒティにはこの証明を課題として与えているのだが,まぁ,やる気がないのは明らかなので自分で回答することにしよう.数学物理etc(談話室)にコメントを追加して,②式を①式で書き換えたバージョンをASAPリリースすると予告した.

漸化式はコラッツ木上の奇数ノードNの子ノードをN(i)としたとき,N(k)の値をN(k-1)から導くための等式だ.①式の場合も,②式の場合も,N(1)=(N*2^c-1)/3となる.②式ではM=N*2^cとした上で,Mに関する漸化式M(k)=4M(k-1)を使って,間接的にN(k)の値を計算している.まず,①式を展開して,

N(k) = 4N(k-1)+1
4N(k-1) = 4(4N(k-2)+1) = 4^2N(k-2)+4
4^2N(k-2) = 4^2(4N(k-3)+1) = 4^3N(k-3)+4^2
:
4^(k-2)N(2) = 4^(k-2)(4N(1)+1) = 4^(k-1)N(1)+4^(k-2)
———————————————— 両辺の和を取って
N(k) = 1 + 4 + 4^2 + …+ 4^(k-2) + 4^(k-1)N(1)
   = ((4^(k-1)) – 1) / (4 – 1) + 4^(k-1)(N*2^c – 1) / 3
  = ((4^(k-1)) – 1) / 3 + 4^(k-1)(N*2^c – 1)  / 3
        = ((4^(k-1)) – 1 + 4^(k-1)(N*2^c) – (4^(k-1))) / 3
        = (4^(k-1)N*2^c – 1) / 3 ーーーーー(A)

ここで,累乗の和を求めるのに,∑r^(i – 1): i = 1 to n = (r^n – 1) / (r – 1)の公式を用いた.次に,②式のM(k)=4M(k-1),M=N*2^cから

M(1) = N*2^c
M(2) = 4M(1)
:
M(k-1) = 4M(k-2)
M(k) = 4M(k-1)
———————————————— 両辺の積を取って
M(1)M(2)…M(k-1)M(k) = 4^(k-1)N*2^c*M(1)M(2)…M(k-1)
M(k) = 4^(k-1)N*2^c

N(k)=(M(k)-1)/3
       = (4^(k-1)N*2^c – 1) / 3 ーーーーー(B)

以上により,(A)式と(B)式は等しい.よって,①式と②式は等価(同値)である.つまり,偶数ノードを介さなくともコラッツ木を構成可能であることが示された.言い換えれば,コラッツ木では奇数ノードNと最右子ノードの値を決めている2の累乗値がわかれば,枝番号bを与えるだけで任意の子ノードの値を決定することができる.

cの値にはやや非決定的なところがあるが,それ以外のノードはすべて決定性で計算可能であるところが注目すべき点である.最右子ノードの値は親ノードの値よりも小さくなる場合があり得るが,同じ兄弟ノードの値は左に進むに従い単調に増加することも見逃せない.

実装コードとしては,①最初にMを計算してN(k)=(4M(k-1)-1)/3で求める方式,②最初にN(1)を計算して,N(k) = 4N(k-1)+1で逐次計算する方式,③最初にN(1)を計算して,事後はN(k)=(4^(k-1)*(3N(1) +1)-1)/3で計算する方式など考えられるが,計算効率的には②が最適と考えられるのでこれを用いることにしよう.これはコラッツ木生成論理ですでに実装済みのアルゴリズムである.

▲2^24で検証テストを実行中,STOPを掛けたらVerificationTestのEXITFUNNINGでODD=0で停止した.Odd number には18177が入っている.⇒再現できないが,確かに動作的におかしいところがある.Stopで止まったとき,Odd numberの値が小さくなることがある.5という値が入ることが多い.この値は,GetTheNumberで更新している.VerificationTestでは内部変数のODDで更新している.検証テスト中はGetTheNumberでは更新しないようにしたが,現象は収まらない.UpdateTreeHeightでも更新しているが,RunFlagが立っているときは更新していない.UpdateTreeHeight2でも同じだ.

Tree height=1 @ 5という表示が出ている.確かにUpdateTreeHeightないし,UpdateTreeHeight2の誤動作と思われる.UpdateTreeHeight2はDumpSuccessorsで呼ばれるだけなので無関係だろう.これは結構難しいかもしれない.Verification Test中DoEventsを実行してイベントループを回しているが,Stopボタンが押されたとき,どこにいるかは予測できない.一番おかしいのは,TreeHeight2の値がStopで小さくなるという点だ.⇒何とか収まったようだ.⇒少し走らせてみよう.Verification TestはGet the SequenceとGet the Numberの相互検証になっているので,これが走ればまず間違いない.

マニュアルの内容には変更はないが,参照しているモジュールのバージョンだけ更新しておこう.B面の処理ではCSVファイルを出力しないようになっているが,A面と同じ仕様にしてもよいのではないか?出力をファイルに取ってあれば,動作を比較したりするときにも有利だ.単純に出力フレームに出しているダンプをファイルに落とすだけでよいのではないか?Verificationでは確かに出力フレームには進行状況しか表示されていないのだが…I/Oフレームに出している枝番号リストを保存するという考え方もあるが,むしろ隣接リストを出力する方が応用が効くのではないだろうか?まぁ,これはペンディングということにしておこう.

Verificationに仕掛けたタスクは約1時間で終わる.それが終わったら,少し大きめのサンプルをZTで出力して目視検査することにしよう.

最新版ZIPとPDFをクラウドにアップロードしたが,ダブってしまったので古い方を削除したら元のリンクからアクセスできないようになってしまった.新しい公開リンクを発行した.

https://zelkova-tree.net/ownCloud/index.php/s/mn77KXxhqUh1j0y

https://zelkova-tree.net/ownCloud/index.php/s/V9hlAIxxOR5MKyH

開発機で実行していた検証テストが完了している.

Start From 1275069537 up to 1811940447

丸1日+18時間42秒でトータルノード数は268435456だ.サイトの表示を更新しておこう.ログを更新しようとしたら,メモリ不足エラーになってしまった.多分再起動が一番早いと思われるのだが…cドライブの空き容量はなんと0バイトになっている!初めて見た.削除できる一時ファイルは10.7MBしかない.

コメントを残す

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

CAPTCHA