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
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))