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

BrettGiles (talk | contribs) 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= |
+ | == [http://projecteuler.net/index.php?section=view&id=31 Problem 31] == |

Investigating combinations of English currency denominations. |
Investigating combinations of English currency denominations. |
||

Line 16: | Line 16: | ||

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

− | == [http://projecteuler.net/index.php?section= |
+ | == [http://projecteuler.net/index.php?section=view&id=32 Problem 32] == |

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

Line 24: | Line 24: | ||

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

− | == [http://projecteuler.net/index.php?section= |
+ | == [http://projecteuler.net/index.php?section=view&id=33 Problem 33] == |

Discover all the fractions with an unorthodox cancelling method. |
Discover all the fractions with an unorthodox cancelling method. |
||

Line 32: | Line 32: | ||

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

− | == [http://projecteuler.net/index.php?section= |
+ | == [http://projecteuler.net/index.php?section=view&id=34 Problem 34] == |

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

Line 40: | Line 40: | ||

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

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

How many circular primes are there below one million? |
How many circular primes are there below one million? |
||

Line 48: | Line 48: | ||

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

− | == [http://projecteuler.net/index.php?section= |
+ | == [http://projecteuler.net/index.php?section=view&id=36 Problem 36] == |

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

Line 56: | Line 56: | ||

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

− | == [http://projecteuler.net/index.php?section= |
+ | == [http://projecteuler.net/index.php?section=view&id=37 Problem 37] == |

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

Line 64: | Line 64: | ||

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

− | == [http://projecteuler.net/index.php?section= |
+ | == [http://projecteuler.net/index.php?section=view&id=38 Problem 38] == |

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

Line 83: | Line 83: | ||

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

− | == [http://projecteuler.net/index.php?section= |
+ | == [http://projecteuler.net/index.php?section=view&id=39 Problem 39] == |

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

Line 106: | Line 106: | ||

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

− | == [http://projecteuler.net/index.php?section= |
+ | == [http://projecteuler.net/index.php?section=view&id=40 Problem 40] == |

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

## Revision as of 10:36, 20 July 2007

## 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 = pence 200 [1,2,5,10,20,50,100,200]
where pence 0 _ = 1
pence n [] = 0
pence n denominations@(d:ds)
| n < d = 0
| otherwise = pence (n - d) denominations
+ pence n ds
```

## Problem 32

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

Solution:

```
problem_32 = undefined
```

## Problem 33

Discover all the fractions with an unorthodox cancelling method.

Solution:

```
problem_33 = undefined
```

## Problem 34

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

Solution:

```
problem_34 = undefined
```

## Problem 35

How many circular primes are there below one million?

Solution:

```
problem_35 = undefined
```

## Problem 36

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

Solution:

```
problem_36 = undefined
```

## Problem 37

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

Solution:

```
problem_37 = undefined
```

## Problem 38

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

Solution:

```
problem_38 = maximum $ catMaybes [result | j <- [1..9999],
let p2 = show j ++ show (2*j),
let p3 = p2 ++ show (3*j),
let p4 = p3 ++ show (4*j),
let p5 = p4 ++ show (5*j),
let result
| isPan p2 = Just p2
| isPan p3 = Just p3
| isPan p4 = Just p4
| isPan p5 = Just p5
| otherwise = Nothing]
where isPan s = sort s == "123456789"
```

## 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.

```
problem_39 = head $ perims !! indexMax
where perims = group
$ sort [n*p | p <- pTriples, n <- [1..1000 `div` p]]
counts = map length perims
Just indexMax = findIndex (== (maximum counts)) $ counts
pTriples = [p |
n <- [1..floor (sqrt 1000)],
m <- [n+1..floor (sqrt 1000)],
even n || even m,
gcd n m == 1,
let a = m^2 - n^2,
let b = 2*m*n,
let c = m^2 + n^2,
let p = a + b + c,
p < 1000]
```

## Problem 40

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

Solution:

```
problem_40 = (d 1)*(d 10)*(d 100)*(d 1000)*(d 10000)*(d 100000)*(d 1000000)
where n = concat [show n | n <- [1..]]
d j = Data.Char.digitToInt (n !! (j-1))
```