コラッツ予想のプログラム

一時期コラッツ予想にはまっていたので、その当時作成したCプログラムです。

collatz.c

/*** The case that the value is odd forever ***/
// L--> (3m+1)/2 -> (3m'+1)/2 -> (3m''+1)/2

// n[=1n+0] -> ((3/2)^1)n+(1/2) -> ((3/2)^2)n+(5/4) -> ((3/2)^3)n+(19/8)
// -> ((3/2)^4)n+(65/16) -> ((3/2)^5)n+(211/32) -> ...

// |f(n) = a_n * m + b_n    |
// |a_n = (3/2)^(n-1)       | => f(n) = (m+1) * 3^(n-1) / 2^(n-1) - 1
// |b_n = (3/2)^(n-1) - 1   |   *** Of course, f(n) is integer ***
// 2 and 3 are coprime -> (m+1)/2^(n-1) is integer and 2^(n-1) <= [less than or equal] (m+1)

/*** This program algorithm ***/
// need to check odd
// 3->5, 5->8(even), 7->11, 9->14(even), 11->17, 13->20(even), 15->23,...
// L--> need to check 3,7,11,15, ..., 4n-1

#include <stdio.h>
#define VALUE 100000

int main(void) {
  for (int i = 1; i < VALUE; i++) {
    unsigned init = 4 * i - 1;
    printf("%u", init);  // initial state: 4n-1

    // 4n-1(odd) -> 6n-1(odd) -> 9n-1(even or odd)
    unsigned long int temp = 9 * i - 1;
    printf(",%lu", temp);

    while (temp > init) {
      if (temp % 2) {
        temp = (3 * temp + 1) / 2;
      } else {
        temp /= 2;
      }
      printf(",%lu", temp);
    }
    printf("\n");
  }
}

実行結果

3,8,4,2
7,17,26,13,20,10,5
11,26,13,20,10
15,35,53,80,40,20,10
19,44,22,11
23,53,80,40,20
27,62,31,47,71,107,161,242,121,182,91,137,206,103,155,233,350,175,263,395,593,890,445,668,334,167,251,377,566,283,425,638,319,479,719,1079,1619,2429,3644,1822,911,1367,2051,3077,4616,2308,1154,577,866,433,650,325,488,244,122,61,92,46,23
...

まあ、なんか収束の規則ないかなあと思って作ったものです。

// need to check odd
// 3->5, 5->8(even), 7->11, 9->14(even), 11->17, 13->20(even), 15->23,...
// L--> need to check 3,7,11,15, ..., 4n-1

の通り、奇数を調べるのですが、その中でも交互に次に偶数がくるので、$4n-1$について列挙する、というものになっています。

んで、次のステップ行くときも、偶数になる過程はすっとばして表示しています。

どうやら、ほとんどの数については成り立つようですが、完全証明には至ってないようです。
最近、ソファ問題が証明されたかも、と話題になったので、ひそかに着々と証明が進んでいるのかもしれません。