Personal tools

Euler problems

From HaskellWiki

Revision as of 08:13, 27 March 2007 by Vincenz (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

These are the solutions to the problems listed on Project Euler


It is recommended you try them yourself before looking at the solutions as these form good exercises for improving your Haskell-hu.

Contents

1 Problem 1

Add all the natural numbers below 1000 that are multiples of 3 or 5.

Solution:

problem_1 = sum [ x | x <- [1..1000], x `mod` 3 == 0, x `mod` 5 == 0]

2 Problem 2

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

Solution:

problem_2 = sum [ x | x <- fibs, x `mod` 2 == 0]
  where fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

3 Problem 3

Find the largest prime factor of 317584931803.

Solution:

problem_3 = foldr max 0 [ x | x <- [1..(round $ sqrt c)], c `mod` x == 0]
  where c = 317584931803

4 Problem 4

Find the largest palindrome made from the product of two 3-digit numbers.

Solution:

problem_4 = foldr max 0 [ x | y <- [100..999], z <- [100..999], let x = y * z, let s = show x, s == reverse s]

5 Problem 5

What is the smallest number divisible by each of the numbers 1 to 20?

Solution:

problem_5 = head [ x | x <- [2520,5040..], all (\y -> x `mod` y == 0) [1..20]]

6 Problem 6

What is the difference between the sum of the squares and the square of the sums?

Solution:

problem_6 = sum [ x^2 | x <- [1..100]] - (sum [1..100])^2

7 Problem 7

Find the 10001st prime.

Solution:

problem_7 = head $ drop 10000 primes
  where primes = 2:3:..

8 Problem 8

Discover the largest product of five consecutive digits in the 1000-digit number.

Solution:

problem_8 = undefined

9 Problem 9

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

Solution:

problem_9 = head [a*b*c | a <- [1..500], b <- [a..500], c <- [1..(1000-a-b)], a + b + c == 1000,  a^2 + b^2 == c^2]


10 Problem 10

Calculate the sum of all the primes below one million.

Solution:

problem_10 = sum [ p | p <- primes, p < 1000000 ]

11 Problem 11

What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?

Solution:

problem_11 = undefined

12 Problem 12

What is the first triangle number to have over five-hundred divisors?

Solution:

problem_12 = undefined

13 Problem 13

Find the first ten digits of the sum of one-hundred 50-digit numbers.

Solution:

problem_13 = undefined

14 Problem 14

Find the longest sequence using a starting number under one million.

Solution:

problem_14 = undefined

15 Problem 15

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Solution:

problem_15 = undefined

16 Problem 16

What is the sum of the digits of the number 21000?

Solution:

problem_16 = undefined

17 Problem 17

How many letters would be needed to write all the numbers in words from 1 to 1000?

Solution:

problem_17 = undefined

18 Problem 18

Find the maximum sum travelling from the top of the triangle to the base.

Solution:

problem_18 = undefined

19 Problem 19

How many Sundays fell on the first of the month during the twentieth century?

Solution:

problem_19 = undefined

20 Problem 20

Find the sum of digits in 100!

Solution:

problem_20 = undefined

21 Problem 21

Evaluate the sum of all amicable pairs under 10000.

Solution:

problem_21 = undefined

22 Problem 22

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

Solution:

problem_22 = undefined

23 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

24 Problem 24

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

Solution:

problem_24 = undefined

25 Problem 25

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

Solution:

problem_25 = undefined

26 Problem 26

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

Solution:

problem_26 = undefined

27 Problem 27

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

Solution:

problem_27 = undefined

28 Problem 28

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

Solution:

problem_28 = undefined

29 Problem 29

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

Solution:

problem_29 = undefined

30 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

31 Problem 31

Investigating combinations of English currency denominations.

Solution:

problem_31 = undefined

32 Problem 32

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

Solution:

problem_32 = undefined

33 Problem 33

Discover all the fractions with an unorthodox cancelling method.

Solution:

problem_33 = undefined

34 Problem 34

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

Solution:

problem_34 = undefined

35 Problem 35

How many circular primes are there below one million?

Solution:

problem_35 = undefined

36 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

37 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

38 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 = undefined

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?

Solution:

problem_39 = undefined

40 Problem 40

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

Solution:

problem_40 = undefined

41 Problem 41

What is the largest n-digit pandigital prime that exists?

Solution:

problem_41 = undefined

42 Problem 42

How many triangle words can you make using the list of common English words?

Solution:

problem_42 = undefined

43 Problem 43

Find the sum of all pandigital numbers with an unusual sub-string divisibility property.

Solution:

problem_43 = undefined

44 Problem 44

Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.

Solution:

problem_44 = undefined

45 Problem 45

After 40755, what is the next triangle number that is also pentagonal and hexagonal?

Solution:

problem_45 = undefined

46 Problem 46

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Solution:

problem_46 = undefined

47 Problem 47

Find the first four consecutive integers to have four distinct primes factors.

Solution:

problem_47 = undefined

48 Problem 48

Find the last ten digits of 11 + 22 + ... + 10001000.

Solution:

problem_48 = undefined

49 Problem 49

Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other.

Solution:

problem_49 = undefined

50 Problem 50

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Solution:

problem_50 = undefined

51 Problem 51

Find the smallest prime which, by changing the same part of the number, can form eight different primes.

Solution:

problem_51 = undefined

52 Problem 52

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order.

Solution:

problem_52 = undefined

53 Problem 53

How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

Solution:

problem_53 = undefined

54 Problem 54

How many hands did player one win in the game of poker?

Solution:

problem_54 = undefined

55 Problem 55

How many Lychrel numbers are there below ten-thousand?

Solution:

problem_55 = undefined

56 Problem 56

Considering natural numbers of the form, ab, finding the maximum digital sum.

Solution:

problem_56 = undefined

57 Problem 57

Investigate the expansion of the continued fraction for the square root of two.

Solution:

problem_57 = undefined

58 Problem 58

Investigate the number of primes that lie on the diagonals of the spiral grid.

Solution:

problem_58 = undefined

59 Problem 59

Using a brute force attack, can you decrypt the cipher using XOR encryption?

Solution:

problem_59 = undefined

60 Problem 60

Find a set of five primes for which any two primes concatenate to produce another prime.

Solution:

problem_60 = undefined

61 Problem 61

Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.

Solution:

problem_61 = undefined

62 Problem 62

Find the smallest cube for which exactly five permutations of its digits are cube.

Solution:

problem_62 = undefined

63 Problem 63

How many n-digit positive integers exist which are also an nth power?

Solution:

problem_63 = undefined

64 Problem 64

How many continued fractions for N ≤ 10000 have an odd period?

Solution:

problem_64 = undefined

65 Problem 65

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

Solution:

problem_65 = undefined

66 Problem 66

Investigate the Diophantine equation x2 − Dy2 = 1.

Solution:

problem_66 = undefined

67 Problem 67

Using an efficient algorithm find the maximal sum in the triangle?

Solution:

problem_67 = undefined

68 Problem 68

What is the maximum 16-digit string for a "magic" 5-gon ring?

Solution:

problem_68 = undefined

69 Problem 69

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

Solution:

problem_69 = undefined

70 Problem 70

Investigate values of n for which φ(n) is a permutation of n.

Solution:

problem_70 = undefined

71 Problem 71

Listing reduced proper fractions in ascending order of size.

Solution:

problem_71 = undefined

72 Problem 72

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

Solution:

problem_72 = undefined

73 Problem 73

How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Solution:

problem_73 = undefined

74 Problem 74

Determine the number of factorial chains that contain exactly sixty non-repeating terms.

Solution:

problem_74 = undefined

75 Problem 75

Find the number of different lengths of wire can that can form a right angle triangle in only one way.

Solution:

problem_75 = undefined

76 Problem 76

How many different ways can one hundred be written as a sum of at least two positive integers?

Solution:

problem_76 = undefined

77 Problem 77

What is the first value which can be written as the sum of primes in over five thousand different ways?

Solution:

problem_77 = undefined

78 Problem 78

Investigating the number of ways in which coins can be separated into piles.

Solution:

problem_78 = undefined

79 Problem 79

By analysing a user's login attempts, can you determine the secret numeric passcode?

Solution:

problem_79 = undefined

80 Problem 80

Calculating the digital sum of the decimal digits of irrational square roots.

Solution:

problem_80 = undefined

81 Problem 81

Find the minimal path sum from the top left to the bottom right by moving right and down.

Solution:

problem_81 = undefined

82 Problem 82

Find the minimal path sum from the left column to the right column.

Solution:

problem_82 = undefined

83 Problem 83

Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down.

Solution:

problem_83 = undefined

84 Problem 84

In the game, Monopoly, find the three most popular squares when using two 4-sided dice.

Solution:

problem_84 = undefined

85 Problem 85

Investigating the number of rectangles in a rectangular grid.

Solution:

problem_85 = undefined

86 Problem 86

Exploring the shortest path from one corner of a cuboid to another.

Solution:

problem_86 = undefined

87 Problem 87

Investigating numbers that can be expressed as the sum of a prime square, cube, and fourth power?

Solution:

problem_87 = undefined

88 Problem 88

Exploring minimal product-sum numbers for sets of different sizes.

Solution:

problem_88 = undefined

89 Problem 89

Develop a method to express Roman numerals in minimal form.

Solution:

problem_89 = undefined

90 Problem 90

An unexpected way of using two cubes to make a square.

Solution:

problem_90 = undefined

91 Problem 91

Find the number of right angle triangles in the quadrant.

Solution:

problem_91 = undefined

92 Problem 92

Investigating a square digits number chain with a surprising property.

Solution:

problem_92 = undefined

93 Problem 93

Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

Solution:

problem_93 = undefined

94 Problem 94

Investigating almost equilateral triangles with integral sides and area.

Solution:

problem_94 = undefined

95 Problem 95

Find the smallest member of the longest amicable chain with no element exceeding one million.

Solution:

problem_95 = undefined

96 Problem 96

Devise an algorithm for solving Su Doku puzzles.

Solution:

problem_96 = undefined

97 Problem 97

Find the last ten digits of the non-Mersenne prime: 28433 × 27830457 + 1.

Solution:

problem_97 = undefined

98 Problem 98

Investigating words, and their anagrams, which can represent square numbers.

Solution:

problem_98 = undefined

99 Problem 99

Which base/exponent pair in the file has the greatest numerical value?

Solution:

problem_99 = undefined

100 Problem 100

Finding the number of blue discs for which there is 50% chance of taking two blue.

Solution:

problem_100 = undefined

101 Problem 101

Investigate the optimum polynomial function to model the first k terms of a given sequence.

Solution:

problem_101 = undefined

102 Problem 102

For how many triangles in the text file does the interior contain the origin?

Solution:

problem_102 = undefined

103 Problem 103

Investigating sets with a special subset sum property.

Solution:

problem_103 = undefined

104 Problem 104

Finding Fibonacci numbers for which the first and last nine digits are pandigital.

Solution:

problem_104 = undefined

105 Problem 105

Find the sum of the special sum sets in the file.

Solution:

problem_105 = undefined

106 Problem 106

Find the minimum number of comparisons needed to identify special sum sets.

Solution:

problem_106 = undefined

107 Problem 107

Determining the most efficient way to connect the network.

Solution:

problem_107 = undefined

108 Problem 108

Solving the Diophantine equation 1/x + 1/y = 1/n.

Solution:

problem_108 = undefined

109 Problem 109

How many distinct ways can a player checkout in the game of darts with a score of less than 100?

Solution:

problem_109 = undefined

110 Problem 110

Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.

Solution:

problem_110 = undefined

111 Problem 111

Search for 10-digit primes containing the maximum number of repeated digits.

Solution:

problem_111 = undefined

112 Problem 112

Investigating the density of "bouncy" numbers.

Solution:

problem_112 = undefined

113 Problem 113

How many numbers below a googol (10100) are not "bouncy"?

Solution:

problem_113 = undefined

114 Problem 114

Investigating the number of ways to fill a row with separated blocks that are at least three units long.

Solution:

problem_114 = undefined

115 Problem 115

Finding a generalisation for the number of ways to fill a row with separated blocks.

Solution:

problem_115 = undefined

116 Problem 116

Investigating the number of ways of replacing square tiles with one of three coloured tiles.

Solution:

problem_116 = undefined

117 Problem 117

Investigating the number of ways of tiling a row using different-sized tiles.

Solution:

problem_117 = undefined

118 Problem 118

Exploring the number of ways in which sets containing prime elements can be made.

Solution:

problem_118 = undefined

119 Problem 119

Investigating the numbers which are equal to sum of their digits raised to some power.

Solution:

problem_119 = undefined

120 Problem 120

Finding the maximum remainder when (a − 1)n + (a + 1)n is divided by a2.

Solution:

problem_120 = undefined

121 Problem 121

Investigate the game of chance involving coloured discs.

Solution:

problem_121 = undefined

122 Problem 122

Finding the most efficient exponentiation method.

Solution:

problem_122 = undefined

123 Problem 123

Determining the remainder when (pn − 1)n + (pn + 1)n is divided by pn2.

Solution:

problem_123 = undefined

124 Problem 124

Determining the kth element of the sorted radical function.

Solution:

problem_124 = undefined

125 Problem 125

Finding square sums that are palindromic.

Solution:

problem_125 = undefined

126 Problem 126

Exploring the number of cubes required to cover every visible face on a cuboid.

Solution:

problem_126 = undefined

127 Problem 127

Investigating the number of abc-hits below a given limit.

Solution:

problem_127 = undefined

128 Problem 128

Which tiles in the hexagonal arrangement have prime differences with neighbours?

Solution:

problem_128 = undefined

129 Problem 129

Investigating minimal repunits that divide by n.

Solution:

problem_129 = undefined

130 Problem 130

Finding composite values, n, for which n−1 is divisible by the length of the smallest repunits that divide it.

Solution:

problem_130 = undefined

131 Problem 131

Determining primes, p, for which n3 + n2p is a perfect cube.

Solution:

problem_131 = undefined

132 Problem 132

Determining the first forty prime factors of a very large repunit.

Solution:

problem_132 = undefined

133 Problem 133

Investigating which primes will never divide a repunit containing 10n digits.

Solution:

problem_133 = undefined

134 Problem 134

Finding the smallest positive integer related to any pair of consecutive primes.

Solution:

problem_134 = undefined

135 Problem 135

Determining the number of solutions of the equation x2 − y2 − z2 = n.

Solution:

problem_135 = undefined

136 Problem 136

Discover when the equation x2 − y2 − z2 = n has a unique solution.

Solution:

problem_136 = undefined

137 Problem 137

Determining the value of infinite polynomial series for which the coefficients are Fibonacci numbers.

Solution:

problem_137 = undefined

138 Problem 138

Investigating isosceles triangle for which the height and base length differ by one.

Solution:

problem_138 = undefined

139 Problem 139

Finding Pythagorean triangles which allow the square on the hypotenuse square to be tiled.

Solution:

problem_139 = undefined

140 Problem 140

Investigating the value of infinite polynomial series for which the coefficients are a linear second order recurrence relation.

Solution:

problem_140 = undefined

141 Problem 141

Investigating progressive numbers, n, which are also square.

Solution:

problem_141 = undefined

142 Problem 142

Perfect Square Collection

Solution:

problem_142 = undefined

143 Problem 143

Investigating the Torricelli point of a triangle

Solution:

problem_143 = undefined

144 Problem 144

Investigating multiple reflections of a laser beam.

Solution:

problem_144 = undefined

145 Problem 145

How many reversible numbers are there below one-billion?

Solution:

problem_145 = undefined

146 Problem 146

Investigating a Prime Pattern

Solution:

problem_146 = undefined