コラッツの問題
d:id:tamura70:20100113:collatz と同様に， n が 2k+r について場合分けすることで，コラッツの問題を調べるプログラムを高速化する．
プログラム
以下のプログラムでは， 222 で割った余りについて場合分けし，あらかじめ表を作成している．
すなわち，222 で割った商が q 余りが r の時， c[r].len ステップ後に c[r].x * q + c[r].y になる．
また，さらに q=0 の場合は，別に表 t[r] を作成している．
#include <stdio.h> #include <sys/types.h> #include <sys/times.h> #include <sys/param.h> #define BITS (22) #define MOD (1 << BITS) typedef unsigned long long ULONG; struct { ULONG x; ULONG y; int len; } c[MOD]; int t[MOD]; double t0; void init() { ULONG x, y, n; int i, len; for (i = 0; i < MOD; i++) { x = MOD; y = i; len = 0; while (x % 2 == 0) { if (y % 2 == 0) { x /= 2; y /= 2; } else { x *= 3; y = 3*y + 1; } len++; } c[i].x = x; c[i].y = y; c[i].len = len; } t[1] = 1; for (i = 2; i < MOD; i++) { len = 0; n = i; while (n >= i) { n = (n%2 == 0) ? n/2 : 3*n+1; len++; } t[i] = len + t[n]; } } double usertime() { struct tms buffer; times(&buffer); return (double)buffer.tms_utime/HZ; } void solve() { ULONG n0, n; int max, len, len1, r; double t0, t1; max = 1; for (n0 = 1; ; n0 += 2) { n = n0; len = 0; while (n != 1) { if (n < MOD) { len += t[n]; break; } r = n % MOD; n = (ULONG)c[r].x * (n/MOD) + c[r].y; len += c[r].len; } if (len > max) { max = len; t1 = usertime() - t0; printf("n=%15qd len=%5d (%.1lf sec)\n", n0, len, t1); fflush(stdout); } } } int main(int argc, char *argv[]) { t0 = usertime(); printf("Generating table\n"); fflush(stdout); init(); printf("Start\n"); fflush(stdout); solve(); }
実行例
Let's Note CF-W5で解いた結果
Generating table Start n= 3 len= 8 (3.3 sec) n= 7 len= 17 (3.3 sec) n= 9 len= 20 (3.3 sec) n= 19 len= 21 (3.3 sec) n= 25 len= 24 (3.3 sec) n= 27 len= 112 (3.3 sec) n= 55 len= 113 (3.3 sec) n= 73 len= 116 (3.3 sec) n= 97 len= 119 (3.3 sec) n= 129 len= 122 (3.3 sec) n= 171 len= 125 (3.3 sec) n= 231 len= 128 (3.3 sec) n= 313 len= 131 (3.3 sec) n= 327 len= 144 (3.3 sec) n= 649 len= 145 (3.3 sec) n= 703 len= 171 (3.3 sec) n= 871 len= 179 (3.3 sec) n= 1161 len= 182 (3.3 sec) n= 2223 len= 183 (3.3 sec) n= 2463 len= 209 (3.3 sec) n= 2919 len= 217 (3.3 sec) n= 3711 len= 238 (3.3 sec) n= 6171 len= 262 (3.3 sec) n= 10971 len= 268 (3.3 sec) n= 13255 len= 276 (3.3 sec) n= 17647 len= 279 (3.3 sec) n= 23529 len= 282 (3.3 sec) n= 26623 len= 308 (3.3 sec) n= 34239 len= 311 (3.3 sec) n= 35655 len= 324 (3.3 sec) n= 52527 len= 340 (3.3 sec) n= 77031 len= 351 (3.3 sec) n= 106239 len= 354 (3.3 sec) n= 142587 len= 375 (3.3 sec) n= 156159 len= 383 (3.3 sec) n= 216367 len= 386 (3.3 sec) n= 230631 len= 443 (3.3 sec) n= 410011 len= 449 (3.3 sec) n= 511935 len= 470 (3.3 sec) n= 626331 len= 509 (3.3 sec) n= 837799 len= 525 (3.3 sec) n= 1117065 len= 528 (3.3 sec) n= 1501353 len= 531 (3.3 sec) n= 1723519 len= 557 (3.3 sec) n= 2298025 len= 560 (3.4 sec) n= 3064033 len= 563 (3.4 sec) n= 3542887 len= 584 (3.4 sec) n= 3732423 len= 597 (3.4 sec) n= 5649499 len= 613 (3.4 sec) n= 6649279 len= 665 (3.5 sec) n= 8400511 len= 686 (3.5 sec) n= 11200681 len= 689 (3.7 sec) n= 14934241 len= 692 (3.9 sec) n= 15733191 len= 705 (3.9 sec) n= 31466383 len= 706 (4.7 sec) n= 36791535 len= 745 (5.0 sec) n= 63728127 len= 950 (6.5 sec) n= 127456255 len= 951 (10.2 sec) n= 169941673 len= 954 (12.7 sec) n= 226588897 len= 957 (16.1 sec) n= 268549803 len= 965 (18.6 sec) n= 537099607 len= 966 (35.5 sec) n= 670617279 len= 987 (44.0 sec) n= 1341234559 len= 988 (88.8 sec) n= 1412987847 len= 1001 (93.6 sec) n= 1674652263 len= 1009 (111.3 sec) n= 2610744987 len= 1051 (176.2 sec) n= 4578853915 len= 1088 (317.0 sec) n= 4890328815 len= 1132 (339.9 sec) n= 9780657631 len= 1133 (713.6 sec) n= 12212032815 len= 1154 (928.3 sec) n= 12235060455 len= 1185 (930.3 sec) n= 13371194527 len= 1211 (1031.5 sec) n= 17828259369 len= 1214 (1424.8 sec)
