diff options
Diffstat (limited to 'haskell/wip')
| -rw-r--r-- | haskell/wip/057-square_root_convergents.hs | 53 | ||||
| -rw-r--r-- | haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs | 34 |
2 files changed, 87 insertions, 0 deletions
diff --git a/haskell/wip/057-square_root_convergents.hs b/haskell/wip/057-square_root_convergents.hs new file mode 100644 index 0000000..5ef5da1 --- /dev/null +++ b/haskell/wip/057-square_root_convergents.hs @@ -0,0 +1,53 @@ +------ +-- Square root convergents +-- Problem 57 +-- +-- It is possible to show that the square root of two can be expressed as an infinite +-- continued fraction. +-- √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213... +-- By expanding this for the first four iterations, we get: +-- 1 + 1/2 = 3/2 = 1.5 +-- 1 + 1/(2 + 1/2) = 7/5 = 1.4 +-- 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666... +-- 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379... +-- The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, +-- 1393/985, is the first example where the number of digits in the numerator exceeds +-- the number of digits in the denominator. +-- In the first one-thousand expansions, how many fractions contain a numerator +-- with more digits than denominator? +------ + + +data Fraction = Numerator Int | Fraction Fraction Fraction deriving (Show) + +main = do + print (mulF (Fraction (Numerator 1) (Numerator 4)) (Numerator 8)) + -- print (sqrt2Fraction 4) + +-- sqrt2Fraction :: Int -> Fraction +-- sqrt2Fraction 1 = Fraction 3 2 +-- sqrt2Fraction x = addF (Numerator 1) d +-- where d = Fraction 1 (addF (Numerator 1) (sqrt2Fraction (x - 1))) + +-- addF :: Fraction -> Fraction -> Fraction +-- addF (Numerator n1) (Numerator n2) = Numerator (n1 + n2) +-- addF (Numerator n) f = addF (Fraction (Numerator n) (Numerator 1)) f +-- addF f (Numerator n) = addF f (Fraction (Numerator n) (Numerator 1)) +-- addF (Fraction n1 d1) (Fraction n2 d2) = Fraction n d +-- where n = addF (mulF n1 d2) (mulF n2 d1) +-- d = mulF d1 d2 + +mulF :: Fraction -> Fraction -> Fraction +mulF (Numerator n1) (Numerator n2) = Numerator (n1 * n2) +mulF (Numerator n) f = mulF (numToFrac n) f +mulF f (Numerator n) = mulF f (numToFrac n) +mulF f (Numerator n) = mulF f (Fraction (Numerator n) (Numerator 1)) +mulF (Fraction n1 d1) (Fraction n2 d2) = Fraction n d + where n = mulF n1 n2 + d = mulF d1 d2 + + +numToFrac :: Fraction -> Fraction +numToFrac (Numerator n) = Fraction (Numerator n) (Numerator 1) +numToFrac f = f + diff --git a/haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs b/haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs new file mode 100644 index 0000000..e4fd400 --- /dev/null +++ b/haskell/wip/145-how_many_reversible_numbers_are_there_below_onebillion.hs @@ -0,0 +1,34 @@ +------ +-- How many reversible numbers are there below one-billion? +-- Problem 145 +-- +-- Some positive integers n have the property that the sum [ n + reverse(n) ] consists +-- entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. +-- We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. +-- Leading zeroes are not allowed in either n or reverse(n). +-- There are 120 reversible numbers below one-thousand. +-- How many reversible numbers are there below one-billion (10^9)? +------ + + +main = do + let notZeroEndedNums = filter (\x -> x `mod` 10 /= 0) [1..10 ^ 6] + revs = filter reversible notZeroEndedNums + -- print revs + print (length revs) + -- print $ length $ filter id $ map reversible notZeroEndedNums + -- print $ [r2 - r1 | (r1, r2) <- zip revs (tail revs)] + +-- countReversible :: Int -> Int +-- countReversible = 0 + + +reversible :: Int -> Bool +reversible x = allOddDigits (x + rx) + where rx = read . reverse . show $ x + +allOddDigits :: Int -> Bool +allOddDigits x + | x `mod` 2 == 0 = False + | x `div` 10 == 0 = True + | otherwise = allOddDigits (x `div` 10) |