Project Euler: Problem 14

Problem 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.

http://projecteuler.net/index.php?section=problems&id=14

ある自然数 n を、n が偶数のときにn/2、奇数のときに 3n + 1 に変形させていくと、最終的に 1 が得られることが知られている(=> コラッツの問題 - Wikipedia)。100 万以下の自然数を同様に変形させた場合、変形に要する回数が最も多い数はどれか求めよ、でいいのかな。

Gauche で書いてみた。

#!/usr/bin/env gosh

(define (collatz num)
  (let loop ((num num)
             (lis '()))
    (if (= num 1)
      (reverse (cons num lis))
      (loop (if (even? num)
              (quotient num 2)
              (+ 1 (* 3 num)))
            (cons num lis)))))

(define (main args)
  (let loop ((n 1)
             (m '()))
    (if (< n 1000000)
      (let1 x (length (collatz n))
        (loop (+ n 1)
              (if (or (null? m) (< (cdr m) x))
                (cons n x)
                m)))
      (print (car m))))
  0)

コラッツの問題の定義通りに変形させた結果をリストで返す (collatz) を定義してから、安直に 1000000 以下の自然数に対してリストの長さを調べている。

とりあえず動いたのでひとまず良しとしてしまったけど、実行にはけっこう時間がかかる。参考までに手元の MacBook で実行した結果は以下の通り。

% time ./problem14.scm
******
./problem14.scm  39.30s user 0.67s system 87% cpu 45.495 total

もっと頭の良い解きかたをしないとかっこわるいかなぁ。