Solution codes for Project Euler
I created a new repo on GitHub to share my solution codes for the problems of Project Euler. I find it is really interesting.
Comments on the problems.
A function is created to test whether a positive integer is a prime number.
Codes are developed to calculate the least common multiple of a group of numbers.
There are some interesting facts about the sum of the sequence of n^2. And it turns out that
(1 + 2 + … + n)^2 = 1^3 + 2^3 + … + n^3.
It turns out that in the Python environment if you check the current number to see whether it is a prime number by referring to the prime numbers already found and stored in a list, the overall performance is not as good as expected.
No magical things happened.
There is a genius solution in the discussion thread of Project Euler.
No magical things happened.
fliplr() functions are utilized in my python code. Remember to handle the opposite diagonals.
Using the prime factorization is the key.
In fact, only the first 11 or 12 digits of each number are needed if only the first 10 digits of the final answer are required.
Some people say that, in LISP, amazing things happens when solve this problem with only one “+” operator.
And it turns out that, for 10 digits precision one could use
double typed values instead of integers. Because for today’s PC, the
double value has 16 significant digits.
The method which utilizes the Hash table is much faster than the naive implementation.
The theoretical solution is based on the knowledge of Pascal’s triangle and the theory of permutation and combination. I did not quite get the idea of the theoretical solution. However, one guy named RudyPenteado gave an illustrative interpretation using binary codes.
Today’s dynamic or scripting programming language is so powerful that there is virtually no upper limit for integer.
However, I composed another piece of code. This code deliberately does not use the big integer functionality of Python. The long_integer class created in PEID 013 is borrowed. Since PEID 016 only require multiplication by 2, only the addition operation is needed.
I have to admit that this problem is not about mathematics and programming. It is all about the different usages of the word “and” between British English and American English. Furthermore, make sure to spell-check your words, like “forty”.
The code also works for PEID 067.
The key is to search from the bottom to the top.
I build a binary tree to do the recursive search. A flag should be set to indicate whether the current node has found a maximum sum.
Python provides a package with the name of
datetime. This package should do the trick.
But I decided to do it by myself.
And it turns out that 1200/7 is a fairly accurate approximation of this problem. Brilliant!
Everybody seems to rely on some sort of big-number library.
It is best to search below sqrt(n) when trying to calculate all the proper divisors of an integer n.
Make sure to check the following two situations: (1) The two numbers in a pair are identical. And, (2) Whether [a, b] and [b, a] are treated as different pairs.
First of all, the knowledge of ASCII codes is a plus. (ord() and chr() functions)
Benefit from list.sort() function of Python.
Then no magical things happened.
Not as fast as those posted on the discussion thread of Project Euler.
You can rely on the powerful
itertools package provided by python. However, I choose another way out.
No brute force this time. Inspired by Problem 013.
The cover image is obtained from the home page of Project Euler.