Spoiler alert! The links contain solutions to the problems.
Here are the algorithms I worked on for Project Euler. Each problem is followed by a quick summary of the problem, and certain problems have a line stating something interesting or important learned. Clicking on a link will take you to a working example of the algorithm written in PHP. The code is show in highlighted format.
Evaluate the sum of all amicable pairs under 10000.
Find the sum of digits in 100!
Tried out the BC Math library for the first time. Would have liked to try the GMP library too, but that's not currently installed.
How many Sundays fell on the first of the month during the twentieth century?
Find the maximum sum travelling from the top of the triangle to the base.
A fun example of recursion. The heart of a problem that looks extremely complicated initially, becomes essentially 6 lines of code.
How many letters would be needed to write all the numbers in words from 1 to 1000?
Another instance, like problem 15, where recursive functions were useful. In this case, I wrote a recurssive function to turn digits into numbers. To look at the function expanded to include the numbers between negative and positive one quadrillion look over here.
What is the sum of the digits of the number 2^1000?
Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?
This problem written another way is: how many paths can you make with a total of 20 rightward paths and 20 downward paths. In other words out of a total of 40 paths, in how many ways can you pick 20 of one type of path. This question is covered in problem number 12. The answer is 40 choose 20, or 40! / (20! * (40-20)!). I created a recursive function to find factorials.
Find the longest sequence using a starting number under one million.
Ran into some memory constraints regarding the size of arrays in this one. Additionally, I think there may be some ways to make it faster.
Find the first ten digits of the sum of one-hundred 50-digit numbers.
What is the value of the first triangle number to have over five hundred divisors?
~1.7 seconds making use of both the algorithms for the number of divisors of a number and for how to represent a triangle number. ~2.5 seconds making use of the algorithm for the number of divisors of a number. ~8 seconds with the brute force method. Can still speed things up
What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?
Calculate the sum of all the primes below two million.
Warning: This one takes a while (~17s). All primes greater than 6 can be written as 6k + or - 1 (where k is some number). This is because ALL numbers can be written as 6k + n. If you go through 6k+1, 6k+2, 6k+3, 6k+4, and 6k+5, only 6k+1 and 6k+5 can be primes, since you can factor the other ones ... 2(3k+1), 3(2k+1), 2(3k+2) ... Finally, 6k+5 is 6k-1 of another name, that is, another k.
Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.
Discover the largest product of five consecutive digits in the 1000-digit number.
Find the 10001st prime.
It's quicker to go through all the numbers each time than to build an array of known primes as you go along. Array operations are slow.
What is the difference between the sum of the squares and the square of the sums?
What is the smallest number divisible by each of the numbers 1 to 20?
Only a few lines of code, but it takes ~5 seconds.
Find the largest palindrome made from the product of two 3-digit numbers.
rats live on no evil star
Find the largest prime factor of a composite number.
You don't need to try factors bigger than the square root of the number whose factors you are seeking.
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.
Calculating Fibonacci numbers is fast when you use the golden ratio. Links: 1 2 3
Add all the natural numbers below one thousand that are multiples of 3 or 5.
I use 4 methods and compare their speeds.