Project Euler - Problem 12

問題

• 原文

  What is the value of the first triangle number to have over five hundred divisors?

• 日本語訳

  501 個以上の約数をもつ最初の三角数はいくらか。

解答

約数の個数は素因数分解の結果から求めることができます。 例えばn = p^a * q^b（pとqは素数）という合成数がある場合、約数は以下の表のようになります：

1	p	p2	...	pa
q	p * q	p2 * q		pa * q
q2	p * q2	p2 * q2		pa * q2
...
qb	p * qb	p2 * qb	pa * qb

p⁰ = q⁰ = 1であることを考えれば、0..aの(a + 1)通りのpのべき乗と、0..bの(b + 1)通りのqのべき乗を掛け合わせた数がnの約数であることが分かります。 これは素因数が3つ以上の場合も同様で、一般にp^a * q^b * r^c * ...の約数は(a + 1)(b + 1)(c + 1)...個存在します。

Problem 3で使った素因数分解を行う関数factorizeを改良し、各素因数について、べき乗回数をcdrに入れたペアのリストを返すようにしました。

(define (triangle-number n) (* (+ 1 n) (/ n 2)))
(define (factorize n)
  (define max-divisor (floor->exact (sqrt n)))
  (define (factorize-1 n div result)
    (if (> div max-divisor)
        (if (= n 1) result (cons (cons n 1) result))
        (let count ((n n) (i 0))
          (define (divisor? m) (zero? (modulo n m)))
          (if (divisor? div) (count (/ n div) (+ i 1))
              (factorize-1 n (+ div 2)
                           (if (zero? i) result
                               (cons (cons div i) result)))))))
  (let prepare ((n n) (i 0))
    (if (even? n) (prepare (/ n 2) (+ i 1))
        (factorize-1 n 3 (if (zero? i) '() (cons (cons 2 i) '()))))))
(define (num-of-divisors-of n)
  (apply * (map (lambda (factor) (+ (cdr factor) 1)) (factorize n))))
(define (solve)
  (let loop ((i 1))
    (define tri (triangle-number i))
    (if (> (num-of-divisors-of tri) 500) tri
        (loop (+ i 1)))))
(define (main argv)
  (display (solve))
  (newline))

参考文献

• mathschallenge.net