Problem 12 - dachs_hippoの日記

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
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
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

訳

三角数の列は自然数を加えることで作られる．よって，7番目の三角数は $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$ である．三角数の最初の10項は
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
である．これらの約数を一覧にすると
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
となる．ここで，28は5個よりも多い約数をもつ最初の三角数であることがわかる．
では，500個よりも多い約数をもつ最初の三角数を求めよ．

ちょっとだけ数学

自然数 $N$ の素因\1数分解を $N=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$ とすると，約数の個数は $(1+r_1)(1+r_2)\cdots(1+r_k)$ です．これを使えばよいです．素因数分解については前の問題のものを使いまわします．

Haskell

{-
Project Euler Problem 12 e12.hs
-}

import Data.List

primes::[Integer]
primes=2:(eratos [3,5..])
    where eratos (p:ps) = p: (eratos [ x | x<-ps, x `mod` p /= 0 ])
{-
primes = 2:3:([6,12..] >>= (\x->[x-1,x+1] ))
-}


min_fact::Integer->Integer
min_fact n = head $ filter (\x -> (n `mod` x ==0)) primes

factorization::Integer->[Integer]
factorization n 
    | n == p = [n]
    | otherwise = p :  factorization(n `div` p)
          where p = min_fact n

triNumber::[Integer]
triNumber = [ i*(i+1) `div` 2 | i<-[1,2..] ]

getNumOfDivisors::Integer -> Integer
getNumOfDivisors  = product . (map (\cs -> (toInteger.length) cs +1)) . group.factorization 

answer::Integer -> Integer
answer n = snd $ head $ filter (\(d,p) -> d > n ) $ map (\x ->  (getNumOfDivisors x,x) ) $ tail triNumber

答えは 76576500

計算時間を測ってみました

上のコードに

main = print $ answer 500

を追加して，コンパイルしてみました．そしてコメントアウトしていないエラトステネスの篩と「6の倍数の前後の列」を

time ./e12

で実行時間を比較しました．

エラトステネスの篩の方は

real	0m1.435s
user	0m0.816s
sys	0m0.088s

「6の倍数の前後の列」の方は

real	0m2.628s
user	0m2.248s
sys	0m0.188s

で倍近い差がでています．

これはこの問題の場合，素因数分解の回数が多いこと，素数の分布が原因だと思われます．「6の倍数の前後の列」は「素数の候補」として規則的に3個，2個おきに出現しますが，エラトステネスの篩は素数そのものが現れます．素数の分布は不規則な上に「疎な部分」もかなりあります．したがって，「6の倍数の前後の列」は無駄が多いのです．この状況においては，一度計算されてしまえば無駄のないエラトステネスの篩の方が有利です．そして素因数分解の回数が多いので，対象の数が大きいほどすでに必要な素因数は計算されている可能性は高く,無駄のないエラトステネスの篩の方が効率的なのでしょう．

追記：2008/05/08

考えてみたら，素因数分解しなくたって，2からその数の半分までの中で約数をfilterで取り出せばいいだけですな．どっちが効率的だろうか．数が大きい場合，たくさんある場合は素因数分解の方が効率的なような気もします．素因数分解そのものの効率化も当然影響しますが，ここで使ってるシンプルなものだけを考えても，素因数分解の方が早いかもしれません（未実験）．

追記2：2008/05/10

三角数は次のようにした方がHaskellらしいかもしれません．

triNumber::[Integer]
triNumber = 1:zipWith (+) [2,3..] triNumber

けど，効率はほんの少し落ちるようです．

追記3：2008/05/10

素因数分解しないで，ひたすら約数を単純に数える2008/05/08の追記の方針だと

answer n = head $ filter (\(x,y) -> y>500) $
    map (\x -> (x, 2 + length  filter (\y -> x `mod` y==0) 
                               [i| i<-[2..x`div`x] ] ))) $
    tail triNumber

となりますが，これはやっぱり論外な時間がかかります．

追記4：2008/05/11

なんでタプルをいれたのか・・・元の数をそのまま持ち運ぶ必要はないです．

answer2::Integer -> Integer
answer2 n = head $ filter (((<) n).getNumOfDivisors)  $ tail triNumber

これで十分ですね．若干速くなるかなくらいです．