春なのでオイラーやります!
Problem 40. Champernowne's constant(チャンパーノウン定数)
はじめ、愚直に小数第1000000位までのチャンパーノウン定数を全て出して、そのあと第1~1000000位を取り出して掛けようと思っていたが、
とてもじゃないけど処理が終わらない。
import Data.Char (digitToInt) main = print $ product $ map (\n -> digitToInt $ c !! n) digits where c = champernowne $ last digits digits = map (10^) [0..6] champernowne limit = champernowne' 0 [] where champernowne' n list | isOver list = list | otherwise = champernowne' (n+1) (list ++ show n) isOver list = not $ null $ drop limit listそこで、チャンパーノウン定数が第何位になるかを計算しつつ、目的の位になればその値を取る、という処理を書いてみた。
目的の桁数
targets
が1,10,100,1000,10000,100000,1000000で、count
が直前のnまでで小数第何位かを表している。targetsのheadがcountとcountに現在のnを足した値の間にあれば、目的の値なのでnumsに加える、というのを
targetsがなくなるまで続ける。
Problem 41. Pandigital prime(パンデジタル素数)
自力では解き方が導き出せなかったので色々調べることに…。まず、自作のZaneli.Euler.primesLimitNumでは性能に限界があり、
エラトステネスの篩を使用した素数取得関数を別途作成。
987654321までの素数を求め、そこからパンデジタル数である最大値を判定することにした。
が、それでもまだ遅い…。
そこで「各桁の総和が3の倍数であればその数も3の倍数」という性質があるらしく(前もって知っていた知識ではなく調べたのだが…)これを利用する。
3の倍数であるパンデジタル数は素数ではないため、前もって省くことができる。
validDigit = filter (\n -> sum [1..n] `mod` 3 /= 0) [1..9]これで[1,4,7]が算出され、つまり1桁,4桁,7桁のパンデジタル数が候補ということになる。
最初に求める素数の上限も987654321までではなく7654321までで良いということになる。
reverse
を2回やっているのがイマイチだが、何とか7秒程度で終わるようになった。(今回はまず素数のリストを作り、その中からパンデジタル数であるものを探すようにしたが、
逆にまずパンデジタル数のリストを作って素数かどうかを判定する、というやり方もあっただろうか。)
Problem 42. Coded triangle numbers(符号化三角数)
listNames
関数はProblem 22 補足のeuler22-2.hsを流用した。三角数の無限リストを作る
triangleNums
関数は、普通に問題文にある通り
triangleNums = map (\n -> n * (n+1) `div` 2) [1..]でも良かったが、「前の項で足した値に+1した値を足す」という処理を
unfoldr
を使って書くこともできそうだったのでやってみた。処理速度はそんなに変わらないようだったが。