Personal tools

Euler problems/21 to 30

From HaskellWiki

< Euler problems(Difference between revisions)
Jump to: navigation, search
(remove comment which didn't apply to the solution given. If you want to improve the solutions, do what HenryLaxen is doing, and actually improve them.)
Line 2: Line 2:
 
Evaluate the sum of all amicable pairs under 10000.
 
Evaluate the sum of all amicable pairs under 10000.
   
Try to do it in Haskell instead of looking up some numbers in OEIS
 
Solution:
 
 
<haskell>
 
<haskell>
 
--http://www.research.att.com/~njas/sequences/A063990
 
--http://www.research.att.com/~njas/sequences/A063990

Revision as of 13:37, 24 February 2008

Contents

1 Problem 21

Evaluate the sum of all amicable pairs under 10000.

--http://www.research.att.com/~njas/sequences/A063990
problem_21 = sum [220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]

2 Problem 22

What is the total of all the name scores in the file of first names?

Solution:

import Data.List
import Data.Char
problem_22 =
    do input <- readFile "names.txt"
       let names = sort $ read$"["++ input++"]"
       let scores = zipWith score names [1..]
       print . show . sum $ scores
  where score w i = (i *) . sum . map (\c -> ord c - ord 'A' + 1) $ w

3 Problem 23

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Solution:

--http://www.research.att.com/~njas/sequences/A048242
import Data.Array 
n = 28124
abundant n = eulerTotient n - n > n
abunds_array = listArray (1,n) $ map abundant [1..n]
abunds = filter (abunds_array !) [1..n]
 
rests x = map (x-) $ takeWhile (<= x `div` 2) abunds
isSum = any (abunds_array !) . rests
 
problem_23 = putStrLn . show . foldl1 (+) . filter (not . isSum) $ [1..n]

4 Problem 24

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Solution:

import Data.List 
 
fac 0 = 1
fac n = n * fac (n - 1)
perms [] _= []
perms xs n= x : perms (delete x xs) (mod n m)
  where m = fac $ length xs - 1
        y = div n m
        x = xs!!y
 
problem_24 = perms "0123456789" 999999

5 Problem 25

What is the first term in the Fibonacci sequence to contain 1000 digits?

Solution:

valid ( i, n ) = length ( show n ) == 1000
 
problem_25 = fst . head . filter valid . zip [ 1 .. ] $ fibs
    where fibs = 1 : 1 : 2 : zipWith (+) fibs ( tail fibs )

6 Problem 26

Find the value of d < 1000 for which 1/d contains the longest recurring cycle.

Solution:

problem_26 = head [a | a<-[999,997..], and [isPrime a, isPrime $ a `div` 2]]

7 Problem 27

Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

Solution:

problem_27 = -(2*a-1)*(a^2-a+41)
  where n = 1000
        m = head $ filter (\x->x^2-x+41>n) [1..]
        a = m-1

8 Problem 28

What is the sum of both diagonals in a 1001 by 1001 spiral?

Solution:

problem_28 = sum (map (\n -> 4*(n-2)^2+10*(n-1)) [3,5..1001]) + 1

9 Problem 29

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Solution:

import Control.Monad
problem_29 = length . group . sort $ liftM2 (^) [2..100] [2..100]

10 Problem 30

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution:

--http://www.research.att.com/~njas/sequences/A052464
problem_30 = sum [4150, 4151, 54748, 92727, 93084, 194979]

I'm sorry, but I find the solution to problem 30 very unsatisfying. I'm using the Euler problems to learn Haskell, so looking up the answer and adding the terms isn't really that helpful. I would like to present the following as a clearer solution that perhaps gives a little more insight into the problem and programming in Haskell. -- Henry Laxen, Feb 20, 2008


problem_30  = sum $ map listToInt (drop 2 ans)
-- we drop 2 because the first two members of the ans are 0 and 1, 
-- which are considered "trivial" solutions and should not count in the sum
  where       maxFirstDigit = (6*9^5 `div` 10^5) + 1
              -- The largest number that can be the sum of fifth powers
              -- is 6*9^5 = 354294, which has 6 digits
              listToInt n = foldl (\x y -> 10*x+y) 0 n
              isSumOfPowers p n = (sum $ map (\x -> x^p) n) == listToInt n
              ans = filter (isSumOfPowers 5) [ [a,b,c,d,e,f] | 
                              a <- [0..maxFirstDigit],
                              b <- [0..9],
                              c <- [0..9],
                              d <- [0..9],
                              e <- [0..9],
                              f <- [0..9] ]