Euler PROJECT solutions
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
# OR is short circuiting, putting n % 3 before n % 5 can already
# greatly reduce the number of calls
# Using directly a generator instead of list comprehension is always a good thing
return sum(n for n in xrange(1000) if (n % 3 == 0 or n % 5 == 0)) # Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.
# need a dynamic programming approach, using only one two cells array
def sum_fib(n):
"sum up even fibonacci numbers until max"
tot = 0
tup = [1, 1]
while True:
tup[0], tup[1] = sum(tup), tup[0]
if tup[0] > n:
return tot
if tup[0] % 2 == 0:
tot += tup[0]
return sum_fib(4000000)module Main where
import Utils (fib)
main = do
print $ head $ filter (\x -> (length $ show $ fib x) == 1000) [0..]A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
| ID | DESCRIPTION | PY | HS | RB | C | CPP | NB | RESULT | SUBMITTED |
|---|---|---|---|---|---|---|---|---|---|
| <50> | _ | _ | _ | _ | _ | _ | N | ||
| 1 | Add all the natural numbers below one thousand that are multiples of 3 or 5 | X | X | _ | _ | _ | _ | 233168 | Y |
| 2 | Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million. | X | X | _ | ? | _ | _ | 4613732 | Y |
| 3 | What is the largest prime factor of the number 600851475143 ? | _ | X | _ | _ | _ | _ | 6857 | Y |
| 4 | Find largest palindrome made from the product of two 3-digit numbers | X | X | _ | _ | _ | _ | 906609 | Y |
| 5 | smallest divisible by 1..20 | X | X | _ | _ | _ | _ | 232792560 | Y |
| 6 | Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum | X | X | _ | _ | _ | _ | 25164150 | Y |
| 7 | What is the 10001st prime number | X | X | X | _ | _ | _ | 104743 | Y |
| 8 | Find the greatest product of five consecutive digits in the 1000-digit number. | X | X | _ | _ | _ | _ | 40824 | Y |
| 9 | find only Pythagorean triplet for which |
X | X | _ | _ | _ | _ | 31875000 | Y |
| 10 | Calculate the sum of all the primes below two million. | _ | X | _ | _ | _ | _ | 142913828922 | Y |
| 11 | biggest product of 4 digits in matrix | ? | ? | _ | _ | _ | _ | N | |
| 12 | What is the value of the first triangle number to have over five hundred divisors? | X | X | X | _ | _ | _ | 76576500 | Y |
| 13 | Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. | _ | X | _ | _ | _ | _ | 5537376230 | Y |
| 14 | Find the longest sequence using a starting number under one million. | X | ? | _ | X | _ | _ | 837799 | Y |
| 15 | (Just binomial 40 20) | X | X | _ | _ | _ | _ | 137846528820 | Y |
| 16 | What is the sum of the digits of the number 21000? | _ | X | _ | _ | _ | _ | 1366 | Y |
| 17 | If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used? | X | X | _ | _ | _ | _ | 21124 | Y |
| 18 | Find the maximum total from top to bottom of the triangle below: | ? | ? | _ | _ | _ | _ | N | |
| 19 | How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)? | X | ? | _ | _ | _ | _ | 171 | Y |
| 20 | find sum of digits of 100! | X | X | _ | _ | _ | _ | 648 | Y |
| 21 | Evaluate the sum of all amicable pairs under 10000. | X | _ | _ | _ | _ | _ | 31626 | Y |
| 22 | What is the total of all the name scores in the file of first names? | X | _ | _ | _ | _ | _ | 871198282 | Y |
| 23 | Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. | X | ? | _ | _ | _ | ? | 4179871 | Y |
| 24 | What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? | X | _ | _ | _ | _ | X | 2783915460 | Y |
| 25 | What is the first term in the Fibonacci sequence to contain 1000 digits? | X | ? | _ | _ | _ | _ | 4872 | Y |
| 26 | Find the value of d 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part. | ? | _ | _ | _ | _ | _ | N | |
| 28 | What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way? | X | _ | _ | _ | _ | _ | 669171001 | Y |
| 29 | How many distinct terms are in the sequence generated by ab for 2 a 100 and 2 b 100? | X | _ | _ | _ | _ | _ | 9183 | Y |
| 30 | Find the sum of all the numbers that can be written as the sum of fifth powers of their digits. | X | _ | _ | _ | _ | _ | 443839 | Y |
| 33 | If the product of these four fractions is given in its lowest common terms, find the value of the denominator. | ? | ? | _ | _ | _ | _ | N | |
| 34 | Find the sum of all numbers which are equal to the sum of the factorial of their digits. | X | X | _ | _ | _ | _ | 40730 | Y |
| 35 | How many circular primes are there below one million? | X | _ | _ | _ | _ | _ | 55 | Y |
| 36 | Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2. | _ | X | _ | _ | _ | _ | 872187 | Y |
| 37 | Find the sum of the only eleven primes that are both truncatable from left to right and right to left | X | ? | ? | _ | _ | _ | 748317 | Y |
| 38 | What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n 1? | X | _ | _ | _ | _ | _ | 918273645 | Y |
| 39 | For which value of p ≤ 1000, is the number of solutions maximised? | ? | ? | _ | _ | _ | _ | N | |
| 40 | If dn represents the nth digit of the fractional part, find the value of the following expression. | ? | _ | _ | _ | _ | _ | N | |
| 41 | What is the largest n-digit pandigital prime that exists? | X | _ | ? | _ | _ | _ | 7652413 | Y |
| 42 | two-thousand common English words, how many are triangle words? | X | _ | _ | _ | _ | _ | 162 | Y |
| 44 | Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D =Pk Pj is minimised; what is the value of D? | X | X | _ | _ | _ | _ | 5482660 | Y |
| 48 | _ | X | _ | _ | _ | _ | 9110846700 | Y | |
| 52 | Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits. | X | X | _ | _ | _ | _ | 142857 | Y |
| 56 | Considering natural numbers of the form, ab, where a, b 100, what is the maximum digital sum? | X | _ | _ | ? | _ | _ | 972 | Y |
| 55 | How many Lychrel numbers are there below ten-thousand? | X | _ | _ | _ | _ | _ | 249 | Y |
| 92 | How many starting numbers below ten million will arrive at 89? | ? | _ | _ | X | _ | _ | 8581146 | Y |
| 59 | Your task has been made easy, as the encryption key consists of three lower case characters. Using cipher1.txt (right click and ‘Save Link/Target As…’), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text. | ? | _ | _ | _ | _ | _ | N | |
| 53 | How many, not necessarily distinct, values of nCr, for 1 n 100, are greater than one-million? | ? | _ | _ | ? | _ | X | N | |
| 32 | Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital. | ? | _ | _ | _ | _ | _ | N | |
| 99 | determine which line number has the greatest numerical value. | X | _ | _ | _ | _ | _ | 709 | Y |
| 54 | How many hands the player 1 wins? | ? | _ | _ | _ | _ | _ | N | |
| TOT | _ | _ | _ | _ | _ | _ | N |