Project Euler No.14

数日ぶりにProject Euler。第14問。

The following iterative sequence is defined for the set of positive integers:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

ある数nが与えられたとき、nが偶数の時はn/2を、奇数の時は3n+1を計算する。それを新しいnとして計算を続けると、どんなnで開始しても最後に必ず1になる(と予想されている)。

では、100万未満の数のうち、最大の長さの過程が必要なnはいくつだろうか。(ただし計算過程で100万を超えることは許す)

“鮮やかさより確実さ”をモットーに、これも力尽く(brute-force)で解きます。

N = 1000000;
cmax = 0;
for k=1:N-1
  n = k;
  c = 1;
  while n ~= 1
    if mod(n,2)==0
      % even
      n = n/2;
      c = c+1;
    else
      % odd
      n = 3*n + 1;
      c = c+1;
    end
  end
  if cmax < c
    cmax = c;
    kmax = k;
    fprintf(1, '%7d %3d\n', kmax, cmax);
  end
end

「最大の〜を求めよ」という問題なので、1〜999999のすべての場合を試さないといけないのが無駄な気がしてしまいます。簡単な高速化としては、まず「2の累乗になったら詰み」なので、その判定を入れるとか、「過去に到達したルートを覚えておいて、そこまで来たらあとのルートは同じ」ことを利用するとかが考えられます。

前者は「8は2の3乗なので、3ステップ」とできますし、後者の場合は「10で開始すると3ステップ後に(さっき確認した)8になるので、3+3=6ステップ」と計算できます。