三角数の約数

30分プログラム、その270。三角数の約数 via Project Euler。

三角数の数列は自然数の和で表わされ、7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である。 三角数の最初の10項は
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる。

最初の7項について、その約数を列挙すると、以下のとおり。
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

これから、7番目の三角数である28は5つ以上の約数をもつことが分る。
では、501 個以上の約数をもつ最初の三角数はいくらか。

またも失敗。もう30分で解けるレベルではなくなったんだろうか。

使い方

gosh> (solve 1)

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; problem11.scm -
;;
;; Copyright(C) 2008 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2008/03/24 21:14:42
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;
(use srfi-1)

(define (tri n)
  (quotient (* n (+ n 1)) 2))

(define (divisor n)
  (filter (lambda (x) (= (modulo n x) 0))
	  (iota n 1)))

(define (check n)
  (>= (length (divisor (tri n))) 501))

(define (solve n)
  (if (check n)
      n
      (solve (+ n 1))))

参考

• 過去の30分プログラム
• Problem 12 - PukiWiki