## 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 .

**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 ()

print()

**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.