Collatz問題 #8

一回の操作である値になるような操作前の値を求め、
さらにその値になる操作前の値を求めるという手続きを繰り返す。
これを1から始めることで1へ至る経路を網羅することができる。
値によっては操作前の値が二つ存在する場合があるので、
この結果は単純な数列で表現せずにグラフで表現する。
これにはGraphvizのDOT言語を使う。

collatz6.c

#include "queue.h"

int main(void)
{
    mpz_t x, y;
    queue_t queue;
    mpz_init_set_ui(x, 1UL);
    mpz_init(y);
    queue_init(queue);
    queue_enqueue(queue, x);
    gmp_printf("digraph {\n  edge [color=blue];\n");
    while (! queue_isempty(queue)) {
        queue_dequeue(queue, x);
        mpz_sub_ui(y, x, 4UL);
        if (mpz_divisible_ui_p(y, 6UL)) {
            mpz_add_ui(y, y, 3UL);
            mpz_tdiv_q_ui(y, y, 3UL);
            gmp_printf("  %Zu -> %Zu [color=red];\n", y, x);
            if (mpz_cmp_ui(y, 100UL) <= 0 && mpz_cmp_ui(y, 1UL)) queue_enqueue(queue, y);
        }
        mpz_mul_2exp(y, x, 1);
        gmp_printf("  %Zu -> %Zu;\n", y, x);
        if (mpz_cmp_ui(y, 100UL) <= 0) queue_enqueue(queue, y);
    }
    gmp_printf("}\n");
    queue_fin(queue);
    mpz_clear(x);
    mpz_clear(y);
    return 0;
}

グラフは操作前の値から操作後の値へ矢印を引く。
その色は操作前の値が偶数の場合は青色、奇数の場合は赤色とする。
操作前の値が奇数の場合、操作後の値はその3倍に1を加えたものなので、
その値はであり、6で割って4余る数となる。
最初の操作後の値1をキューに与え、
キューから操作後の値を一個取り出しては操作前の値を求めてキューに入れていく。
この手続きでキューが空になることはないので、
操作前の値が100を超えたときはキューに入れずに打ち切ることにした。
これで1に至る経路のごく一部が芋づる式に得られる。

            if (mpz_cmp_ui(y, 100UL) <= 0 && mpz_cmp_ui(y, 1UL)) queue_enqueue(queue, y);

にて、エンキューする前に操作前の値yが1ではないことをチェックしているのは、
1 4 2 1のループを無限にエンキューすることを防ぐためである。
Collatz問題の予想が正しければこのループ以外にループは無いはずなので、
このループカットさえしておけば一度現れた値全てを記録する必要はない。

digraph {
  edge [color=blue];
  2 -> 1;
  4 -> 2;
  1 -> 4 [color=red];
  8 -> 4;
  16 -> 8;
  5 -> 16 [color=red];
  32 -> 16;
...snip

のようなDOT言語による記述が結果として標準出力に得られる。