Project Euler


This page is a presentation of my solutions to the problems you can find at Project Euler. This is a site which has over 300 math problems which should be solved with the aid of a computer. Most of them can only be solved using a computer, since they involve a great number of computations. The problems grow in difficulty and from some point on, the implementation itself should be carefully thought since the computer can only perform a finite number of operations per minute. The goal is to get the answer to the given problem in less than a minute. I uset C, Pari GP, Python, Ms Excel and sometimes only a piece of paper and a pencil.
Problem 1. Very easy. Do it in C, or any language you want.
Problem 2. Google for Fibonacci and find its properties. Use a non-recursive algorithm which calculates all the Fibonacci numbers under 1000000 and sum those which are odd.
Problem 3. You have some options here. Do it in Python if you want to do it directly, or by simply writing factor(600851475143) in Pari GP.
Problem 4. The only challenge is to make a function to verify if a number is a palindrome. Using strings can be easier.
Problem 5. Make a least common multiple function for two numbers and iterate it for 1 to 20 to get the result. Again Pari GP can be of great help for a quick solve.
Problem 6. Use the formula (a_1+...+a_{100})^2=2\displaystyle \sum_{1\leq j < i\leq 100} a_ia_j.
Problem 7. Make a function “nextprime” which returns the next prime number after a given number. Iterate it 10000 times starting from 2 to get the result. Alternative: prime(10001) in Pari GP.
Problem 8. The hardest thing is to read that number from a file, and then go through it step by step, checking every product. Excel can be of great help also.
Problem 9. Since there can be only one such triplet, the implementation is simple:
for (a=1,a<=333,a++)
for(b=a+1,b<=(1000-a)/2,b++)
for(c=b+1,c<a+b,c++)
if (a^2+b^2==c^2)
print(a\cdot b\cdot c)
Problem 10. Easy task. Be careful, since the sum is quite big. Use an appropriate type for the sum, or just use Python (no limits 😉 ).
Problem 11. Similar to one of the previous problems, the greatest issue is to read all the entries from a file into a properly chosen matrix, with the hint that the matrix should be with 3 lines and 3 columns of 0’s greater than the initial matrix, to ease the programming. Carefully search every direction, up, down and diagonally in the direction SE and SW (south-east, south-west). I forgot the SW direction and got the wrong result. It took me a while to realize that.
Problem 12. Make a divisor counting function, or simply use Pari GP. (numdiv(n) returns the number of divisors of n).
Problem 13. Use Excel or Python. Excel is pretty easy.
Problem 14. I used C for this one. It is easy to make a function which counts the steps needed for given n. Make a for loop to get the maximum.
Problem 15 This is the first problem which poses some difficulty. A recursion algorithm works for 15×15 grid, but fails for 20×20. The ideea is that the vertical paths (or horizontal ones) are the one which uniquely determine the path. Therefore the number we search is a number of increasing functions from a set to another. I think you can figure it out from here. The result then can be calculated in Pari GP in miliseconds.
Problem 16 This one is a typical Pari GP problem. The trick is to make a function which returns the sum of digits of positive integer. it works like this in Pari GP.
sumdigits(n)=local(m);{
s=0;
while(n!=0,s=s+(n%10);n=n\10);
m=s;
}

Then simply type print(sumdigits(2^1000)).
Problem 17. Use Excel for this. Other coding possibilities are to be considered.
Problem 18. Read the triangle into a matrix. Then create a cost matrix initialized with zeros. The cost of the top vertex is its value in the matrix. Then, recursively, when you reach a point, you check the costs of the two next possible positions and if you can make a greater cost, you replace the cost in the matrix. This is similar to Dijkstra’s Algorithm ( a reversed version, for maximum cost). I leave some of the thinking to you. This algorithm can be used efficiently in problem 67.
A more easy approach is brute force calculating every possible sum. This does not work anymore for problem 67.
Problem 19. Excel has all the necessary tools. You could also use some formulas to find the day of the week for a given date.
Problem 20. Pari GP all the way, just like one of the previous problems.

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: