Problem 63 is an easy one. Let’s get right to it.
The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.
How many n-digit positive integers exist which are also an nth power?
Nothing that cannot be solved in one (word-wrapped) line of Python code.
|
1 2 |
print(sum([1 for j in range(22) for i in range(1, 22) if len(str(i ** j)) == j])) |
Problem 62 is yet another wonderful illustration of the limits of brute force approaches. Here is the problem description.
The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.
Find the smallest cube for which exactly five permutations of its digits are cube.
On the face of it, the approach seems evident: list out all cubes up to a certain upper bound. For each cube, check if the list of cubes has at least 4 other numbers formed by transposing its digits. The lowest number in that set is the result.
I will admit to taking this approach initially. And my program ran and ran and ran… and ran some more before I terminated it.
Why did this seemingly straightforward approach fail?
It failed because of the number of executions. To give you an idea, 1233 is 1860867. The number of permutations of this number is 5040, the factorial of the number of digits. So, just to loop through all permutations of cubes from 1 to 500, we would have over 23.3 million permutations to search through. If our upper bound was 1000 cubes, then the number shoots up to over 204 million permutations!
How can we solve this? Well, it turns out that if we changes the order of steps in our original approach, we can solve this problem in O(n) time. As we generate cubes, we can cache the digits of the cube. Any new cube that we add to our cache will be checked to see if it can be formed by an existing set of digits. Once the number of cubes for a particular set of digits reaches five, we have our answer.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
cubes = [str(i ** 3) for i in range(10000)] d = {} for cube in cubes: digits = tuple(sorted(cube)) # using tuples since lists are non-hashable if digits in d: d[digits] += ',' + cube if d[digits].count(',') == 4: print(d[digits].split(',')[0]) break else: d[digits] = cube |
Problem 61 deals with figurate numbers. Here is the problem statement.
Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:
Triangle P3,n=n(n+1)/2 1, 3, 6, 10, 15, … Square P4,n=n2 1, 4, 9, 16, 25, … Pentagonal P5,n=n(3n−1)/2 1, 5, 12, 22, 35, … Hexagonal P6,n=n(2n−1) 1, 6, 15, 28, 45, … Heptagonal P7,n=n(5n−3)/2 1, 7, 18, 34, 55, … Octagonal P8,n=n(3n−2) 1, 8, 21, 40, 65, … The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.
- The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
- Each polygonal type: triangle (P3,127=8128), square (P4,91=8281), and pentagonal (P5,44=2882), is represented by a different number in the set.
- This is the only set of 4-digit numbers with this property.
Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.
The statement at the end — “only ordered set“ — threw me off a bit, because I took it to mean that the six numbers would be triangular, square, pentagonal and so on in that order. There is no such set, and so I had to go back to the drawing board again.
It was then that point 2 in the problem statement dawned on me. 8128, 2882, and 8281 are cyclical, but 2882 is pentagonal. This makes the problem more interesting. The set of six numbers could be any permutation of the six types of figurates we are dealing with. Thankfully, since we know that there exists only one such set of six numbers, we can stop executing when we reach that set.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
from itertools import permutations def is_cyclical(i, j): return str(i)[2:] == str(j)[:2] def append_to_list(l, e): return_list = [] for i in l: for j in e: if is_cyclical(i[-1], j[0]): k = i[:] k.append(j[0]) return_list.append(k) return return_list def sum_of_cyclical_figurate(): perms = list(permutations([3, 4, 5, 6, 7, 8])) for p in perms: cy1 = append_to_list(figurates[p[0]], figurates[p[1]]) cy2 = append_to_list(cy1, figurates[p[2]]) cy3 = append_to_list(cy2, figurates[p[3]]) cy4 = append_to_list(cy3, figurates[p[4]]) cy5 = append_to_list(cy4, figurates[p[5]]) for x in cy5: if is_cyclical(x[-1], x[0]): return sum(x) figurates = [[]] * 9 figurates[3] = [[n] for n in [i * (i + 1) // 2 for i in range(3, 200)] if 999 < n < 10000] figurates[4] = [[n] for n in [i ** 2 for i in range(3, 100)] if 999 < n < 10000] figurates[5] = [[n] for n in [i * (3 * i - 1) // 2 for i in range(5, 100)] if 999 < n < 10000] figurates[6] = [[n] for n in [i * (2 * i - 1) for i in range(6, 100)] if 999 < n < 10000] figurates[7] = [[n] for n in [i * (5 * i - 3) // 2 for i in range(7, 100)] if 999 < n < 10000] figurates[8] = [[n] for n in [i * (3 * i - 2) for i in range(8, 100)] if 999 < n < 10000] print(sum_of_cyclical_figurate()) |
We encountered number spirals previously in problem 28, and now we revisit them in Problem 58. Here is the problem description.
Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?
We will take the same approach here as we did for solving problem 28. For each new square layer that is added, the numbers at the four corners will be of the form n2, n2 – (n-1), n2 – (n-1)*2, n2 – (n-1)*3. We will therefore check if each of these values (except, of course, n2) is prime and increment a counter accordingly.
My first attempt at solving this problem was using a prime sieve, but even with an upper limit of 100,000,000, we will be unable to reach 10%. So my revised attempt makes use of our trusty old is_prime() function.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
from euler_commons import is_prime prime_count = 0 i = 1 while True: i += 2 n1 = i ** 2 ## never prime n2 = n1 - (i - 1) n3 = n2 - (i - 1) n4 = n3 - (i - 1) for n in [n2, n3, n4]: if is_prime(n): prime_count += 1 prime_pct = prime_count / (2 * i - 1) if prime_pct < 0.1: break print(i) |
Problem 57 is titled Square root convergents. Here is the problem statement.
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…
By expanding this for the first four iterations, we get:
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.
In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?
I found putting pen to paper very helpful in solving this problem. Obviously, trying construct a fraction going to 1000 levels should be enough to scare anyone from trying to solve this using a brute force approach. Let us write down the first few numbers in this series.
My first thought was that the numerators are prime, but seeing 99 in the list blew a hole in that notion. As we continue to look for patterns, we find that the next denominator in the series is merely the sum of the numerator and the denominator of the current number.
5 = 3 + 2; 12 = 7 + 5; 29 = 17 + 12, and so on
The numerators also follow a pattern. If you look at 3, 7, 17, 41, you will notice that the next numerator in the series is twice the current numerator plus the previous numerator.
17 = 7*2 + 3; 41 = 17*2 + 7; 99 = 41*2 + 17, and so on
Now that we have reduced the nth number in the series into its constituent parts, we can set up two lists, one each for the numerator and the denominator, and count for those instances where the numerator has more digits than the denominator.
|
1 2 3 4 5 6 7 8 9 10 11 |
numerators = [3, 7] denominators = [2] count = 0 while count <= 999: count += 1 denominators.append(denominators[count - 1] + numerators[count - 1]) numerators.append(numerators[count] * 2 + numerators[count - 1]) print(sum(1 for i, j in enumerate(numerators) if i < 1000 and len(str(j)) > len(str(denominators[i])))) |
Problem 56 is titled Powerful digit sum. The problem statement is as follows.
A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?
Once you break this problem down to its constituent parts, it becomes very easy to solve.
|
1 2 3 4 5 6 7 8 9 10 |
def get_digital_sum(s): return sum([int(n) for n in list(str(s))]) max_digital_sum = 0 for a in range(1, 100): for b in range(1, 100): max_digital_sum = max(get_digital_sum(a ** b), max_digital_sum) print(max_digital_sum) |
Problem 55 introduces us to Lychrel numbers. Let’s take a look at the problem statement.
If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?
NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.
It is very helpful to know that we could stop checking after 50 attempts, for if we did not have this information, this would be a never-ending quest.
In the code listing below, I get a count of all the non-Lychrel numbers under 10000, and subtract that from 10000 to get the right answer. (While the logic is right, it took me a few tries to get to the right answer, because I did not know what number to use as my lower bound. I started with 10, moved down to 1, and finally to 0 in order to get to the right answer.)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def get_palindrome(n): return int(str(n)[::-1]) def is_palindrome(n): if str(n) == str(n)[::-1]: return True return False upper_limit = 10000 non_lychrel_count = 0 for i in range(upper_limit): current_number = i for k in range(50): total = current_number + get_palindrome(current_number) if is_palindrome(total): non_lychrel_count += 1 break else: current_number = total print(upper_limit - non_lychrel_count) |
Problem 53 is titled Combinatoric selections, and its description is as follows.
There are exactly ten ways of selecting three from five, 12345:
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
In combinatorics, we use the notation, 5C3 = 10.
In general,
nCr = ,where r ≤ n, n! = n×(n−1)×…×3×2×1, and 0! = 1. It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?
Interestingly, this problem only looks for the number of combinations, and the formula is listed in the problem statement itself. We will make use of this and check for values of n ≥ 23. For the given upper bound of n, it is sufficient to check for values of r between 4 and n-3. This is because 100C3 = 100C97 < 1000000.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def factorial(n): if n in factorials: return factorials[n] product = 1 for i in range(2, n + 1): product *= i factorials[n] = product return product factorials = {0: 1, 1: 1} count = sum([1 for n in range(23, 101) for r in range(4, n - 3) if factorial(n) / (factorial(r) * factorial(n - r)) > 1000000]) print(count) |
After an interesting problem 51, we have another easy problem here. Here’s the description of problem 52.
It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.
The code listing below should be self-explanatory, so not much of a commentary is required. I did not take a guess at the answer prior to solving this, but when I saw the output, I had an “Elementary, my dear Watson” moment.
|
1 2 3 4 5 |
for i in range(10, 1000000): if all(sorted(list(str(i))) == sorted(list(str(i * j))) for j in range(2, 7)): print(i) break |
Staying with prime numbers, problem 50 focuses on primes numbers that can be expressed as the sum of consecutive prime numbers. Here is the problem statement.
The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
Since we know the upper limit, we can use the Sieve of Eratosthenes to generate all prime numbers under 1,000,000. Once we have this list, we shall derive the sum of consecutive prime numbers starting with 2 until we reach the upper bound. We will repeat this with subsequent prime numbers, all the while keeping count of the number of successive prime numbers that make up our total.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
upper_limit = 1000000 primes_list = [True] * upper_limit primes_list[0] = False primes_list[1] = False for i in range(2, upper_limit): if primes_list[i]: for j in range(i * i, upper_limit, i): primes_list[j] = False primes = [i for i, j in enumerate(primes_list) if j] primes_set = set(primes) # for quicker comparisons total = 0 max_count = 0 result = 0 for i, j in enumerate(primes): total = j count = 1 for k in range(i + 1, len(primes)): total += primes[k] count += 1 if total >= upper_limit: break if total in primes_set and count > max_count: result = total max_count = count print(result) |