« Project Euler : Problem 12 ~ 三角数の約数の数 (1) | トップページ | 既約分数クイズ、ファレイ数列、フォードの円 »

2010年1月21日 (木)

Project Euler : Problem 12 ~ 三角数の約数の数 (2)

 ちょっと間が空きましたが、Problem 12 の続きです。

 問題はこちらをご覧ください。

 

 実際の解法を示す前に、前提となる条件をいくつか挙げておきます。

  1. n 番目の三角数は Tn = n * (n + 1) / 2 で表せる。
  2. 隣り合う正の整数 n と n + 1 は「互いに素」である。ここで、n が偶数の場合は n / 2 と n + 1 が、n が奇数の場合は n と (n + 1) / 2 がそれぞれ「互いに素」となる。
  3. 正の整数 x の約数の数を f(x) とすると、a と b が「互いに素」であれば、f(a * b) = f(a) * f(b) となる。
  4. 以上のことより、n が偶数の場合は f(Tn) = f(n / 2) * f(n + 1) となり、n が奇数の場合は f(Tn) = f(n) * f((n + 1) / 2) となる。
 ここで、f(Tn) を小さい方から見ていくと、次のようになります。
  f(T1) = f(1) * f(2/2)
  f(T2) = f(2/2) * f(3)
  f(T3) = f(3) * f(4/2)
  ...
 よく見ると、前の式の一部が必ず次の式に出てきています。ということは、小さい方から三角数の個数を調べていく場合、計算結果の一部を次に引き継ぐことが出きるので、計算量の節約になります。

 以上のことを踏まえて、Haskell のコードを書いてみました。

import Data.List (group) -- 素因数分解 factorize :: Integral a => a -> [(a, Int)] factorize 1 = [(1, 0)] factorize n = format $ factorize' n divs where divs = 2 : 3 : [x + y | x <- [6, 12 ..], y <- [-1, 1]] factorize' n ps@(p : ps') | n < p * p = [n] | rem n p == 0 = p : factorize' (div n p) ps | otherwise = factorize' n ps' format ps = [(head xs, length xs) | xs <- group ps] -- 約数の個数 countOfDivs :: Integral a => a -> Int countOfDivs n = product [b + 1 | (_, b) <- factorize n] -- 多角数の一般項 from 『Wikipedia』, modified by Tsumuji polyNum :: Integral a => a -> a -> a polyNum p n = div (p * n * (n - 1)) 2 - n * (n - 2) problem012 :: Int -> Int problem012 num = loop (countOfDivs 1) 2 where loop d1 n | d1 * d2 >= num = polyNum 3 (n - 1) | otherwise = loop d2 (n + 1) where d2 = countOfDivs (if even n then (div n 2) else n) main = print $ problem012 501
 最適化オプションを付けてコンパイルしたものを、 Pentium M, 1500MHz のノートパソコンで実行すると、次のようになりました。
$ time ./problem012 76576500 real 0m0.036s user 0m0.020s sys 0m0.000s
 前回のコードの約 5 倍の速度です。自分でもちょっとびっくりでした。

« Project Euler : Problem 12 ~ 三角数の約数の数 (1) | トップページ | 既約分数クイズ、ファレイ数列、フォードの円 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/47353497

この記事へのトラックバック一覧です: Project Euler : Problem 12 ~ 三角数の約数の数 (2):

« Project Euler : Problem 12 ~ 三角数の約数の数 (1) | トップページ | 既約分数クイズ、ファレイ数列、フォードの円 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ