Problem 119

http://projecteuler.net/index.php?section=problems&id=119

brute force.
かなり遅い。もう少し早いものを考えたいが、思いつかない。

import Data.List
import Data.Char

digits :: Integer -> [Integer]
digits = map (toInteger.digitToInt).show
p119 n =sort [(a^b)|
    a<-[2..floor.sqrt$ n],
    b<-[2..floor$log n / log (fromIntegral a)],
    (sum.digits) (a^b) ==a]!!29
main = print.p119 $ 10^15

必要条件は d = d ^ n (mod 9)だから、これを使えば少しは探索範囲が減る。
どれほど効率が良くなるかはよく分からないが、多分7倍ぐらい（根拠は少しある）。

と思ったら、倍ぐらいにしかならなかった。

import Data.List
import Data.Char
import Data.Ord

valid d n = d == (toInteger.sum.map digitToInt.show$d^n)

findA :: Integer -> [Integer]
findA upp =sort[d^n| d<-[2..sqrt' upp], n<-range' d, valid d n]
    where sqrt' = floor.sqrt.fromIntegral
          range' d = case lookup (mod d 9) period of
                       Just t -> takeWhile(<=(upper d)).tail.iterate (+t) $ 1
                       Nothing -> []
          period = zip [0,1,2,4,5,7,8] [1,1,6,3,6,3,2]
          upper d = floor$log (fromIntegral upp) / log (fromIntegral d)
main = print.(!!29).findA$10^15

rst76さんのコメントから、

findA :: Integer -> [Integer]
findA upp =sort[d^n| d<-[2..9*(1+upper 10)], n<-range' d, valid d n]
    where range' d = case lookup (mod d 9) period of
                       Just t -> takeWhile(<=(upper d)).tail.iterate (+t) $ 1
                       Nothing -> []
          period = zip [0,1,2,4,5,7,8] [1,1,6,3,6,3,2]
          upper d = floor$log (fromIntegral upp) / log (fromIntegral d)

かなり速くなりました。