Project Euler Problem 1

Project Euler Emacs Lisp

　遅ればせながら Project Euler というプログラム問題サイトを知りました。せっかくなので、自分の解答を残していこうと思います。言語は、C/C++ Javascript ひまわり(w) なんかを検討した末、 せっかくなら他の人があまりやっていないものを、そして一度じっくりいじってみたかったという理由で、Emacs Lisp で行くことにしました。
問題1: 1000未満の自然数のうち、3の倍数と5の倍数の総和をもとめる。[=>原文和訳]

まずは dotimes でループ処理

(require 'cl)
(defun problem001-1 ()
  (let ((N 1000)
        (total 0))
    (dotimes (i N total)
      (if (or (zerop (% i 3))
              (zerop (% i 5)))
          (incf total i)))))

　静的スコープ、動的スコープの違いはありますが、基本的に Common Lisp と似たようなコードになるかと思います。剰余計算に % が使えるのはちょっと楽です。dotimes のカウンター i は 0 から開始します。0 は「自然数」ではありませんが合計値には影響しないのでよしとします。C/C++の for ループみたいに dotimes の開始値が指定できるとスッキリするんだけど。

次、再帰

(setq max-lisp-eval-depth 5000) ;設定しないと再帰エラーになる。
(defun problem001-2 ()
  (let ((N 1000))
    (defun calc(m)
      (if (zerop m)
          0
        (+ (if (or (zerop (% m 3))
                   (zerop (% m 5)))
               m 0)
           (calc (1- m)))))
    (calc (1- N))))

　関数内ローカル関数 calc で再帰しています。デフォルトのままだと N=1000 の再帰ではエラーになりましたが、max-lisp-eval-depth 変数の値を増やすことで回避できました。

別解

　1からの連続する n個の自然数の和を求める公式があります。
　　　n * (n + 1) / 2
　ここで、連続するn個の3の倍数の和を考えると。
　　　3 + 6 + 9 + 12 +...+3n = 3 * (1 + 2 + 3 + 4 + ...+ n)
　と、n個の自然数の和 の3倍で求められることがわかります。ということは、和の公式を使えば次の式が得られます。
　　　(n * (n + 1) / 2) * 3
　同様に、最初の n個の5の倍数の和は、 (n * (n + 1) / 2) * 5
　一般化して、最初の n個の mの倍数の和は、(n * (n + 1) / 2) * m
　ここで注意しなければならないのは、これらの和の公式は「最初の n個の合計」であって、「n未満の数の合計」ではないということです。問題は 1000 未満ですから、1000未満に3の倍数や5の倍数がいくつあるかをまず計算し、それを公式の n にあてはめればよいでしょう。
　N 以下の3の倍数の個数は、N / 3 で求められます。今回は「N未満」ですから、N がカウントされないように (N-1) / 3 とすべきでしょう。N=1000 ですから、3の場合はどちらでも同じですが、5の場合はこの差が影響します。
　以上を踏まえてコードにすると、次のようになりました。

(defun problem001-3 ()
  (let* ((N 1000)
         (n (1- N)))    ;「N未満」を「n以下」と読みかえる
    (defun sum (m)
      (let ((k (floor (/ n m))))
        (* (/ (* k (1+ k)) 2) m)))
    (- (+ (sum 3) (sum 5)) (sum 15))))

　ローカル関数 sum は、n 以下（つまり N未満）の m の倍数の和を計算します。求めたいのは、3と5の倍数の和なので、(+ (sum 3) (sum 5) ) ですが、3と5両方の倍数、つまり15の倍数は それぞれのsumで重複して加算されていますので、最後に引いています。
　この関数は、Nの値による繰り返し処理がありませんので、Nが大きくなっても計算にかかるコストは変わりません。N=1000程度ではループで計算する場合との速度差は実感できませんが、N=100万ともなると目に見えて速度の違いが現れます。もっとも、そこまでNを増やすと加算結果がオーバーフローして正しい答は得られませんが。
　ちなみに Emacs Lispでは 識別子の大文字と小文字は区別されます。