Project Euler Problem 12

問題12: 501 個以上の約数をもつ最初の三角数はいくらか。[=>問題文]

問題12の解答

(defun factorize (N)
  "素因数分解"
  (let ((n N) (i 1) (dest nil))
    (if (zerop (mod n 2))
        (let ((count 0))
          (while (zerop (mod n 2))
            (setq n (/ n 2))
            (incf count))
          (setq dest (cons (cons 2 count) dest))))
    (while (>= (floor (sqrt n)) (incf i 2))
      (if (zerop (mod n i))
          (let ((count 0))
            (while (zerop (mod n i))
              (setq n (/ n i))
              (incf count))
            (setq dest (cons (cons i count) dest)))))
    (if (= n 1)
        dest
      (cons (cons n 1) dest))))

(defun count-divisors (N)
  "約数の数を取得"
  (reduce #'(lambda (acc lis)
              (* acc (1+ (cdr lis))))
          (factorize N)
          :initial-value 1))

(defun problem012 (N)
  (let ((n 0) (count 0) (tri 0))
    (while (< count N)
      (incf n)
      (incf tri n)
      (setq count (count-divisors tri)))
    tri))

(problem012 501)

　素因数分解関数 factorize は、問題3の時作成した素数表を使わない解法をベースに改造しています。以前のバージョンは、たとえば 600 の素因数分解結果を (2 2 2 3 5 5) というリストで返しましたが、今回は ( (2 . 3) (3 . 1) (5 . 2) ) というような「素数と個数のドット対」のリストで返すようにしています。
　この形で素因数分解ができれば約数の数を求めるのは簡単で、各素数の個数（ドット対のcdr部）それぞれに 1 を加え、すべて掛け合わせるだけで求まります。これは素因数にばらした素数の集合から任意個数の数字を選ぶ組み合わせの数にあたります。600の約数(2 2 2 3 5 5)の例なら、2を選ぶ個数のパターンは0〜3の4パターン、3は0個か1個かの2パターン、5は0〜2個の3パターンで、それぞれのパターン同士の組み合わせを掛け合わせると、600の約数は全部で4x2x3=24個あることがわかります。個数を掛け合わせる前に 1 を足すのは、選択数0個の場合を考慮しなければならないからですね。
　n番目の三角数は最初の n個の自然数の和なので、和の公式で計算しています。 よく考えたらどうせ n を 1 からカウントアップしているんだから、ついでに三角数も作っていけますね。１ループにつき、加算1回ですむのでこちらのほうがコスト低いです。

factorize の逆関数

　検算用に factorize で作成したドット対リストから、もとの合成数を復元する関数も作ってみました。

(defun de-factorize (lis)
  (reduce #'(lambda (acc cns)
              (* acc (expt (car cns) (cdr cns))))
          lis
        :initial-value 1))