Project Euler and Solutions

Project Euler is a set of challenging problems that require mathematical and computer programming skills to solve. In this post, I show my approches and solutions to three problems from the Euler Project. Out of the problems I chose, one have been solved by fewer than 25,000 people, one fewer than 100,000 people, and one fewer than 500,000 people.

Largest Palindrome Product

The Largest palindrome product is Problem 4 from Project Euler. It is solved by 489,906 people as of September 1, 2021. The question is:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

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

My approach to this problem roughly consist of three parts. First, looping through all pairs potential 3-digit numbers to find the product. Second, check whether the product is a palindrome. Third, if the product is indeed a palindrome, check if it is the largest. Then, we have a solution.

1. For-loops

We create two for-loops for loop through all 3-digit number pairs, and take the product of these two numbers. 3-digit numbers range from 100 to 999. This sets the lower and upper bounds of the outer loop. Since we are only interested in unique pairs, therefore, the inner loop starts from the current number in the outer loop. By doing this, we avoid redundancy and speed up the performance. Notice, the for-loops loops numbers in a descending order. Since we are loops through all pairs, whether we are doing the for-loops in ascending and descending order wouldn’t have an impact on the code efficiency.

Here is the implementation:

2. Palindrome Check

After obtaining the product, it is time to check whether the product is a palindrome. A palindrome is defined as a number that read the same both ways. For example, 161, 9889 are palindromes, because they are the same whether we read them from left to right or from right to left.

There are many different ways to check whether a number is a palindrome in Python. Here, I convert the integer to string data type. Then, I use the negative stride in Python string indexing to reverse the order of the digit. Following that, I check whether the reversed number is equal to the original number.

Here is the code:

3. Largest Palindrome Check

For each palindrome we find, we check if it is larger than the previous palindrome. If it does, we want to overwrite the largest palindrome found. This way, when the for-loops finish, we are certain that we have obtain the correct answer.

To implement this in code, we first initiate a tuple with length three. The first and second element of the tuple are the two multiples. And the third element is the product of these two numbers. We overwrite this variable when the new palindrome is greater than the old one.

Here is how to write this in code:

And that’s it. After implementing the code, you’ll find the solution. Here is the complete code:

Digit Factorials

The Digit factorials is Problem 34 in Project Euler. It was solved by 95,102 people as of September 1, 2021. The question is

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

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

Note: As 1! = 1 and 2! = 2 are not sums they are not included.

My approach to this question is as follows. First, a for-loop for loop over all possible values. Second, for each value in the for-loop, we calculate the sum of the factorials for each digit. Third, we check to see if the sum equals to original number. Finally, after finding all numbers that satisfy the requirements, we take the sum to produce the final result. There is the breakdown of each step.

1. For-loop

The trickiest part of this approach to set a reasonable lower and upper bound for the search. For the lower bound, since the question prompt excludes 1 and 2, therefore, it is reasonable to set the lower bound to 3. Setting the upper bound requires some more thinking. Since the largest value any digit can take is 9, let’s look at 9! = 362,880, which has 6 digits. The largest 6-digit number is 999,999. The sum of the factorials for each digit for 999,999 is 2,177,280. The sum has 7 digit which is significantly larger than the original number. From here, we see that 6* 9! Is greater than 999,999. Therefore, it is reasonable to assume that numbers which are equal to the sum of the factorial of their digits is bounded by 999,999.

2. Sum of the factorials of digits

The second step in the process is to calculate the sum of the factorials of each digit and compare the sum with the original number. To do this, we need to first break the integer into single composite digits. Then, loop over each digits and sum up the factorial values. Here is how to implement this in code.

Notice that I pre-calculate the factorials from 0 to 9 in advance to speed up the performance. Then I convert the integer to string type, and use Python list comprehension to break the integer into single digit. Following that I use a for-loop for sum up the factorials. After obtaining the sum, we append the number to the solution list if the sum equal to the original number.

3. Sum of the integers

Finally, after we have the list that contains all numbers which are equal to the sum of the factorial of their digits, we simply sum of the list to obtain the final answer.

Concealed Square

The Concealed Square is Problem 206 in Project Euler. It was solved by 24,160 people as of September 1, 2021. The question is

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit.

My approach to this problem contains roughly these steps. First, a for-loop to loop through all potential candidate. Then, after taking the square the number, check if the squared value has the form 1_2_3_4_5_6_7_8_9_0.

1. For-loop

Similar to the Digit Factorials problem, this question requires some careful thinking about the lower and upper bounds of the for-loop. After some trials, I found that if the squared value has an even number of digits, then the square root has half amount of digits and is in the higher value range. For example, the square of 990 has 6 digits, the square of 8,973 has 8 digits. If the squared value has an odd number of digits, then the number of digits the square root takes is (# digits in the squared number + 1)/2, and the number is in the lower value range. For example, the square of 25 has 3 digits, and the square of 17821 has 9 digits. In the problem, the target number has 19 digits, so we know that the answer has to be a 10-digit number. Furthermore, the target number starts with 1 and end with 0. This means that the answer also has to starts with 1 and end with 0. Now, we have narrowed our search range to between 1,000,000,000 and 1,999,999,990.

After some trial and error, I found the square of 1,010,101,010 produce a result that is very close the target form but smaller. Therefore, I set it as the lower bound. I found the square of 1,900,000,000 already produce a result that is larger than the target. Therefore, I set it as the upper bound.

For the code implementation of the for-loop.

Notice the for-loop skip 10 numbers for each iteration. This is because we know the answer has to end with 0, there is no need to iterate numbers whose last digit is not 0.

2. Matching the pattern

After getting the squared value, I converted the number into string and used regular expression to check for the pattern. If there is a match, then the search is finished.

Here is the complete code.

Refer to the Jupyter Notebook here!