Problem 1の解答例を読む

Scheme

Project EulerにProblem1の解答例がアップされていたので読んでみる。

問題は、

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

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

解答例1

僕はこう解答した。

(define (problem1 n)
  (fold (lambda (n acc)
          (if (or (zero? (modulo n 3))
                  (zero? (modulo n 5)))
              (+ acc n)
              acc))
        0
        (iota n)))

(problem1 10) ; 23
(problem1 1000) ; 233168

1から999までのリストを作って、3か5で割り切れたら合計に足していく。

擬似コードで書くと、こんなんらしい。

target=999
sum=0
for i=1 to target do
if (i mod 3=0) or (i mod 5)=0 then sum:=sum+i
output sum

僕は解答例1の方法で解いた。

でも、

10億未満の・・・と言われたらあっという間にオーバーフローしちゃうよね。

と問題提起。

解答例2

で、解答例2。

target = 999,n=3の場合、

3 + 6 + 9 + 12 + ...... + 999 = 3 * (1 + 2 + 3 + 4 + ... + 333)

となるので、終端をpとして、

p = target div n

(999 div 5の場合、199となる。)

1からpまでの等差数列の和

1 + 2 + 3 + ... + p = 1 ⁄ 2 * p * (p + 1)

合計は、

SumDivisibleBy(3)+SumDivisibleBy(5)-SumDivisibleBy(15)

として求めればいいよね。


「等差数列の和」なるほど。


擬似コードは、

target=999
Function SumDivisibleBy(n)
  p=target div n
  return n*(p*(p+1)) div 2
EndFunction
Output SumDivisibleBy(3)+SumDivisibleBy(5)-SumDivisibleBy(15)

ふむふむ。

Schemeで書き直し。SumDivisibleByを3回書くのが面倒なので、pは絶対値を取ってmapで求められるように改造してみた。

(define (problem1 n)
  (let ((sum-divisible-by
          (lambda (m)
            (let ((p (quotient n (abs m))))
                 (quotient (* m p (+ p 1)) 2)))))
       (apply + (map sum-divisible-by '(3 5 -15)))))

(problem1 999)  ; 233168
(problem1 99999) ; 2333316668
(problem1 99999999) ; 2333333316666668
(problem1 99999999999) ; 2333333333316666666668

確かに一瞬で求まる。等差数列の和スゲー。


細かいディティールまで読めないのが悲しい。きっちり英語が読めるようになりたいなぁ・・・。