ホーム - Project Euler

Problem 14¶

Longest Collatz Sequence¶

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

• $n \to n/2$ ($n$ is even)
• $n \to 3n + 1$ ($n$ is odd)

Using the rule above and starting with $13$, we generate the following sequence:
$$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 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/2 (n が偶数)
• n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.
$$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1.$$
13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)
さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.
注意: 数列の途中で100万以上になってもよい

#!r6rs
#!chezscheme

(import (chezscheme))

(define (collatz-list num collatz-vector)
  (let loop ([current-num num] [collatz '()])
    (cond
      [(= current-num 1)
       (reverse (cons current-num collatz))]
      [(and (< current-num 1000000)
            (vector-ref collatz-vector current-num))
       => (lambda (lis)
            `(,@(reverse collatz) ,@lis))]
      [else
        (let ([next (if (even? current-num)
                      (/ current-num 2)
                      (add1 (* current-num 3)))])
          (loop next (cons current-num collatz)))])))

(define (update-collatz-list! collatz collatz-vector)
  (let loop ([rest collatz])
    (cond
      [(null? rest) collatz-vector]
      [else
        (let ([index (car rest)]
              [next-rest (cdr rest)])
          (cond
            [(<= 1000000 index) (loop next-rest)]
            [(vector-ref collatz-vector index) collatz-vector]
            [else
              (vector-set! collatz-vector index rest)
              (loop next-rest)]))])))

(define collatz-table
  (let ([collatz-vector (make-vector 1000000 #f)])
    (let loop ([i 1] [collatz-vector collatz-vector])
      (cond
        [(<= 1000000 i) collatz-vector]
        [(vector-ref collatz-vector i)
         (loop (add1 i) collatz-vector)]
        [else
          (loop (add1 i)
                (update-collatz-list! (collatz-list i collatz-vector)
                                      collatz-vector))]))))

(define collatz-length-vector
  (vector-map
    (lambda (num lis)
      (if (zero? num)
        (cons num 0)
        (cons num (length lis))))
    (list->vector (iota 1000000))
    collatz-table))

(define pickup-longest-collatz
  (let loop ([i 1] [max-cell '(0 . 0)])
    (if (<= 1000000 i)
      max-cell
      (let ([current-cell (vector-ref collatz-length-vector i)])
        (if (< (cdr max-cell) (cdr current-cell))
          (loop (add1 i) current-cell)
          (loop (add1 i) max-cell))))))

(define answer-14
  (car pickup-longest-collatz))

(printf "14: ~D~%" answer-14)