# Euler problems/191 to 200

### From HaskellWiki

Henrylaxen (Talk | contribs) m (fixed link) |
Henrylaxen (Talk | contribs) (Solution to problem 192) |
||

Line 50: | Line 50: | ||

</haskell> | </haskell> | ||

A brief tutorial on solving this problem is available [http://maztravel.com/haskell/euler_problem_191.html here] | A brief tutorial on solving this problem is available [http://maztravel.com/haskell/euler_problem_191.html here] | ||

+ | |||

+ | |||

+ | == [http://projecteuler.net/index.php?section=problems&id=192 Problem 192] == | ||

+ | Best Approximations | ||

+ | |||

+ | Before going through the code below, it is important to have a | ||

+ | good understanding of continued fractions. Have a look at the | ||

+ | wikipedia article below. Pay particular attention to the secion | ||

+ | on semiconvergents, for that is the key to the code in closest2, | ||

+ | which calculates '''the other''' candidate for closest rational. | ||

+ | HenryLaxen May 5, 2008 | ||

+ | |||

+ | |||

+ | http://en.wikipedia.org/wiki/Continued_fraction | ||

+ | |||

+ | http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion | ||

+ | <haskell> | ||

+ | import Data.List | ||

+ | import Data.Ratio | ||

+ | -- Continued fraction representations of square roots are periodic | ||

+ | -- Here we calculate the periodic expansion | ||

+ | squareRootPeriod :: Int -> Int -> Int -> [Int] | ||

+ | squareRootPeriod r n d = m : rest | ||

+ | where | ||

+ | m = truncate ((sqrt (fromIntegral r) + fromIntegral n ) / fromIntegral d) | ||

+ | a = n - d * m | ||

+ | rest = if d == 1 && n /= 0 | ||

+ | then [] | ||

+ | else squareRootPeriod r (-a) ((r - a ^ 2) `div` d) | ||

+ | |||

+ | -- Turn the period into an infinite stream | ||

+ | continuedFraction :: [Int] -> [Integer] | ||

+ | continuedFraction l = map fromIntegral $ (head l) : (concat $ repeat (tail l)) | ||

+ | |||

+ | -- calculate successive convergents as a ratio | ||

+ | convergents :: [Integer] -> [Ratio Integer] | ||

+ | convergents l = zipWith (%) (drop 2 $ hn) (drop 2 $ kn) | ||

+ | where | ||

+ | hn = 0:1:zipWith3 (\x y z -> x*y+z) l (tail hn) hn | ||

+ | kn = 1:0:zipWith3 (\x y z -> x*y+z) l (tail kn) kn | ||

+ | |||

+ | -- here are the guts of the solution | ||

+ | -- we calculate convergents until the size of the denominator exceeds | ||

+ | -- the given bound. This is one candidate for the closest rational | ||

+ | -- approximation. The other candidate is a semiconvergent, which is | ||

+ | -- calculated as p3%q3 | ||

+ | closest2 :: Integer -> Integer -> [Ratio Integer] | ||

+ | closest2 bound n = | ||

+ | let a = convergents $ continuedFraction $ squareRootPeriod (fromIntegral n) 0 1 | ||

+ | b = takeWhile (\x -> (denominator x) <= bound) a | ||

+ | c = reverse b | ||

+ | (p:q:_) = c | ||

+ | (p1,q1) = (numerator p, denominator p) | ||

+ | (p2,q2) = (numerator q, denominator q) | ||

+ | p3 = ((bound-q2) `div` q1) * p1 + p2 | ||

+ | q3 = ((bound-q2) `div` q1) * q1 + q2 | ||

+ | in [p,(p3%q3)] | ||

+ | |||

+ | -- pick the ratio returned from closest2 which is | ||

+ | -- actually closer to the square root, and return the denominator | ||

+ | denomClosest :: Integer -> Integer -> Integer | ||

+ | denomClosest bound n = | ||

+ | let (l:r:[]) = closest2 bound n | ||

+ | c1 = if abs (l*l - (n%1)) < abs (r*r - (n%1)) then l else r | ||

+ | in denominator c1 | ||

+ | |||

+ | isSquare :: Integer -> Bool | ||

+ | isSquare n = n `elem` takeWhile (<= n) [n*n | n <- [x..] ] | ||

+ | where x = floor . sqrt . fromIntegral $ n | ||

+ | |||

+ | nonSquares :: Integer -> [Integer] | ||

+ | nonSquares k = [ n | n<-[2..k] , (not . isSquare) n] | ||

+ | |||

+ | bound = (10^12) | ||

+ | |||

+ | problem_192 :: Integer | ||

+ | problem_192 = | ||

+ | sum $ map (denomClosest bound) (nonSquares 100000) | ||

+ | |||

+ | </haskell> |

## Revision as of 10:47, 5 May 2008

## 1 Problem 191

Prize Strings

A couple of notes. I was too lazy to memoize this, so I just ran it twice, once with 15 and then again with 30. I pasted the output of the 15 run into the code. The way to get a handle on this is to just case it out. Ask yourself what can I add to award (n-1) to generate award (n). You can add an O to the end of all of award (n-1). You can add an L to any award (n-1) that doesn't contain an L, and you can add an A to award (n-1) provided it doesn't end with two A's. So the function hasM_LsAndEndsInN_As is just what is needed to cover all of the cases. Henry Laxen April 29, 2008

award 1 = 3 award 15 = 107236 award k = award (k-1) -- + O + sum [ hasM_LsAndEndsInN_As 0 i (k-1) | i<-[0..2] ] -- +L + sum [ hasM_LsAndEndsInN_As i j (k-1) | i<-[0,1], j<-[0,1] ] -- +A hasM_LsAndEndsInN_As 0 0 1 = 1 -- O hasM_LsAndEndsInN_As 1 0 1 = 1 -- L hasM_LsAndEndsInN_As 0 1 1 = 1 -- A hasM_LsAndEndsInN_As _ _ 1 = 0 hasM_LsAndEndsInN_As 0 0 15 = 5768 hasM_LsAndEndsInN_As 0 1 15 = 3136 hasM_LsAndEndsInN_As 0 2 15 = 1705 hasM_LsAndEndsInN_As 1 0 15 = 54736 hasM_LsAndEndsInN_As 1 1 15 = 27820 hasM_LsAndEndsInN_As 1 2 15 = 14071 hasM_LsAndEndsInN_As m n k | m < 0 || n < 0 = 0 | n == 0 = sum [ hasM_LsAndEndsInN_As (m-1) i (k-1) | i<-[0..2]] -- +L + sum [ hasM_LsAndEndsInN_As m i (k-1) | i<-[0..2]] -- +O | n 0 = hasM_LsAndEndsInN_As m (n-1) (k-1) -- + A -- Count awards of length k that have "m" L's in them, and end in "n" A's problem191 n = do let p a b c d = "hasM_LsAndEndsInN_As " ++ foldl (\x y -> x ++ (show y) ++ " ") "" [a,b,c] ++ "= " ++ (show d) putStrLn $ "award " ++ (show n) ++ " = " ++ show (award n) mapM_ (\(i,j) -> putStrLn $ p i j n (hasM_LsAndEndsInN_As i j n)) [ (i,j) | i<-[0..1], j<-[0..2]]

A brief tutorial on solving this problem is available here

## 2 Problem 192

Best Approximations

Before going through the code below, it is important to have a
good understanding of continued fractions. Have a look at the
wikipedia article below. Pay particular attention to the secion
on semiconvergents, for that is the key to the code in closest2,
which calculates **the other** candidate for closest rational.
HenryLaxen May 5, 2008

http://en.wikipedia.org/wiki/Continued_fraction

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion

import Data.List import Data.Ratio -- Continued fraction representations of square roots are periodic -- Here we calculate the periodic expansion squareRootPeriod :: Int -> Int -> Int -> [Int] squareRootPeriod r n d = m : rest where m = truncate ((sqrt (fromIntegral r) + fromIntegral n ) / fromIntegral d) a = n - d * m rest = if d == 1 && n /= 0 then [] else squareRootPeriod r (-a) ((r - a ^ 2) `div` d) -- Turn the period into an infinite stream continuedFraction :: [Int] -> [Integer] continuedFraction l = map fromIntegral $ (head l) : (concat $ repeat (tail l)) -- calculate successive convergents as a ratio convergents :: [Integer] -> [Ratio Integer] convergents l = zipWith (%) (drop 2 $ hn) (drop 2 $ kn) where hn = 0:1:zipWith3 (\x y z -> x*y+z) l (tail hn) hn kn = 1:0:zipWith3 (\x y z -> x*y+z) l (tail kn) kn -- here are the guts of the solution -- we calculate convergents until the size of the denominator exceeds -- the given bound. This is one candidate for the closest rational -- approximation. The other candidate is a semiconvergent, which is -- calculated as p3%q3 closest2 :: Integer -> Integer -> [Ratio Integer] closest2 bound n = let a = convergents $ continuedFraction $ squareRootPeriod (fromIntegral n) 0 1 b = takeWhile (\x -> (denominator x) <= bound) a c = reverse b (p:q:_) = c (p1,q1) = (numerator p, denominator p) (p2,q2) = (numerator q, denominator q) p3 = ((bound-q2) `div` q1) * p1 + p2 q3 = ((bound-q2) `div` q1) * q1 + q2 in [p,(p3%q3)] -- pick the ratio returned from closest2 which is -- actually closer to the square root, and return the denominator denomClosest :: Integer -> Integer -> Integer denomClosest bound n = let (l:r:[]) = closest2 bound n c1 = if abs (l*l - (n%1)) < abs (r*r - (n%1)) then l else r in denominator c1 isSquare :: Integer -> Bool isSquare n = n `elem` takeWhile (<= n) [n*n | n <- [x..] ] where x = floor . sqrt . fromIntegral $ n nonSquares :: Integer -> [Integer] nonSquares k = [ n | n<-[2..k] , (not . isSquare) n] bound = (10^12) problem_192 :: Integer problem_192 = sum $ map (denomClosest bound) (nonSquares 100000)