Personal tools

Euler problems/21 to 30

From HaskellWiki

< Euler problems(Difference between revisions)
Jump to: navigation, search
m
m (Corrected the links to the Euler project)
Line 1: Line 1:
 
[[Category:Programming exercise spoilers]]
 
[[Category:Programming exercise spoilers]]
== [http://projecteuler.net/index.php?section=problems&id=21 Problem 21] ==
+
== [http://projecteuler.net/index.php?section=view&id=21 Problem 21] ==
 
Evaluate the sum of all amicable pairs under 10000.
 
Evaluate the sum of all amicable pairs under 10000.
   
Line 13: Line 13:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=22 Problem 22] ==
+
== [http://projecteuler.net/index.php?section=view&id=22 Problem 22] ==
 
What is the total of all the name scores in the file of first names?
 
What is the total of all the name scores in the file of first names?
   
Line 24: Line 24:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=23 Problem 23] ==
+
== [http://projecteuler.net/index.php?section=view&id=23 Problem 23] ==
 
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
 
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
   
Line 32: Line 32:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=24 Problem 24] ==
+
== [http://projecteuler.net/index.php?section=view&id=24 Problem 24] ==
 
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
 
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
   
Line 45: Line 45:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=25 Problem 25] ==
+
== [http://projecteuler.net/index.php?section=view&id=25 Problem 25] ==
 
What is the first term in the Fibonacci sequence to contain 1000 digits?
 
What is the first term in the Fibonacci sequence to contain 1000 digits?
   
Line 56: Line 56:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=26 Problem 26] ==
+
== [http://projecteuler.net/index.php?section=view&id=26 Problem 26] ==
 
Find the value of d < 1000 for which 1/d contains the longest recurring cycle.
 
Find the value of d < 1000 for which 1/d contains the longest recurring cycle.
   
Line 71: Line 71:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=27 Problem 27] ==
+
== [http://projecteuler.net/index.php?section=view&id=27 Problem 27] ==
 
Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
 
Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
   
Line 79: Line 79:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=28 Problem 28] ==
+
== [http://projecteuler.net/index.php?section=view&id=28 Problem 28] ==
 
What is the sum of both diagonals in a 1001 by 1001 spiral?
 
What is the sum of both diagonals in a 1001 by 1001 spiral?
   
Line 101: Line 101:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=29 Problem 29] ==
+
== [http://projecteuler.net/index.php?section=view&id=29 Problem 29] ==
 
How many distinct terms are in the sequence generated by a<sup>b</sup> for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
 
How many distinct terms are in the sequence generated by a<sup>b</sup> for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
   
Line 109: Line 109:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=30 Problem 30] ==
+
== [http://projecteuler.net/index.php?section=view&id=30 Problem 30] ==
 
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.
 
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.
   

Revision as of 10:34, 20 July 2007

Contents

1 Problem 21

Evaluate the sum of all amicable pairs under 10000.

Solution: This is a little slow because of the naive method used to compute the divisors.

problem_21 = sum [m+n | m <- [2..9999], let n = divisorsSum ! m, amicable m n]
    where amicable m n = m < n && n < 10000 && divisorsSum ! n == m
          divisorsSum = array (1,9999)
                        [(i, sum (divisors i)) | i <- [1..9999]]
          divisors n = [j | j <- [1..n `div` 2], n `mod` j == 0]

2 Problem 22

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

Solution:

-- apply to a list of names
problem_22 :: [String] -> Int
problem_22 = sum . zipWith (*) [ 1 .. ] . map score
    where score = sum . map ( subtract 64 . ord )

3 Problem 23

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

Solution:

problem_23 = undefined

4 Problem 24

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

Solution:

perms [] = [[]]
perms xs = do
    x <- xs
    map ( x: ) ( perms . delete x $ xs )
 
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 = fst $ maximumBy (\a b -> snd a `compare` snd b)
                            [(n,recurringCycle n) | n <- [1..999]]
    where  recurringCycle d = remainders d 10 []
           remainders d 0 rs = 0
           remainders d r rs = let r' = r `mod` d
                               in case findIndex (== r') rs of
                                    Just i  -> i + 1
                                    Nothing -> remainders d (10*r') (r':rs)

7 Problem 27

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

Solution:

problem_27 = undefined

8 Problem 28

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

Solution:

corners :: Int -> (Int, Int, Int, Int)
corners i = (n*n, 1+(n*(2*m)), 2+(n*(2*m-1)), 3+(n*(2*m-2))) 
    where m = (i-1) `div` 2
          n = 2*m+1
 
sumcorners :: Int -> Int
sumcorners i = a+b+c+d where (a, b, c, d) = corners i
 
sumdiags :: Int -> Int
sumdiags i | even i    = error "not a spiral"
           | i == 3    = s + 1
           | otherwise = s + sumdiags (i-2) 
           where s = sumcorners i
 
problem_28 = sumdiags 1001

9 Problem 29

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

Solution:

problem_29 = length . group . sort $ [a^b | a <- [2..100], b <- [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:

problem_30 = undefined