Collatz問題 #13

C Graphviz

今までのグラフに合わせて、
操作によって初期値になるような100を超える値もノードになるように、
操作後に初期値になる操作前の値から初期値へのエッジも含めるように変更する。

collatz9.c
...snip
void collatz_route(mpz_t x)
{
    mpz_t n;
    mpz_init(n);
    mpz_sub_ui(n, x, 4UL);
    if (mpz_divisible_ui_p(n, 6UL)) {
        mpz_add_ui(n, n, 3UL);
        mpz_tdiv_q_ui(n, n, 3UL);
        gmp_printf("  %Zu -> %Zu [color=red];\n", n, x);
    }
    mpz_mul_2exp(n, x, 1);
    gmp_printf("  %Zu -> %Zu;\n", n, x);
    mpz_set(n, x);
    while (mpz_cmp_ui(n, 1UL) > 0) {
...snip

このコードで追加された部分もtredで処理することを前提にして、
操作によって初期値になるような値が100を超えるかどうかの判断をせずに、
全ての初期値について単純に操作前の値からのエッジを追加している。

$ ./collatz9 | tred | dot -Tpng -ocollatz9.png
warning: %1 has cycle(s), transitive reduction not unique
cycle involves edge 2 -> 1

$ ./collatz9 | gc -ne
     273    3259 %1 (<stdin>)

$ ./collatz9 | tred | gc -ne
warning: %1 has cycle(s), transitive reduction not unique
cycle involves edge 2 -> 1
     273     273 %1 (<stdin>)

$ ./collatz9 | tred | gvpr "BEG_G{int s=0;} N[indegree==0]{s++;} END_G{print(s);}"
warning: %1 has cycle(s), transitive reduction not unique
cycle involves edge 2 -> 1
22

$ ./collatz9 | tred | gvpr "BEG_G{int s=0;} N[name>100&&indegree==0]{s++;} END_G{print(s);}"
warning: %1 has cycle(s), transitive reduction not unique
cycle involves edge 2 -> 1
22

$ ./collatz8 | tred | gvpr "BEG_G{int s=0;} N[indegree==0]{s++;} END_G{print(s);}"
warning: %1 has cycle(s), transitive reduction not unique
cycle involves edge 2 -> 1
19

collatz9.pngのサイズはcollatz8.pngよりさらに長い935x11387ピクセルで、
1から最も遠いノード97の操作前の値194のノード分だけ縦に長くなる。
collatz8より増加したノード数273-251=22個は入力エッジが0のノード、つまり開始ノードであり、
その全てが100を超える値をもっている。
collatz8での開始ノード数が19であったのに対してcollatz9では22個に増加しているのは、
本来二つのノードからの入力エッジを受けるノードのうち開始ノードでなく途中にあるノードで、
2倍の値からのエッジがcollatz8では出力されなかったものがcollatz9で出力されているからである。

$ ./collatz9 | tred | gvpr "E[tail.name>100&&tail.indegree==0&&head.indegree==2]{print(head);}"
warning: %1 has cycle(s), transitive reduction not unique
cycle involves edge 2 -> 1
82
88
100

collatz9で増えた開始ノードを探すために、その開始ノードから入力を受けるノードの値をgvprで表示させた。
それが82, 88, 100の3個のノードであることが分かる。
各操作（エッジ）について、
操作前の値が100より大きく（tail.name>100）、
そのノードが開始ノードであり（tail.indegree==0）、
操作後の値のノードに入力エッジが二つ入っている（head.indegree==2）
ような条件を持つ操作後のノードを表示（print(head)）している。