Chapter 05

Problem 5: Smallest multiple

aoi.iter
aoi.iter
2022.06.23に更新
このチャプターの目次

2022/06/22

https://projecteuler.net/problem=5

問題

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

考察

  • 素因数分解に関する問題
  • 2 から 20 までの数値に対して、それぞれの素因数し、2 から 20 までの数値を表現するのに十分な素数とその個数の対応の連想配列を作成する
  • 求めた素数とその個数を全て掛け合わせた結果が答えとなる
  • 1~10 とあるが、1 は product の単位元なので無視する
  • 素数の生成は math.prime を使う
    • アリストテレスの篩の実装は面倒臭い...
    • Gauche には素因数分解を行うmc-factorizeがあるが、素因数分解くらいは自分で書く
2~10の各素因数と、各素数の最大個数
   | 2 3 5 7
============
 2 | 1
 3 |   1
 4 | 2
 5 |     1
 6 |
 7 |       1
 8 | 3
 9 |   2
10 | 1   1
------------
max| 3 2 1 1

各素数とその最大個数の累乗と、それらの積
(* (expt 2 3)
   (expt 3 2)
   (expt 5 1)
   (expt 7 1))
=> 2520

解答

(use math.prime)
(use util.stream)

(define (divisible? n a)
  (zero? (mod n a)))

;; 非破壊的なhash-table-put!
(define (hash-table-put ht key value)
  (let ((ht2 (hash-table-copy ht)))
    (begin (hash-table-put! ht2 key value )
            ht2)))

;; ハッシュテーブルのkeyの値をインクリメントする
;; keyがなければ1をセットする
(define (hash-table-increment-value ht key)
  (let ((new-val (+ 1 (hash-table-get ht key 0))))
    (hash-table-put ht key new-val)))

;; ハッシュテーブルの
;; すでにセットされている値よりも新規値が大きい場合に更新を行う
(define (hash-table-put-max ht key val)
  (let ((new-val (max val
                      (hash-table-get ht key -inf.0))))
    (hash-table-put ht key new-val)))

;; ハッシュテーブルの和をとる
;; 両者に同一Keyが存在する場合、大きな値が優先される
(define (hash-table-union-max ht1 ht2)
  (let ((new-ht (hash-table-copy ht1)))
    (hash-table-fold ht2 (lambda (key val ht) (hash-table-put-max ht key val)) new-ht)))

;; 素因数分解を行う関数
(define (primes n)
  (letrec ((primes-rec (lambda (n table prime-stream)
                         (let ((prime (stream-car prime-stream)))
                           (cond ((= n 1) table)
                                 ((divisible? n prime) (primes-rec (/ n prime)
                                                                   (hash-table-increment-value table prime)
                                                                   prime-stream))
                                 (else (primes-rec n table (stream-cdr prime-stream))))))))
    (primes-rec n (make-hash-table) *primes*)))

(hash-table->alist (primes 25))
; => ((5 . 2))
(hash-table->alist (primes 18))
; => ((2 . 1) (3 . 2))


;; 解答
(define (solve n)
  (exact
   (fold *
         1
         (map (lambda (x) (expt (car x) (cdr x)))
              (hash-table->alist (fold (lambda (pht ht) (hash-table-union-max pht ht))
                                       (make-hash-table)
                                       (map primes (iota n 1))))))))

(solve 10)
; => 2520
(solve 20)
; => 232792560

感想

apply の第二引数には pair が使えない

gosh> (apply expt '(2 3))
8
gosh> (apply expt '(2 . 3))
*** ERROR: improper list not allowed: (2 . 3)
Stack Trace:
_______________________________________
  0  (apply expt '(2 . 3))
        at "(standard input)":1101
  1  (eval expr env)
        at "/usr/local/Cellar/gauche/0.9.11-p1/share/gauche-0.98/0.9.11-p1/lib/gauche/interactive.scm":336

list と pair は成り立ちが異なる

gosh> (equal? '(1 . 2) '(1 2))
#f
gosh> (equal? '(1  2) (cons 1 (cons 2 ())))
#t
gosh> (equal? '(1 . 2) (cons 1 2 ))
#t

当然、pair に対して cadr は効かない

gosh> (cadr '(1 . 2))
\*\*\* ERROR: pair required, but got 2
Stack Trace:

---

0 (cadr '(1 . 2))
at "(standard input)":1196
1 (eval expr env)
at "/usr/local/Cellar/gauche/0.9.11-p1/share/gauche-0.98/0.9.11-p1/lib/gauche/interactive.scm":336

泣く泣く、apply でなく car, cdr を使った


gosh> (expt (car '(2 . 3)) (cdr '(2 . 3)))
8

参考資料

N/A