Project Euler and Me

Thanks to Ailin and Adam that introduce me the Project Euler and now I am totally addicted with it. After 8 years not using C as my primary programming language, is time for me to pick it up and do something with C ideology - small footprint with great performance!

Below is the question from Project Euler and the code I had written to solve it. Feel free to download them then make it better or give comment and suggestion on the solution. Programmer ROCKS!

ID	Description / Title	Solutions
1	Add all the natural numbers below one thousand that are multiples of 3 or 5.	Link
2	By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.	Link
3	Find the largest prime factor of a composite number.	Link
4	Find the largest palindrome made from the product of two 3-digit numbers.	Link
5	What is the smallest number divisible by each of the numbers 1 to 20?	Link
6	What is the difference between the sum of the squares and the square of the sums?	Link
7	Find the 10001st prime.	Link
8	Discover the largest product of five consecutive digits in the 1000-digit number.	Link
9	Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.	Link
10	Calculate the sum of all the primes below two million.	Link
11	What is the greatest product of four adjacent numbers on the same straight line in the 20 by 20 grid?	Link
12	What is the value of the first triangle number to have over five hundred divisors?	Link
13	Find the first ten digits of the sum of one-hundred 50-digit numbers.	Link
14	Find the longest sequence using a starting number under one million.	Link
15	Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?	Serial Parallel
16	What is the sum of the digits of the number 21000?	Link
17	How many letters would be needed to write all the numbers in words from 1 to 1000?
18	Find the maximum sum travelling from the top of the triangle to the base.	Link
19	How many Sundays fell on the first of the month during the twentieth century?
20	Find the sum of digits in 100!	Link
21	Evaluate the sum of all amicable pairs under 10000.
22	What is the total of all the name scores in the file of first names?	Link
23	Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.	Link
24	What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?	Link
25	What is the first term in the Fibonacci sequence to contain 1000 digits?	Link
26	Find the value of d < 1000 for which 1/d contains the longest recurring cycle.	Link
27	Find a quadratic formula that produces the maximum number of primes for consecutive values of n.	Link
28	What is the sum of both diagonals in a 1001 by 1001 spiral?	Link
29	How many distinct terms are in the sequence generated by ab for 2 = a = 100 and 2 = b = 100?	Link
30	Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.	Link
31	Investigating combinations of English currency denominations.	Link
32	Find the sum of all numbers that can be written as pandigital products.	Link
33	Discover all the fractions with an unorthodox cancelling method.	Link
34	Find the sum of all numbers which are equal to the sum of the factorial of their digits.	Link
35	How many circular primes are there below one million?	Link
36	Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.	Link
37	Find the sum of all eleven primes that are both truncatable from left to right and right to left.	Link
38	What is the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 1, 2, 3, ... ?	Link
39	If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p = 1000, has the most solutions?	Link
40	Finding the nth digit of the fractional part of the irrational number.	Link
41	What is the largest n-digit pandigital prime that exists?	Link
42	How many triangle words does the list of common English words contain?	Link
43	Find the sum of all pandigital numbers with an unusual sub-string divisibility property.	Link
44	Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.	Link
45	After 40755, what is the next triangle number that is also pentagonal and hexagonal?	Link
46	What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?	Link
47	Find the first four consecutive integers to have four distinct primes factors.	Link
48	Find the last ten digits of 11 + 22 + ... + 10001000.	Link
49	Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other.	Link
50	Which prime, below one-million, can be written as the sum of the most consecutive primes?	Link

Problem 15

Using programmatic method with serial navigating technique take 2 hours 15 minutes to get the result. If using mathematical method to calculate the possible path only take less then 1 second. The difference between these two methods is mathematical method only projected how many path there are but programmatic method give the actual path it had been navigated.

In my opinion, the real world problem like solving maze or path finding, programmatic method is more realistic. However, mathematical method can help to pre-project the result. The next thing I will going to do is design a parallel path navigating technique using multi-thread with multiple navigator, this solution will combine both mathematical  and programmatic method to accomplish the objective.

Result

Problem 15 with Serial Navigating Solution
-------------------------------------------
Path for 1x1. P: 2 (0s 2ms), M: 2 (0s 381ms)
Path for 2x2. P: 6 (0s 2ms), M: 6 (0s 11ms)
Path for 3x3. P: 20 (0s 4ms), M: 20 (0s 12ms)
Path for 4x4. P: 70 (0s 9ms), M: 70 (0s 12ms)
Path for 5x5. P: 252 (0s 50ms), M: 252 (0s 13ms)
Path for 6x6. P: 924 (0s 101ms), M: 924 (0s 13ms)
Path for 7x7. P: 3432 (0s 370ms), M: 3432 (0s 16ms)
Path for 8x8. P: 12870 (0s 1479ms), M: 12870 (0s 16ms)
Path for 9x9. P: 48620 (0s 5363ms), M: 48620 (0s 21ms)
Path for 10x10. P: 184756 (0s 18646ms), M: 184756 (0s 15ms)
Path for 11x11. P: 705432 (0s 40020ms), M: 705432 (0s 17ms)
Path for 12x12. P: 2704156 (0s 167027ms), M: 2704156 (0s 17ms)
Path for 13x13. P: 10400600 (0s 587571ms), M: 10400600 (0s 19ms)
Path for 14x14. P: 40116600 (3s -715159ms), M: 40116600 (0s 20ms)
Path for 15x15. P: 155117520 (8s 773356ms), M: 155117520 (0s 19ms)
Path for 16x16. P: 601080390 (36s -370565ms), M: 601080390 (0s 81ms)
Path for 17x17. P: 2333606220 (138s 83071ms), M: 2333606220 (0s 104ms)
Path for 18x18. P: 9075135300 (546s -580371ms), M: 9075135300 (0s 68ms)

Path for 19x19. P: 35345263800 (2104s 60565ms), M: 35345263800 (0s 44ms)

Path for 20x20. P: 137846528820 (8236s 7101ms), M: 137846528820 (0s 40ms)