Trying Project Euler
Using Python to Solve Complex Math Problems
About Project Euler:
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. It was created in 2001 as a sub-section of another problem-solving website, mathschallenge.net. New problems are added once a week, with most new problems being suggested by a member of the PE community. Project Euler’s goal is to provide people with an opportunity to maintain and enhance their skills in mathematics, programming and problem solving. As of November 21st, 2019, there are 689 total problems to be solved on the website.
Starting on the Problems:
I decided to go through the problems in the order of least difficult to most difficult(PE assigns each problem a “difficulty rating”). This would allow me to build off each successfully completed problem and make the more complex problems much more manageable.
Problem 1:
To solve this problem, I used an if statement inside a for loop. It was a pretty simple solution.
Problem 2:
This problem is definitely more difficult than problem 1. Fortunately, I recently learned about recursion in Python, and one of the examples was calculation the Fibonacci sequence.
Here is the code for calculating the value of the n-th term:
I made a new python module to hold all the calculations I would need to create to solve the PE problems, and I put the function for Fibonacci in that new module. Then, I imported the module with the Fibonacci function so I could keep my solution code clean.
Problem 3:
This one was the first one that really caused me trouble. To solve it, I had to figure out a way to check if a number was prime, then check if that number was a factor of 600851475143. This required two separate functions in the module, one to check if a given number was prime, and one to check through all possible factors.
These are the two functions; isprime checks all the possible conditions that would make a number not prime, while max_prime_factor iterates through a range of the possible factors and pushes those numbers into the isprime function. If a number is prime and is a factor of the given number, the max_prime_factor function will set that number as the returned value of the maximum prime number. Since the iteration goes in ascending order, this means that the last prime factor found will have the maximum value. In this case, the maximum prime factor of 600851475143 is 6857.
Problem 4:
This problem was easily the most difficult so far. To solve it, I had to use a nested for loop. At first, I thought I could iterate backwards and just take the first solution. Unfortunately, I couldn’t manage to make this approach work. In the end, I iterated normally and I created a variable that would be assigned to the highest palindrome that is found.
In the check_for_palindrome function, I had to take the input(an integer) and convert it to a string. Then, I compared the result to the reverse of itself. If the string matched its reversed string, then the function returned true.
Problem 5:
This problem had a very simple, if inelegant solution: for each number starting at 2,520, check if it is divisible by all numbers between 1 and 20.
Problem 14:
From here on out, I will only be highlighting the problems that were particularly difficult or interesting.
Problem 14 was interesting because it required a new function to calculate the sequence.
It took some slightly creative looping, but overall the function was not very difficult to build. Once the function is built, all I had to do was plug the function into a loop to iterate through all values under 1 million.
Problem 17:
Problem 17 provided an interesting challenge. The fastest solution required me to find a system to encode a given number, then iterate through all the possible numbers and find the total number of letters.
In this snippet, ‘S’ is a list that contains the number of letters for ‘One’ through ‘Nineteen’, ‘D’ contains the number of letters for multiples of 10 from ‘Ten’ through ‘Ninety’, ‘H’ represents ‘Hundred’ and ‘T’ represents ‘Thousand.’ After figuring out the encoding, all it took was a simple for loop and some conditional statements to calculate the answer.
At first, I had a more convoluted method to calculate the total lengths, and while that method worked, it took several minutes to run, so clearly I needed a more streamlined solution.
Conclusion:
So far, Project Euler has provided some challenge to both my programming and math skills. While none of the problems took me too long to solve, each provided a fresh set of issues that required creative problem solving. PE is a very good tool to keep your programming skills sharp and it has even taught me some good new techniques already. I will be adding to this as I continue to work my way through the list of problems.
