*Question: Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.*

This is simply a case of looping and creating a function that tests if a given input is pandigital. Again, the upper bounds on the for loops were a bit tricky. I set the limit at 10,000 since the total number of digits cannot exceed 9, so the maximum situation that can occur is 9999 * 1 = 9999 (9 digits).

Here’s the code:

def isPandigital19(s): return '0' not in s and len(s) == 9 == len(set(s)) result = set() for n in range(2, 10000): for m in range(2, 10000): if n * m > 10000: continue elif isPandigital19(str(n)+str(m)+str(n*m)): result.add(n*m) print(sum(result))

So the result is stored in a set, since there could be duplicate multiplicand/multiplier/product pandigitals. We iterate through the possibilities using two for loops, and quickly check if the product is greater than 10,000 to skip to the next iteration. This is because if the product is over 10,000, the total digits of it and its factors are guaranteed to be over 9 digits. Only then do we check if the identity is pandigital using the function *isPandigital19()*.

This function essentially checks the to see if the length of the string (of the identity) is 9 (9 digits), and if there are no duplicates by also testing the set of the string. However, 0 cannot be a digit in the identity since we’re only concerned with the digits 1-9, so that test is also included in the function. The function returns a true or false value, and the rest is self-explanatory.

*Answer: 45228*

]]>

*Question: How many different ways can £2 be made using any number of coins?*

My solution to this wasn’t very pretty — just look at the monstrous for loop below.

result = 2 for b in range(2): for c in range(5): if 100*b + 50*c > 200: continue for d in range(11): if 100*b + 50*c + 20*d > 200: continue for e in range(21): if 100*b + 50*c + 20*d + 10*e > 200: continue for f in range(41): if 100*b + 50*c + 20*d + 10*e + 5*f > 200: continue for g in range(101): if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g > 200: continue for h in range(201): if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g + h == 200: result += 1 print(result)

Yeah…zero points for style there. I know for a fact that there is a “clever” way of solving this problem, but its explanation was pretty over my head. Essentially this code works by trying (almost) every combination of coins possible and testing it to see if its value is 200. This is slightly streamlined by initially considering two possibilities, 200 and 100 + 100, so that there are less total calculations. This is the reason why *result* is initialized to 2 and there is no loop for the 200 coin. The number of calculations is also reduced by continuing (skipping to the next iteration) the for loop whenever the current value is greater than 200, which also skips all corresponding inner nested loops.

This slight detail allows us to skip most of the 1,922,707,710 calculations needed for a complete brute force solution, and returns an answer in a reasonable amount of time.

*Answer: 73682*

]]>

*Question: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.*

The trickiest part of this problem was determining a limit past which it is certain that no numbers can satisfy the conditions. The rest is more or less simple brute forcing and equality checking.

The limit can be found this way. It is impossible for a 9 digit number to be written as the sum of the fifth powers of its digits simply because the sum doesn’t reach that high. The lowest 9 digit number is 100,000,000, but the highest possible sum is 9*95 = 531441. Following this logic, 8 and 7 digit numbers are also impossible. However, a 6 digit number could potentially be written as the sum of the fifth powers of its digits: 100,000 < 6*95 = 354,294. Therefore, the largest number we need to test is 354,294 since any number after that will be impossible to reach with these sums.

Here’s the code:

result = 0 for x in range(2, 354295): # 6*9^5 + 1 digits = [int(n)**5 for n in str(x)] if sum(digits) == x: result += x print(result)

The variable *result* is initialized to 0. We generate *x*‘s up until the limit, and find the fifth power of each of its digits using list comprehension. If the sum of these values is equal to the number itself, we add the number to the result. Once the loop finished the result is printed.

*Answer: 443839*

]]>

*How many distinct terms are in the sequence generated by a^b for 2<=a<=100 and 2<=b<=100?*

This is remarkably simple in Python.

Here it is:

result = {a**b for a in range(2, 101) for b in range(2, 101)} print(len(result))

A set is used to keep track of unique elements (note the curly braces), and a list comprehension with two for loops are used to generate the values. The length of the set is printed at the end.

*Answer: 9183*

]]>

*Question: What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral?*

My initial solution to this problem was quite different from my final one. I intended to make the spiral into a one-dimensional list, and since the diagonal digits occur at a regular rate, a couple of counters could keep track of which position was actually on a diagonal. This was slightly more complicated than I foresaw, but it did succeed in the end, albeit very messily. Looking through the answer forums, I discovered another way of approaching this problem. The spiral could be seen as concentric squares, and all that was needed was to find the corners of each square.

Take a look:

result = 1 for i in range(3, 1002, 2): result += (i*i) + (i*i-i+1) + (i*i-2*i+2) + (i*i-3*i+3) print(result)

I think you’ll agree that this is rather succinct (perhaps not the *result +=* line, but I did not combine the expressions algebraically for sake of clarity). Viewing the spiral as a bunch of concentric squares, the dimensions are 1×1, 3×3, 5×5 … 1001×1001. It is unnecessary to calculate the value of the center of the square, which is why the for loop starts with (a square of length) 3 and *result* is initialized to 1. It is incremented by two, and you can see why by looking at the dimensions of the squares.

Now we have to find the values of the corners of a square with dimensions *i*x*i*. It’s important to note that the square is still technically constructed from a spiral; the numbers start from the center and spiral outward; they do not start on the border of the square. If the square is constructed in this manner, then we know somewhat intuitively that the top right corner is simply *i2*, or *i*i*. The top left corner’s equation was pretty much found by guess and check. The bottom two corners were slightly harder to find just by looking at the pattern of numbers, so I resorted to using the ever-handy regression function on my TI-84. These two equations were found to be i2-2i+2 and i2-3i+3, respectively. We add all of these corners into the *result* variable, and print at the end.

*Answer: 669171001*

]]>

*Question: Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.*

I’m not exactly sure why, but this was a pretty fun problem to do. Basically I just had to brute force my way through this problem, and it actually ran much faster than I anticipated.

Take a look:

def isPrime(x): divisor = 3 limit = int(x**0.5) + 1 while divisor < limit: if x % divisor == 0: return False else: divisor += 2 return True result = [0, 0, 0] # a, b, counter for a in range(-999, 1000): for b in range(-999, 1000): n = 0 while True: x = n*n + a*n + b if x > 0 and isPrime(x): n += 1 else: if n > result[2]: result = [a, b, n] break print(result[0]*result[1])

As you can see, I reused the ever-so-popular *isPrime()* function for this problem. We use two for loops to test every combination of coefficients, and initialize n, the independent variable of the quadratic, to 0. We then continue to generate values of the quadratic until we reach one that isn’t prime. The length of the chain generated is tested to see if it’s greater then the previous longest chain, and if it is we overwrite the variable *result*.

*Answer: -59231*

]]>

*Question: Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.*

I had to find a clever solution to this problem, mainly because I didn’t know how to brute force it (maybe I should’ve read this). I learn something new everyday, and by solving this problem I discovered a neat application for Fermat’s Little Theorem.

Take a look:

def lengthDecimal(n): # finds length of recurring cycle of 1/n while n % 2 == 0: n //= 2 while n % 5 == 0: n //= 5 for x in range(1, n): if (10**x - 1) % n == 0: return x return 0 result = [0, 0] # number, length for n in range(2, 1000): if lengthDecimal(n) > result[1]: result = [n, lengthDecimal(n)] print(result)

Any multiple of 2 or 5 in the denominator will yield the same number of decimal places, so that is the first step of the *lengthDecimal()* function. If a prime number is in the denominator, we can use a trick based on Fermat’s Little Theorem to calculate the length of the recurring decimal cycle. The application is as follows: 1/n has a cycle of x digits if (10x – 1) % n = 0. Given n, it’s a simple matter of guess and check to find x.

This function is used to test numbers up to 1000.

*Answer: 983*

]]>

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

This was pretty simple, all we need to do is generate Fibonacci terms and check the length of each one. We also need a counter to keep track of what term we’re on.

a = b = n = 1 counter = 2 while len(str(n)) != 1000: counter += 1 n = a + b a, b = b, n print(counter)

*a*, *b*, and *n* are variables used to generate the Fibonacci sequence. Since Project Euler defines the first term of the Fibonacci sequence as 1 rather than 0, we initialize the counter to 2, since the first term we calculate (2) will be the 3rd term. The rest is self-explanatory.

*Answer: 4782*

]]>

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

This was pretty simple using the *itertools* module. Just to clarify, a permutation is a combination of items where the order does matter, which applies in this case because we’re dealing with numbers.

import itertools print([x for x in itertools.permutations('0123456789', 10)][999999])

This creates a list of each permutation, and we don’t need to sort it because *itertools* creates each permutation in order of increasing value, since *‘0123456789’* is in order of increasing value. The second argument for *permutations()*, *10*, isn’t explicitly needed since it will default to the length of the iterable, but this makes it a bit clearer. The millionth lexicographic permutation will be 999,999th in the list, so that’s the position we print.

The printed statement is not pretty, but it works. I’m not exactly sure why *itertools.permutations()* returns a list of the (string) digits of each permutation, instead of just a string for each permutation.

*Answer: 2783915460*

]]>

*Question: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.*

This problem was rather complicated…it took me a while to come up with an efficient way of solving it. Bits of this code are actually the result of reading other people’s solutions to improve my own.

Take a look:

def abundantNumberGen(limit): # returns list of abundant numbers up to limit numbers = [] for x in range(1, limit): if sum(properFactors(x)) > x: numbers.append(x) return numbers def properFactors(n): # returns list of proper factors of a number factors = [1] # 1 is automatically a factor for x in range(2, int(n**0.5)+1): if n % x == 0: factors.extend([x, n/x]) if n**0.5 == int(n**0.5): # important! must remove the extra square root if n is a perfect square factors.remove(n**0.5) return factors result = list(range(28123)) # list of numbers up to 28123; result[12] = 12, result[28122] = 28122 abundantNumbers = abundantNumberGen(28123) for n in abundantNumbers: for m in abundantNumbers: if n + m < 28123: result[n + m] = 0 # result[100] = 100 --> result[100] = 0 print(sum(result))

Instead of directly reading the run code first, let’s analyze the functions first for a change of pace.

def properFactors(n): # returns list of proper factors of a number factors = [1] # 1 is automatically a factor for x in range(2, int(n**0.5)+1): if n % x == 0: factors.extend([x, n/x]) if n**0.5 == int(n**0.5): # important! must remove the extra square root if n is a perfect square factors.remove(n**0.5) return factors

This function is used repeatedly in calculating the solution, so any increase in efficiency here would significantly reduce the run time overall. This was done by automatically setting one as a factor, and only test-dividing up to the square root of the number. The factors found are stored in a list, and every time we find a factor, we add its corresponding factors (e.g. the number is 10, we find 2 and then find 5) to the list. It’s extremely important to remove the duplicate square root factor if the number is a perfect square; I initially overlooked this fact and ended up with a wrong answer. This is a more general version of the *D(n)* function used in problem 21.

def abundantNumberGen(limit): # returns list of abundant numbers up to limit numbers = [] for x in range(1, limit): if sum(properFactors(x)) > x: numbers.append(x) return numbers

This function returns a list abundant numbers up to a specified limit, directly using the definition of an abundant number. We test if the sum of a number’s proper divisors is greater than the number itself, and if true, we append it to the list.

result = list(range(28123)) # list of numbers up to 28123; result[12] = 12, result[28122] = 28122 abundantNumbers = abundantNumberGen(28123) for n in abundantNumbers: for m in abundantNumbers: if n + m < 28123: result[n + m] = 0 # result[100] = 100 --> result[100] = 0 print(sum(result))

Now let’s look at the run code. The first line here was adapted from another solution I found, since I thought it was an extremely clever and efficient way of tackling this problem. Line 1 creates a list where the elements are equal to their indexes, i.e. *list[10] = 10, list[124] = 124*, simple but very useful. We generate abundant numbers up to the specified limit of 28123 (because we want a sum of abundant numbers that is less than 28123). We then test every combination of two abundant numbers, using two for loops, and if the result is less than 28123, i.e. a number that can be expressed as the sum of two abundant numbers, we set that element of the list to zero. When this finishes, all the numbers in the list that can be expressed as a sum of abundant numbers will be zero, and we can simply sum the remaining to find the solution.

*Answer: 4179871*

]]>