3*n+1

アルゴリズムの問題に、3*n+1問題というのがあります。これは、「nが偶数の時 n を2で割り、nが奇数の時 3でnをかけ+1すると、nは最終的に1になるのは何故か」というやつです。

以下、プログラム。

#include <stdio.h>
#include <stdint.h>

int
loop (const unsigned long long int startNumber)
{
        unsigned long long int v = startNumber;
        int   c = 0;

        while (v != 1) {
                c++;
                if (v % 2 == 0)
                        v /= 2;
                else
                        v = 3*v+1;
        }
        return c;
}

int
main (void)
{
        unsigned long long int i = 10;

        for (i = 10; i < UINTMAX_MAX; i++) {
                printf("%Lu\t%d\n",i, loop(i));
        }
}

後でグラフ化