project euler problem 30

問題どおりだと以下のとおり

Prelude Data.List> let f x= g $ show x ; g []=0;g (x:xs)=((read [x])::Int)^4+ g xs in [x|x<-[2..9999],f x==x]
[1634,8208,9474]
(0.30 secs, 132602804 bytes)

どうも色々実験すると6桁以内なので

main=print $ sum $ filter (\x->f x==x) [2..999999]

f x= g $ show x

g []=0
g (x:xs)=((read [x]):: Integer )^5+ g xs


実験内容

Prelude> 9^5*6
354294
Prelude> 9^5*7
413343
Prelude> map (length.show) $ map (\x->9^5*x) [1..10]
[5,6,6,6,6,6,6,6,6,6]

ということで　各桁を五乗したものを足しても6桁以上にならない。

project euler problem 29

たぶん組み合わせの出力とsort|uniqの問題だろう

import Data.List
main = print $ length $ map head $ group $ sort $ map (uncurry (^)) [(a,b)|a<-[2..100],b<-[\
2..100]]

あんまりなのでポイントフリー化してみたが余り意味が無かった。

import Data.List
main = (print.length.(map head).group.sort.(map (uncurry (^)))) [(a,b)|a<-[2..100],b<-[2..100]]

project euler problem 27

なんどやってもおかしいと思ったのは n^2+a*n+bの値がマイナスになっていてもisPrimeがTrueを出すときがあったせいだ。

import Data.Numbers.Primes
import Data.Ord
import Data.List

main=print $  uncurry (*) $ maximumBy (comparing (length.plist)) ab
m=1000
ab = [(a,b)|a<-[(-m)..m],b<- takeWhile (<m) primes ]
plist (a,b) = takeWhile ck [0..]
    where f n = n*n+a*n+b
          ck n | f n < 0 = False  -- isPrimeがマイナスを素数として判定するため                      
               | otherwise = isPrime $ f n

素数列を生み出すライブラリのおかげで６秒で計算できた。

haskell で 素数のライブラリを使う

http://hackage.haskell.org/packages/archive/primes/0.2.0.0/doc/html/Data-Numbers-Primes.html

これをつかう。

cabal install primes

以上

使い方

Prelude Data.Numbers.Primes> :m Data.Numbers.Primes 
Prelude Data.Numbers.Primes> sum $ takeWhile (<2000000) primes
142913828922
(0.62 secs, 401446300 bytes)

ものすごい速さだ。なぜいまままで気がつかなかったorz

コンパイルするときには ghc --make とやればモジュールをリンクしてくれる。

問題点 マイナスも素数としてしまう。（ほんとの素数の定義はそうなのかな？）

Prelude Data.Numbers.Primes> isPrime (-5)
True

project euler problem 28

73 74 75 76 77 78 79 80 81
72 43 44 45 46 47 48 49 50
71 42 21 22 23 24 25 26 51
70 41 20 7 8 9 10 27 52
69 40 19 6 1 2 11 28 53
68 39 18 5 4 3 12 29 54
67 38 17 16 15 14 13 30 55
66 37 36 35 34 33 32 31 56
65 64 63 62 61 60 59 58 57

増分を記述すると

☆ ☆ ☆ ☆ ☆
1 3 5 7 9 13 17 21 25 31 37 43 49 57 65 73 81
+2 +2 +2 +2 +4 +4 +4 +4 +6 +6 +6 +6 +8 +8 +8 +8

ここで、各増分の末項は9,25,49,81と奇数の二乗になっているのを利用して

Prelude> let n=1001 in sum $ concat ([1]:[[b-3*c,b-2*c,b-c,b]|a<-[3,5..n],let b=a*a;c=a-1])
669171001
(0.01 secs, 3149680 bytes)

project euler problem 26

フェルマーの小定理をみると
mod a^(p-1) p == 1 (pは2,5以外の素数）
aを１０とすると　10^(p-1)は　p-1桁のなかに循環少数が含まれている
また、余りが1になったとき循環が終わることがわかる

http://www.math.kindai.ac.jp/~chinen/junkan_f/junkan.html

ということで割り算の筆算を実装して余りが１になったときに循環しているとやればOK

import Data.List
import Data.Ord
main = print $ maximumBy (comparing (length.recurringCycle)) $ drop 3 $ takeWhile (<1000) primes

recurringCycle n = rc 1 n
    where rc n d
              | mod (n*10) d == 1 = [div (n*10) d] --余りが1のとき循環終了                          
              | otherwise = (div (n*10) d):(rc (mod (n*10) d) d )

primes = 2:[x|x<-[3,5..],isPrime x]
    where isPrime x = all ((/=0).(mod x)) $ takeWhile (<= (floor.sqrt.fromIntegral) x) primes

maximumBy で comparingをやるのをわすれてて苦労した。