Project Euler - Improve your coding skills while having a blastproblem-solving
20 Sep 2019
2 minute read
Project Euler is a free platform named after famous mathematician Leonhard Euler that provides a large series of computer programming problems that challenge your problem-solving skills.
"Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics."
How it works #
After you sign up, you can try to complete almost 700 different problems. You will need to provide efficient solutions that don’t overload your computer’s CPU. Each solution should prepare you to solve the following levels.
Over 900 000 users have finished at least one of the many levels that are added about every two weeks. If you like challenging yourself in computer science and mathematics, you will love this website.
Let’s look at one of the first, beginner exercises: The instructions are:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Warning: the solution is explained below this message. First try to solve the problem and then scroll down
There are many ways to find the solution to this problem, in one of them you could brute force your way to the solution using your machine’s computational power (this example uses Python):
## initial values term1 = 1 term2 = 2 ans = 0 # while the last value of the sequence is below 4 million while (term2 < 4000000): # update sequence term1 = term2 + term1 # add the first term to the answer if it is even else add 0 ans += term1 if term1 % 2 == 0 else 0 # add term2 to the answer if it is even else add 0 ans += term2 if term2 % 2 == 0 else 0 term2 = term2 + term1
A more elegant, codeless solution would be to use the golden ratio, the approximate ratio between two consecutive terms of the fibonacci sequence. If we observe the fibonacci sequence, we can see that every third number is even (1, 1, 2, 3, 5, 8…). So the ratio between following even elements of the sequence is the golden ratio * 3 (or 4.236068).
All you have to do now is multiply these terms by 4.236068 and round the results to the nearest integer:
2 * golden ratio approx = 8
8 * golden ratio approx = 34
34 * golden ratio approx = 144
Add up all the previous values and stop before their values are higher than 4 million and you will have the solution.
2 + 8 + 34 + 144… = 4613732
I really recommend you check this website out. It’s a really fun and educative tool!
Subscribe to the blog's Valuable Entropy newsletter: