Collatz問題 #11

操作後の値が100以下になる操作を全て挙げてDOT言語で表したグラフを出力してみる。

collatz7.c

#include <stdio.h>

int main(void)
{
    unsigned long x;
    puts("digraph {\n  edge [color=blue];");
    for (x = 1; x <= 100; x++) {
        if (x % 6 == 4) printf("  %lu -> %lu [color=red];\n", (x - 1) / 3, x);
        printf("  %lu -> %lu;\n", x << 1, x);
    }
    puts("}");
    return 0;
}

このプログラムが出力したグラフにおいては、値が100以下のノード数は、

$ ./collatz7 | gvpr "BEG_G{int s=0;} N[name<=100]{s++;} END_G{print(s);}"
100

となる。
しかし、出力エッジ数が0のノードの数が、

$ ./collatz7 | gvpr "BEG_G{int s=0;} N[outdegree==0]{s++;} END_G{print(s);}"
33

であり、接続されたエッジを通って1のノードに到達できないノードが33個以上あることが分かる。
collatz6の結果によればこれは100-49=51個ある。