diff options
| -rw-r--r-- | haskell/027-quadratic_primes.hs | 43 | ||||
| -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 |
3 files changed, 130 insertions, 0 deletions
diff --git a/haskell/027-quadratic_primes.hs b/haskell/027-quadratic_primes.hs new file mode 100644 index 0000000..b971b18 --- /dev/null +++ b/haskell/027-quadratic_primes.hs @@ -0,0 +1,43 @@ +------ +-- Quadratic primes +-- Problem 27 +-- +-- Euler discovered the remarkable quadratic formula: +-- $n^2 + n + 41$ +-- It turns out that the formula will produce 40 primes for the consecutive integer values +-- $0 \le n \le 39$. However, when $n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41$ +-- is divisible by 41, and certainly when $n = 41, 41^2 + 41 + 41$ is clearly divisible by 41. +-- The incredible formula $n^2 - 79n + 1601$ was discovered, which produces 80 primes +-- for the consecutive values $0 \le n \le 79$. The product of the coefficients, +-- −79 and 1601, is −126479. +-- Considering quadratics of the form: +-- +-- $n^2 + an + b$, where $|a| < 1000$ and $|b| \le 1000$where $|n|$ is the modulus/absolute +-- value of $n$e.g. $|11| = 11$ and $|-4| = 4$ +-- +-- Find the product of the coefficients, $a$ and $b$, for the quadratic expression that +-- produces the maximum number of primes for consecutive values of $n$, starting with $n = 0$. +------ + + +import Data.List(maximumBy) + +main = do + let maxTuple = fst $ maximumBy (\(_, l1) (_, l2) -> compare l1 l2) + [((a, b), length (quadraticPrimes a b)) | a <- [-999..999], b <- [-1000..1000]] + print (fst maxTuple * snd maxTuple) + +quadraticPrimes :: Int -> Int -> [Int] +quadraticPrimes a b = takeWhile isPrime [n ^ 2 + a * n + b | n <- [0..]] + +isPrime :: Int -> Bool +isPrime 2 = True +isPrime 3 = True +isPrime x + | x < 2 = False + | x `mod` 2 == 0 || x `mod` 3 == 0 = False + | otherwise = divCheck 5 + where divCheck d + | d * d > x = True + | x `mod` d == 0 || x `mod` (d + 2) == 0 = False + | otherwise = divCheck (d + 6) 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) |