プロジェクト

全般

プロフィール

Problem 14 » 履歴 » バージョン 2

Noppi, 2023/12/30 13:12

1 1 Noppi
[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]
2
# [[Problem 14]]
3
4
## Longest Collatz Sequence
5
The following iterative sequence is defined for the set of positive integers:
6
7
* $n \to n/2$ ($n$ is even)
8
* $n \to 3n + 1$ ($n$ is odd)
9
10
Using the rule above and starting with $13$, we generate the following sequence:
11
$$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1.$$
12
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$.
13
Which starting number, under one million, produces the longest chain?
14
**NOTE:** Once the chain starts the terms are allowed to go above one million.
15
16
## 最長のコラッツ数列
17
正の整数に以下の式で繰り返し生成する数列を定義する.
18
19
* n → n/2 (n が偶数)
20
* n → 3n + 1 (n が奇数)
21
22
13からはじめるとこの数列は以下のようになる.
23
$$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1.$$
24
13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)
25
さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.
26
**注意:** 数列の途中で100万以上になってもよい
27
28
```scheme
29 2 Noppi
#!r6rs
30
#!chezscheme
31
32
(import (chezscheme))
33
34
(define (collatz-list num collatz-vector)
35
  (let loop ([current-num num] [collatz '()])
36
    (cond
37
      [(= current-num 1)
38
       (reverse (cons current-num collatz))]
39
      [(and (< current-num 1000000)
40
            (vector-ref collatz-vector current-num))
41
       => (lambda (lis)
42
            `(,@(reverse collatz) ,@lis))]
43
      [else
44
        (let ([next (if (even? current-num)
45
                      (/ current-num 2)
46
                      (add1 (* current-num 3)))])
47
          (loop next (cons current-num collatz)))])))
48
49
(define (update-collatz-list! collatz collatz-vector)
50
  (let loop ([rest collatz])
51
    (cond
52
      [(null? rest) void]
53
      [else
54
        (let ([index (car rest)]
55
              [next-rest (cdr rest)])
56
          (cond
57
            [(<= 1000000 index) (loop next-rest)]
58
            [(vector-ref collatz-vector index) void]
59
            [else
60
              (vector-set! collatz-vector index rest)
61
              (loop next-rest)]))])))
62
63
(define collatz-table
64
  (let ([collatz-vector (make-vector 1000000 #f)])
65
    (let loop ([i 1])
66
      (cond
67
        [(<= 1000000 i) collatz-vector]
68
        [(vector-ref collatz-vector i)
69
         (loop (add1 i))]
70
        [else
71
          (update-collatz-list!
72
            (collatz-list i collatz-vector)
73
            collatz-vector)
74
          (loop (add1 i))]))))
75
76
(define collatz-length-vector
77
  (vector-map
78
    (lambda (num lis)
79
      (if (zero? num)
80
        (cons num 0)
81
        (cons num (length lis))))
82
    (list->vector (iota 1000000))
83
    collatz-table))
84
85
(define pickup-longest-collatz
86
  (let loop ([i 1] [max-cell '(0 . 0)])
87
    (if (<= 1000000 i)
88
      max-cell
89
      (let ([current-cell (vector-ref collatz-length-vector i)])
90
        (if (< (cdr max-cell) (cdr current-cell))
91
          (loop (add1 i) current-cell)
92
          (loop (add1 i) max-cell))))))
93
94
(define answer-14
95
  (car pickup-longest-collatz))
96
97
(printf "14: ~D~%" answer-14)
98 1 Noppi
```