Difference between revisions of "Euler problems/121 to 130"
Jump to navigation
Jump to search
Marypoppins (talk | contribs) |
|||
| Line 1: | Line 1: | ||
| + | Do them on your own! |
||
| − | == [http://projecteuler.net/index.php?section=problems&id=121 Problem 121] == |
||
| − | Investigate the game of chance involving coloured discs. |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | import Data.List |
||
| − | problem_121 = possibleGames `div` winningGames |
||
| − | where |
||
| − | possibleGames = product [1..16] |
||
| − | winningGames = |
||
| − | (1+) $ sum $ map product $ chooseUpTo 7 [1..15] |
||
| − | chooseUpTo 0 _ = [] |
||
| − | chooseUpTo (n+1) x = |
||
| − | [y:z | |
||
| − | (y:ys) <- tails x, |
||
| − | z <- []: chooseUpTo n ys |
||
| − | ] |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=122 Problem 122] == |
||
| − | Finding the most efficient exponentiation method. |
||
| − | |||
| − | Solution using a depth first search, pretty fast : |
||
| − | <haskell> |
||
| − | import Data.List |
||
| − | import Data.Array.Diff |
||
| − | import Control.Monad |
||
| − | |||
| − | depthAddChain 12 branch mins = mins |
||
| − | depthAddChain d branch mins = foldl' step mins $ nub $ filter (> head branch) |
||
| − | $ liftM2 (+) branch branch |
||
| − | where |
||
| − | step da e | e > 200 = da |
||
| − | | otherwise = |
||
| − | case compare (da ! e) d of |
||
| − | GT -> depthAddChain (d+1) (e:branch) $ da // [(e,d)] |
||
| − | EQ -> depthAddChain (d+1) (e:branch) da |
||
| − | LT -> da |
||
| − | |||
| − | baseBranch = [2,1] |
||
| − | |||
| − | baseMins :: DiffUArray Int Int |
||
| − | baseMins = listArray (1,200) $ 0:1: repeat maxBound |
||
| − | |||
| − | problem_122 = sum . elems $ depthAddChain 2 baseBranch baseMins |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=123 Problem 123] == |
||
| − | Determining the remainder when (pn − 1)n + (pn + 1)n is divided by pn2. |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | problem_123 = |
||
| − | fst . head . dropWhile (\(n,p) -> (2 + 2*n*p) < 10^10) $ |
||
| − | zip [1..] primes |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=124 Problem 124] == |
||
| − | Determining the kth element of the sorted radical function. |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | import Data.List |
||
| − | compress [] = [] |
||
| − | compress (x:[]) = [x] |
||
| − | compress (x:y:xs) | x == y = compress (y:xs) |
||
| − | | otherwise = x : compress (y:xs) |
||
| − | |||
| − | rad = product . compress . primeFactors |
||
| − | |||
| − | radfax = (1,1) : zip [2..] (map rad [2..]) |
||
| − | |||
| − | sortRadfax n = sortBy (\ (_,x) (_,y) -> compare x y) $ take n radfax |
||
| − | problem_124=fst$sortRadfax 100000!!9999 |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=125 Problem 125] == |
||
| − | Finding square sums that are palindromic. |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | import Data.List as L |
||
| − | import Data.Set as S |
||
| − | |||
| − | hi = 100000000 |
||
| − | |||
| − | ispalindrome n = (show n) == reverse (show n) |
||
| − | |||
| − | -- the "drop 2" ensures all sums use at least two terms |
||
| − | -- by ignoring the 0- and 1-term "sums" |
||
| − | sumsFrom i = |
||
| − | takeWhile (<hi) . |
||
| − | drop 2 . |
||
| − | scanl (\s n -> s + n^2) 0 $ [i..] |
||
| − | |||
| − | limit = |
||
| − | truncate . sqrt . fromIntegral $ (hi `div` 2) |
||
| − | |||
| − | problem_125 = |
||
| − | fold (+) 0 . |
||
| − | fromList . |
||
| − | concat . |
||
| − | L.map (L.filter ispalindrome . sumsFrom) $ [1 .. limit] |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=126 Problem 126] == |
||
| − | Exploring the number of cubes required to cover every visible face on a cuboid. |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | problem_126 = undefined |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=127 Problem 127] == |
||
| − | Investigating the number of abc-hits below a given limit. |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | import Data.List |
||
| − | import Data.Array.IArray |
||
| − | import Data.Array.Unboxed |
||
| − | |||
| − | main = appendFile "p127.log" $show$ solve 99999 |
||
| − | |||
| − | rad x = fromIntegral $ product $ map fst $ primePowerFactors $ fromIntegral x |
||
| − | primePowerFactors x = [(head a ,length a)|a<-group$primeFactors x] |
||
| − | solve :: Int -> Int |
||
| − | solve n = sum [ c | (rc,c) <- invrads |
||
| − | , 2 * rc < c |
||
| − | , (ra, a) <- takeWhile (\(a,_)->(c > 2*rc*a)) invrads |
||
| − | , a < c `div` 2 |
||
| − | , gcd ra rc == 1 |
||
| − | , ra * rads ! (c - a) < c `div` rc] |
||
| − | where |
||
| − | rads :: UArray Int Int |
||
| − | rads = listArray (1,n) $ map rad [1..n] |
||
| − | invrads = sort $ map (\(a,b) -> (b, a)) $ assocs rads |
||
| − | problem_127 = main |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=128 Problem 128] == |
||
| − | Which tiles in the hexagonal arrangement have prime differences with neighbours? |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | p128= |
||
| − | concat[m|a<-[0..70000],let m=middle a++right a,not$null m] |
||
| − | where |
||
| − | middle n |
||
| − | |all isPrime [11+6*n,13+6*n,29+12*n]=[2+3*(n+1)*(n+2)] |
||
| − | |otherwise=[] |
||
| − | right n |
||
| − | |all isPrime [11+6*n,17+6*n,17+12*n]=[1+3*(n+2)*(n+3)] |
||
| − | |otherwise=[] |
||
| − | problem_128=do |
||
| − | print(p128!!1997) |
||
| − | isPrime x |
||
| − | |x<100=isPrime' x |
||
| − | |otherwise=all (millerRabinPrimality x )[2,7,61] |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=129 Problem 129] == |
||
| − | Investigating minimal repunits that divide by n. |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | import Data.List |
||
| − | factors x=fac$fstfac x |
||
| − | funp (p,1)= |
||
| − | head[a| |
||
| − | a<-sort$factors (p-1), |
||
| − | powMod p 10 a==1 |
||
| − | ] |
||
| − | funp (p,s)=p^(s-1)*funp (p,1) |
||
| − | funn []=1 |
||
| − | funn (x:xs) =lcm (funp x) (funn xs) |
||
| − | p129 q= |
||
| − | head[a| |
||
| − | a<-[q..], |
||
| − | gcd a 10==1, |
||
| − | let s=funn$fstfac$(*9) a, |
||
| − | s>q, |
||
| − | s>a |
||
| − | ] |
||
| − | problem_129 = p129 (10^6) |
||
| − | </haskell> |
||
| − | |||
| − | == [http://projecteuler.net/index.php?section=problems&id=130 Problem 130] == |
||
| − | Finding composite values, n, for which n−1 is divisible by the length of the smallest repunits that divide it. |
||
| − | |||
| − | Solution: |
||
| − | <haskell> |
||
| − | --factors powMod in p129 |
||
| − | fun x |
||
| − | |(not$null a)=head a |
||
| − | |otherwise=0 |
||
| − | where |
||
| − | a=take 1 [n|n<-sort$factors (x-1),(powMod x 10 n)==1] |
||
| − | problem_130 =sum$take 25[a|a<-[1..], |
||
| − | not$isPrime a, |
||
| − | let b=fun a, |
||
| − | b/=0, |
||
| − | mod (a-1) b==0, |
||
| − | mod a 3 /=0] |
||
| − | </haskell> |
||
Revision as of 21:44, 29 January 2008
Do them on your own!