# Difference between revisions of "Euler problems/31 to 40"

Henrylaxen (talk | contribs) |
Henrylaxen (talk | contribs) |
||

Line 104: | Line 104: | ||

problem_34 = sum [145, 40585] |
problem_34 = sum [145, 40585] |
||

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

+ | |||

+ | Once again, I find this kind of solution most ''unilluminating'', and would like to offer my own, in the interest of people using the projectEuler problems to teach themselves Haskell -- HenryLaxen 2008-02-23 |
||

+ | |||

+ | <haskell> |
||

+ | import Data.Array |
||

+ | import Data.List |
||

+ | |||

+ | {- |
||

+ | |||

+ | The key comes in realizing that N*9! < 10^N when N >= 9, so we |
||

+ | only have to check up to 9 digit integers. The other key is |
||

+ | that addition is commutative, so we only need to generate |
||

+ | combinations (with duplicates) of the sums of the various |
||

+ | factorials. These sums are the only potential "curious" sums. |
||

+ | |||

+ | -} |
||

+ | |||

+ | fac n = a!n |
||

+ | where a = listArray (0,9) (1:(scanl1 (*) [1..9])) |
||

+ | |||

+ | -- subsets of size k, including duplicates |
||

+ | combinationsOf 0 _ = [[]] |
||

+ | combinationsOf _ [] = [] |
||

+ | combinationsOf k (x:xs) = map (x:) |
||

+ | (combinationsOf (k-1) (x:xs)) ++ combinationsOf k xs |
||

+ | |||

+ | intToList n = reverse $ unfoldr |
||

+ | (\x -> if x == 0 then Nothing else Just (x `mod` 10, x `div` 10)) n |
||

+ | |||

+ | isCurious (n,l) = sort (intToList n) == l |
||

+ | |||

+ | -- Turn a list into the sum of the factorials of the digits |
||

+ | factorialSum l = foldr (\x y -> (fac x) + y) 0 l |
||

+ | |||

+ | possiblyCurious = map (\z -> (factorialSum z,z)) |
||

+ | curious n = filter isCurious $ possiblyCurious $ combinationsOf n [0..9] |
||

+ | problem_34 = sum $ (fst . unzip) $ concatMap curious [2..9] |
||

+ | </haskell> |
||

+ | (The wiki formatting is messing up the unzip">unzip line above, it is correct in the version I typed in. It should of course just be fst . unzip) |
||

+ | |||

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

## Revision as of 20:21, 23 February 2008

## Contents

## Problem 31

Investigating combinations of English currency denominations.

Solution:

This is the naive doubly recursive solution. Speed would be greatly improved by use of memoization, dynamic programming, or the closed form.

```
problem_31 = ways [1,2,5,10,20,50,100,200] !!200
where ways [] = 1 : repeat 0
ways (coin:coins) =n
where n = zipWith (+) (ways coins) (take coin (repeat 0) ++ n)
```

A beautiful solution, making usage of laziness and recursion to implement a dynamic programming scheme, blazingly fast despite actually generating the combinations and not only counting them :

```
coins = [1,2,5,10,20,50,100,200]
combinations = foldl (\without p ->
let (poor,rich) = splitAt p without
with = poor ++ zipWith (++) (map (map (p:)) with)
rich
in with
) ([[]] : repeat [])
problem_31 = length $ combinations coins !! 200
```

The above may be *a beautiful solution*, but I couldn't understand it without major mental gymnastics. I would like to offer the following, which I hope will be easier to follow for ordinary *mentats* -- HenryLaxen 2008-02-22

```
coins = [1,2,5,10,20,50,100,200]
withcoins 1 x = [[x]]
withcoins n x = concatMap addCoin [0 .. x `div` coins!!(n-1)]
where addCoin k = map (++[k]) (withcoins (n-1) (x - k*coins!!(n-1)) )
problem_31 = length $ withcoins (length coins) 200
```

## Problem 32

Find the sum of all numbers that can be written as pandigital products.

Solution:

```
import Control.Monad
combs 0 xs = [([],xs)]
combs n xs = [(y:ys,rest) | y <- xs, (ys,rest) <- combs (n-1) (delete y xs)]
l2n :: (Integral a) => [a] -> a
l2n = foldl' (\a b -> 10*a+b) 0
swap (a,b) = (b,a)
explode :: (Integral a) => a -> [a]
explode = unfoldr (\a -> if a==0 then Nothing else Just . swap $ quotRem a 10)
pandigiticals =
nub $ do (beg,end) <- combs 5 [1..9]
n <- [1,2]
let (a,b) = splitAt n beg
res = l2n a * l2n b
guard $ sort (explode res) == end
return res
problem_32 = sum pandigiticals
```

## Problem 33

Discover all the fractions with an unorthodox cancelling method.

Solution:

```
import Data.Ratio
problem_33 = denominator . product $ rs
{-
xy/yz = x/z
(10x + y)/(10y+z) = x/z
9xz + yz = 10xy
-}
rs = [(10*x+y)%(10*y+z) | x <- t,
y <- t,
z <- t,
x /= y ,
(9*x*z) + (y*z) == (10*x*y)]
where t = [1..9]
```

That is okay, but why not let the computer do the *thinking* for you? Isn't this a little more directly expressive of the problem? -- HenryLaxen 2008-02-34

```
import Data.Ratio
problem_33 = denominator $ product
[ a%c | a<-[1..9], b<-[1..9], c<-[1..9],
isCurious a b c, a /= b && a/= c]
where isCurious a b c = ((10*a+b)%(10*b+c)) == (a%c)
```

## Problem 34

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Solution:

```
--http://www.research.att.com/~njas/sequences/A014080
problem_34 = sum [145, 40585]
```

Once again, I find this kind of solution most *unilluminating*, and would like to offer my own, in the interest of people using the projectEuler problems to teach themselves Haskell -- HenryLaxen 2008-02-23

```
import Data.Array
import Data.List
{-
The key comes in realizing that N*9! < 10^N when N >= 9, so we
only have to check up to 9 digit integers. The other key is
that addition is commutative, so we only need to generate
combinations (with duplicates) of the sums of the various
factorials. These sums are the only potential "curious" sums.
-}
fac n = a!n
where a = listArray (0,9) (1:(scanl1 (*) [1..9]))
-- subsets of size k, including duplicates
combinationsOf 0 _ = [[]]
combinationsOf _ [] = []
combinationsOf k (x:xs) = map (x:)
(combinationsOf (k-1) (x:xs)) ++ combinationsOf k xs
intToList n = reverse $ unfoldr
(\x -> if x == 0 then Nothing else Just (x `mod` 10, x `div` 10)) n
isCurious (n,l) = sort (intToList n) == l
-- Turn a list into the sum of the factorials of the digits
factorialSum l = foldr (\x y -> (fac x) + y) 0 l
possiblyCurious = map (\z -> (factorialSum z,z))
curious n = filter isCurious $ possiblyCurious $ combinationsOf n [0..9]
problem_34 = sum $ (fst . unzip) $ concatMap curious [2..9]
```

(The wiki formatting is messing up the unzip">unzip line above, it is correct in the version I typed in. It should of course just be fst . unzip)

## Problem 35

How many circular primes are there below one million?

Solution: millerRabinPrimality on the Prime_numbers page

```
--http://www.research.att.com/~njas/sequences/A068652
isPrime x
| x==1 = False
| x==2 = True
| x==3 = True
| otherwise = millerRabinPrimality x 2
permutations n = take l
. map (read . take l)
. tails
. take (2*l-1)
. cycle $ s
where s = show n
l = length s
circular_primes [] = []
circular_primes (x:xs)
| all isPrime p = x : circular_primes xs
| otherwise = circular_primes xs
where p = permutations x
x = [1,3,7,9]
dmm = foldl (\x y->x*10+y) 0
xx n = map dmm (replicateM n x)
problem_35 = (+13) . length . circular_primes
$ [a | a <- concat [xx 3,xx 4,xx 5,xx 6], isPrime a]
```

## Problem 36

Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

Solution:

```
--http://www.research.att.com/~njas/sequences/A007632
problem_36 = sum [0, 1, 3, 5, 7, 9, 33, 99, 313, 585, 717,
7447, 9009, 15351, 32223, 39993, 53235,
53835, 73737, 585585]
```

## Problem 37

Find the sum of all eleven primes that are both truncatable from left to right and right to left.

Solution:

```
-- isPrime in p35
-- http://www.research.att.com/~njas/sequences/A020994
problem_37 = sum [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
```

## Problem 38

What is the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 1, 2, 3, ... ?

Solution:

```
import Data.List
mult n i vs
| length (concat vs) >= 9 = concat vs
| otherwise = mult n (i+1) (vs ++ [show (n * i)])
problem_38 = maximum . map read . filter ((['1'..'9'] ==) .sort)
$ [mult n 1 [] | n <- [2..9999]]
```

## Problem 39

If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

Solution: We use the well known formula to generate primitive Pythagorean triples. All we need are the perimeters, and they have to be scaled to produce all triples in the problem space.

```
--http://www.research.att.com/~njas/sequences/A046079
problem_39 = let t = 3*5*7
in floor(2^floor(log(1000/t)/log 2)*t)
```

## Problem 40

Finding the nth digit of the fractional part of the irrational number.

Solution:

```
--http://www.research.att.com/~njas/sequences/A023103
problem_40 = product [1, 1, 5, 3, 7, 2, 1]
```