Collatz問題 #12

操作後の値が100以下のノードを全て含み、かつ、
その全てがエッジ伝いに1のノードへ到達できるようなグラフを得たい場合、
単純にやるなら、100以下の全ての値について、
これをそれぞれ初期値として、
その1に至る経路を出力したものを一つのグラフとして出力すればいい。

collatz8.c

#include <gmp.h>

void collatz_route(mpz_t x);

void collatz_route(mpz_t x)
{
    mpz_t n;
    mpz_init_set(n, x);
    while (mpz_cmp_ui(n, 1UL) > 0) {
        gmp_printf("  %Zu -> ", n);
        if (mpz_odd_p(n)) {
            mpz_mul_ui(n, n, 3UL);
            mpz_add_ui(n, n, 1UL);
            gmp_printf("%Zu [color=red];\n", n);
        } else {
            mpz_tdiv_q_2exp(n, n, 1);
            gmp_printf("%Zu;\n", n);
        }
    }
    mpz_clear(n);
}

int main(void)
{
    unsigned long i;
    mpz_t x;
    mpz_init(x);
    gmp_printf("digraph {\n  edge [color=blue];\n  1 -> 4 [color=red];\n");
    for (i = 2; i <= 100; i++) {
        mpz_set_ui(x, i);
        collatz_route(x);
    }
    gmp_printf("}\n");
    mpz_clear(x);
    return 0;
}

1になった時点で操作を打ち切るので、1から4へのエッジの出力は特別扱いとなる。

このコードは明らかに問題がある。
全ての初期値について1へ到達するまでのエッジを出力しているため、
1に近づくにつれて同一ノード対間のエッジの多重度がどんどん増加する。
この出力をそのままdotコマンドに渡して視覚化してみれば凄いことになっているのが分かる。
そこで同一ノード対間のエッジを一つにまとめるためにGraphvizのコマンドtredを使う。

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

1 4 2 1のループがあるためtredが警告を出すが、問題なく多重化されたエッジは解消される。
ただ、これにより出力されたcollatz8.pngは、
手元の環境で792x11291ピクセルという超縦長になったのでここでは示さない。
gcでノードとエッジの数を数えると、

$ ./collatz8 | gc -ne
     251    3143 %1 (<stdin>)

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

であり、251個のノードに対して3143個あったエッジがtredによって251個になっている。
1 4 2 1のループがあるので全てのノードは丁度1個の出力エッジをそれぞれ持っており、
グラフが251個のノードに対して251個のエッジになっていることは正しい。

collatz8.cでの処理中に以前に出力したノードを記録して、
余分なノードを出力しないようにコーディングすることもできるが、
上のような方法でcollatz8.cの処理は単純さを保って、
既存のプログラムに後を任せると随分楽になる。
もちろんあまりに無駄出力が多く処理量が我慢の範囲を超えない程度の問題に対して、だが。