[Project Euler] Problem 8 「Largest product in a series」

以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

EX 6桁の数123789なら, 1*2*3*7*8と2*3*7*8*9の二通りとなり, 後者の2*3*7*8*9＝3024が最大の積となる.

一番, 面倒くさいのは与えられた1000桁の数値を分割する方法を考えることかもしれません. Schemeを使っているので, 間に空白を入れて1桁の整数のリストとすることにします. その後の計算方法は次のとおりです.

1. 整数のリストの先頭から5個の整数を取り出す.
2. 先頭の要素を捨て, 残りが5個未満になるまで繰り返す.
3. 5個の整数の積を求める.
4. 計算結果でソートする.

問題の数値と5個の要素に分ける手続きを定義します.

(require srfi/1)

(define prob-8 
  (list 7 3 1 6 7 1 7 6 5 3 1 3 3 0 6 2 4 9 1 9 2 2 5 1 1 9 6 7 4 4 2 6 5 7 4 7 4 2 3 5 5 3 4 9 1 9 4 9 3 4
        9 6 9 8 3 5 2 0 3 1 2 7 7 4 5 0 6 3 2 6 2 3 9 5 7 8 3 1 8 0 1 6 9 8 4 8 0 1 8 6 9 4 7 8 8 5 1 8 4 3
        8 5 8 6 1 5 6 0 7 8 9 1 1 2 9 4 9 4 9 5 4 5 9 5 0 1 7 3 7 9 5 8 3 3 1 9 5 2 8 5 3 2 0 8 8 0 5 5 1 1
        1 2 5 4 0 6 9 8 7 4 7 1 5 8 5 2 3 8 6 3 0 5 0 7 1 5 6 9 3 2 9 0 9 6 3 2 9 5 2 2 7 4 4 3 0 4 3 5 5 7
        6 6 8 9 6 6 4 8 9 5 0 4 4 5 2 4 4 5 2 3 1 6 1 7 3 1 8 5 6 4 0 3 0 9 8 7 1 1 1 2 1 7 2 2 3 8 3 1 1 3
        6 2 2 2 9 8 9 3 4 2 3 3 8 0 3 0 8 1 3 5 3 3 6 2 7 6 6 1 4 2 8 2 8 0 6 4 4 4 4 8 6 6 4 5 2 3 8 7 4 9
        3 0 3 5 8 9 0 7 2 9 6 2 9 0 4 9 1 5 6 0 4 4 0 7 7 2 3 9 0 7 1 3 8 1 0 5 1 5 8 5 9 3 0 7 9 6 0 8 6 6
        7 0 1 7 2 4 2 7 1 2 1 8 8 3 9 9 8 7 9 7 9 0 8 7 9 2 2 7 4 9 2 1 9 0 1 6 9 9 7 2 0 8 8 8 0 9 3 7 7 6
        6 5 7 2 7 3 3 3 0 0 1 0 5 3 3 6 7 8 8 1 2 2 0 2 3 5 4 2 1 8 0 9 7 5 1 2 5 4 5 4 0 5 9 4 7 5 2 2 4 3
        5 2 5 8 4 9 0 7 7 1 1 6 7 0 5 5 6 0 1 3 6 0 4 8 3 9 5 8 6 4 4 6 7 0 6 3 2 4 4 1 5 7 2 2 1 5 5 3 9 7
        5 3 6 9 7 8 1 7 9 7 7 8 4 6 1 7 4 0 6 4 9 5 5 1 4 9 2 9 0 8 6 2 5 6 9 3 2 1 9 7 8 4 6 8 6 2 2 4 8 2
        8 3 9 7 2 2 4 1 3 7 5 6 5 7 0 5 6 0 5 7 4 9 0 2 6 1 4 0 7 9 7 2 9 6 8 6 5 2 4 1 4 5 3 5 1 0 0 4 7 4
        8 2 1 6 6 3 7 0 4 8 4 4 0 3 1 9 9 8 9 0 0 0 8 8 9 5 2 4 3 4 5 0 6 5 8 5 4 1 2 2 7 5 8 8 6 6 6 8 8 1
        1 6 4 2 7 1 7 1 4 7 9 9 2 4 4 4 2 9 2 8 2 3 0 8 6 3 4 6 5 6 7 4 8 1 3 9 1 9 1 2 3 1 6 2 8 2 4 5 8 6
        1 7 8 6 6 4 5 8 3 5 9 1 2 4 5 6 6 5 2 9 4 7 6 5 4 5 6 8 2 8 4 8 9 1 2 8 8 3 1 4 2 6 0 7 6 9 0 0 4 2
        2 4 2 1 9 0 2 2 6 7 1 0 5 5 6 2 6 3 2 1 1 1 1 1 0 9 3 7 0 5 4 4 2 1 7 5 0 6 9 4 1 6 5 8 9 6 0 4 0 8 
        0 7 1 9 8 4 0 3 8 5 0 9 6 2 4 5 5 4 4 4 3 6 2 9 8 1 2 3 0 9 8 7 8 7 9 9 2 7 2 4 4 2 8 4 9 0 9 1 8 8 
        8 4 5 8 0 1 5 6 1 6 6 0 9 7 9 1 9 1 3 3 8 7 5 4 9 9 2 0 0 5 2 4 0 6 3 6 8 9 9 1 2 5 6 0 7 1 7 6 0 6 
        0 5 8 8 6 1 1 6 4 6 7 1 0 9 4 0 5 0 7 7 5 4 1 0 0 2 2 5 6 9 8 3 1 5 5 2 0 0 0 5 5 9 3 5 7 2 9 7 2 5 
        7 1 6 3 6 2 6 9 5 6 1 8 8 2 6 7 0 4 2 8 2 5 2 4 8 3 6 0 0 8 2 3 2 5 7 5 3 0 4 2 0 7 5 2 9 6 3 4 5 0))

(define (take-5 lst)
  (if (< (length lst) 5)
      ()
      (cons (take lst 5) (take-5 (cdr lst)))))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (sort
   (map (lambda (lst) (list (fold * 1 lst) lst))
        (take-5 prob-8))
   (lambda (a b) (< (car a) (car b))))
((0 (3 1 3 3 0))
 (0 (1 3 3 0 6))
 (0 (3 3 0 6 2))
 (0 (3 0 6 2 4))
 (0 (0 6 2 4 9))

 ..... 省略 .....

 (15552 (8 3 9 9 8))
 (16128 (9 4 7 8 8))
 (18144 (7 6 6 8 9))
 (24696 (7 9 7 7 8))
 (28224 (9 8 7 8 7))
 (28224 (8 7 8 7 9))
 (31752 (9 8 7 9 7))
 (31752 (8 7 9 7 9))
 (31752 (7 8 7 9 9))
 (40824 (9 9 8 7 9)))
> 

[Project Euler] Problem 7 「10001番目の素数」

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.

エラトステネスのふるいを使えば, 答えは求まりそうです.

1. ベクターを用意して, すべての要素を#tにする.
2. 配列の添字が２の倍数になっている要素に#fを設定する.もちろん, 2は#tのまま.
3. ２より大きな範囲で最初に#tとなっている要素の添字を求める.これが次の素数になる.
4. 見つけた素数について, 同様に#fを設定する.
5. ベクターの長さの平方根まで処理をすれば終了.

方針に従い, エラトステネスのふるいを実装します.

(require srfi/1)

(define (sieve pv n)
  (define (loop i)
    (when (< i (vector-length pv))
      (vector-set! pv i #f)
      (loop (+ i n))))
  (loop (+ n n)))

(define (find-prime pv start)
  (cond ((<= (vector-length pv) start) #f)
        ((vector-ref pv start) start)
        (else (find-prime pv (+ start 1)))))

(define (eratosthenes pv)
  (define (loop n)
    (when (and n (< n (sqrt (vector-length pv))))
      (sieve pv n)
      (loop (find-prime pv (+ n 1)))))
  (loop 2))
  
(define (prime-vector n)
  (let ((pv (make-vector (+ n 1) #t)))
    (eratosthenes pv)
    pv))

(define (prime-vect-to-list pv)
  (define (loop ans n)
    (if (< n (vector-length pv))
        (let ((p (find-prime pv n)))
          (if p 
              (loop (cons p ans) (+ p 1)) 
              (reverse ans)))
        (reverse ans)))
  (loop () 2))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (prime-vect-to-list (prime-vector 100))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
> (define pl (prime-vect-to-list (prime-vector 1000000)))
> (length pl)
78498
> (list-ref pl 10000)
104743
> 

[Project Euler] Problem 6 「二乗和の差」

最初の10個の自然数について, その二乗の和は,

1² + 2² + ... + 10² = 385

最初の10個の自然数について, その和の二乗は,

(1 + 2 + ... + 10)² = 3025

これらの数の差は 3025 - 385 = 2640 となる.

同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.

プログラムを作成しなくても解けそうですが, 折角なので計算機を使います.

1. 1から100までの自然数のリストを求める.
2. すべての要素の和を求め, その結果を2乗する.
3. それぞれを2乗したリストを作り, すべての要素の和を求める.

ここに載せるほどのことはないと思いますが, 定義した手続きは次のようなものです.

(require srfi/1)

(define (square n) (* n n))

計算結果は次のようになります.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (- (square (fold + 0 (iota 100 1)))
     (fold + 0 (map square (iota 100 1))))
25164150
> 

[Project Euler] Problem 5 「最小の倍数」

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

最小公倍数を求める問題です。

1. Problem 3で作成した手続きを使って素因数分解する.
2. 1から20までの整数を素因数分解した結果から, 重複部分を取り除く.
3. その結果を掛け合わせる.

定義する手続きは次のとおりです.

(require srfi/1)

(define (square n) (* n n))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

;; 素因数分解
(define (prime-factorization n)
  (let ((a (smallest-divisor n)))
    (if (= a n)
        (list n)
        (cons a (prime-factorization (/ n a))))))

;; リストから要素を一つ取り除く
(define (remove-one lst obj)
  (cond ((null? lst) ())
        ((equal? (car lst) obj) (cdr lst))
        (else (cons (car lst) (remove-one (cdr lst) obj)))))
  
;; bの要素がaに含まれてない場合にaに追加する.
(define (merge a b)
  (cond ((null? a) b)
        ((null? b) a)
        ((member (car b) a) 
         (cons (car b) 
               (merge (remove-one a (car b)) (cdr b))))
        (else (cons (car b) (merge a (cdr b))))))

(define (my-lcm n)
  (fold *
        1
        (fold merge 
              ()
              (map prime-factorization (iota n 1)))))

計算結果は次のようになりました.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (my-lcm 10)
2520
> (my-lcm 20)
232792560
> 

[Project Euler] Problem 4 「最大の回文積」

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.

補助的な手続きをいくつか定義して問題を解きます.

1. 整数の各桁を取り出す手続きを定義する.
2. リストが回文になっていることを判定する手続きを定義する.
3. 3桁の整数のリストを２つ作り, すべての組合せの積を求める.
4. その積から最大のものを見つける.

補助手続きは次のようになります.

(require srfi/1)

(define (decimal-format nbr)
  (define (loop ans n)
    (if (= 0 n)
        ans
        (loop (cons (remainder n 10) ans) (quotient n 10))))
  (loop () nbr))

(define (palindromic? nbr)
  (let ((dec (decimal-format nbr)))
    (equal? dec (reverse dec))))

方針に従って計算した結果は次のようになります.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (sort (apply append
               (filter (lambda (lst) (not (equal? lst ())))
                       (map (lambda (n)
                              (filter (lambda (a) (palindromic? (car a)))
                                      (map (lambda (i) (list (* i n) i n))
                                           (iota 900 100))))
                            (iota 900 100))))
        (lambda (a b) (< (car a) (car b))))

((10201 101 101)
 (11211 111 101)
 (11211 101 111)
 (12221 121 101)
 (12221 101 121)
 (12321 111 111)
 (13231 131 101)
 (13231 101 131)

 ..... 省略 .....

 (886688 968 916)
 (886688 916 968)
 (888888 962 924)
 (888888 924 962)
 (906609 993 913)
 (906609 913 993))
> 

[Project Euler] Problem 3 「最大の素因数」

13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.

SICPのp.28「除数の探索」を参考に, 素因数分解をする手続きを定義します.

(require srfi/1)

(define (square n) (* n n))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime-factorization n)
  (let ((a (smallest-divisor n)))
    (if (= a n)
        (list n)
        (cons a (prime-factorization (/ n a))))))

600851475143を素因数分解してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (prime-factorization 600851475143)
(71 839 1471 6857)
> (* 71 839 1471 6857)
600851475143
> 

[Project Euler] Problem 2 「偶数のフィボナッチ数」

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

数列の項の値が400万より小さい, 偶数値の項の総和を求めよ.

この問題もProblem 1と同じような方針で解きます.

1. 400万未満のフィボナッチ数のリストを求めます.
2. フィボナッチ数のリストから偶数のみを取り出します.
3. その和を求めます.

まず, フィボナッチ数のリストを求める手続きを定義します.

(define (fib-list n)
  (define (loop r a b)
    (if (< n a)
        (reverse r)
        (loop (cons a r) b (+ a b))))
  (loop () 1 2))

100未満の範囲で計算して方針に誤りが無いことを確認してから, 400万未満の範囲で計算します.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 128 MB.
> (fib-list 100)
(1 2 3 5 8 13 21 34 55 89)
> (filter even? (fib-list 100))
(2 8 34)
> (apply + (filter even? (fib-list 100)))
44
> (apply + (filter even? (fib-list 4000000)))
4613732

上限が400万ということなので, リストの要素数が増えそうなので末尾再帰にしてみましたが, 思ったよりも要素数が少なく残念な気分です.

> (fib-list 4000000)
(1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 
 4181 6765 10946 17711 28657 46368 75025 121393 196418
 317811 514229 832040 1346269 2178309 3524578)

[Project Euler] Problem 1 「3と5の倍数」

10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.

同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

次の方針でこの問題を解きます.

1. 1から999までの整数のリストを作ります.
2. 作った整数のリストから3の倍数か5の倍数になっている整数を取り出します.
3. 取り出した整数の和を求めます.

整数のリストを作るために, SRFI 1のiotaを使います. また, 3の倍数か5の倍数かを判定する手続きを定義します.

(require srfi/1)

(define (div-3-or-5? n)
  (or (= 0 (remainder n 3))
      (= 0 (remainder n 5))))

10未満の範囲で計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 128 MB.
> (iota 9 1)
(1 2 3 4 5 6 7 8 9)
> (filter div-3-or-5? (iota 9 1))
(3 5 6 9)
> (apply + (filter div-3-or-5? (iota 9 1)))
23
> 

正しく計算できているようです. 同様にして, 1000未満の数で計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 128 MB.
> (apply + (filter div-3-or-5? (iota 999 1)))
233168
> 

この問題は, ３の倍数の総和と５の倍数の総和から, 15の倍数の総和を引くことでも求められます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (require srfi/1)
> (apply + (iota 333 3 3))
166833
> (apply + (iota 199 5 5))
99500
> (apply + (iota 66 15 15))
33165
> (- (+ 166833 99500) 33165)
233168
>