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 [,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 [,1,2,4,5,7,8] [1,1,6,3,6,3,2]
upper d = floor$log (fromIntegral upp) / log (fromIntegral d)

かなり速くなりました。

More Reading
Newer// Problem 127
Older// Problem 121