Problem #131 says:

There are some prime values, p, for which there exists a positive integer, n, such that the expression \(n^{3} + n^{2}p\) is a perfect cube.

For example, when \(p = 19, 8^{3} + 8^{2}×19 = 12^{3}\).

What is perhaps most surprising is that for each prime with this property the value of n is unique, and there are only four such primes below one-hundred.

How many primes below one million have this remarkable property?

This is a problem that would drive a person insane if they tried to brute force a solution; even though the search area is (relatively for a Project Euler problem) small. This problem has a very elegant solution as long as you know how to break down the problem to it’s base components. Writing the problem out gives us \(n^{3} + n^{2}p = y^{3}\) which we can rearrange to look like \(n^{2}(n+p) = y^{3}\). Playing with a few values leads us to the conclusion that both \(n^{2}\) and \((n+p)\) have to be cubes. This makes p a difference of cubes such that \( (a+1)^{3} – a^{3} = p \)

So we take this new knowledge and figure out when \( (a+1)^{3} – a^{3} \) becomes greater than 1,000,000 and find that this happens around a = 577. This means that we just put the numbers from 1 to 577 into our difference of squares equation and count which ones return a prime.

Solution provided in c#/mono runs in about .038 seconds.

using System;
using System.Collections.Generic;
namespace Problem131
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			List<int> primes = GeneratePrimes(1000);
			int count = 0;

			for (int i = 1; i < 577; i++)
			{
				int check = ((i+1)*(i+1)*(i+1)) - (i*i*i);

				if (IsPrime(check,primes))
				{
					count++;
				}
			}
			Console.WriteLine(count);
			Console.ReadLine();
		}
		static bool IsPrime(int i,List<int> primes)
		{
			foreach(int p in primes)
			{
				if (i%p == 0 && i!= p)
					return false;
			}

			return true;
		}
		static List<int> GeneratePrimes(int num)
        {
            List<int> RetValue = new List<int>();
            RetValue.Add((int)2);
            RetValue.Add((int)3);
            int Stepper = 5;
            int Check = 1;
            while (Stepper <= num)
            {
                foreach (int i in RetValue)
                {
                    if (Stepper % i == 0)
                    {
                        Check = 0;
                        break;
                    }
                    if (Math.Sqrt(Stepper) < i)
                    {
                        break;
                    }
                }
                if (Check == 1)
                {
                    //Console.WriteLine(((float)Stepper / (float)num) * 100);
                    RetValue.Add(Stepper);
                }
                Check = 1;
                Stepper++;
                Stepper++;
            }
            return RetValue;
        }
	}

}

Problem #204 says:

We will call a positive number a generalised Hamming number of type n, if it has no prime factor larger than n.
Hence the Hamming numbers are the generalised Hamming numbers of type 5.

How many generalised Hamming numbers of type 100 are there which don’t exceed 10^9?

This is actually a problem that has been solved to death. While researching hamming numbers several methods were found to generate them. This solution uses Dijkstra’s method of starting with a list containing the number one. Then multiply every element in that list with one of the prime numbers we’re using then combine the resulting list with the original list and repeat the previous step using the resulting list with the next prime.

To find out how many times we have to repeat this operation before having all of the numbers we take the upper bound and find the log base two of that number. This gives us the number of iterations needed to make sure that we have all of the numbers we’re interested in. The solution uses a hash set to make sure that it is unique and contains no duplicates. To minimize time spent generating hamming numbers if a number exceeds the upper bound it’s thrown out.

It’s not the most elegant solution to the problem and takes about 1 min 40 seconds to run. Solution provided in c#/mono. One simple thing that could speed this up is the insight that you only need the new numbers from the previous iteration to generate the next iterations hamming numbers, if you use the old numbers you duplicate a lot of work. This would require storing the resulting set from the previous run and intersecting it with the current set; this would then be passed into the expand set function.

As provided this solution solves the sample given in the problem statement.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Threading.Tasks;
using System.Linq;

namespace Problem204
{
	class MainClass
	{
		public static void Main (string[] args)
		{

			List<long> primes = GeneratePrimes(5);
			long Upperbound = 100000000L;
			HashSet<long> p = new HashSet<long>();
			p.Add(1L);
			long k = 1L;

			while(k <= 29)
			{
				p = ExpandSet(p,primes,Upperbound);
				Console.WriteLine(p.Count());
				k++;
			}

			long count = p.Count();
			Console.WriteLine(count);

		}

		static HashSet<long> ExpandSet (HashSet<long> p, List<long> primes, long max)
		{
			var RetValue = new HashSet<long>();
			foreach(long prime in primes)
			{
				foreach (long s in p)
				{

					if ((s*prime) > max)
						continue;
					else
						RetValue.Add(s*prime);
				}

			}
			RetValue.UnionWith(p);
			return RetValue;
		}

	static List<long> GeneratePrimes(long num)
        {
            List<long> RetValue = new List<long>();
            RetValue.Add((long)2);
            RetValue.Add((long)3);
            long Stepper = 5;
            long Check = 1;
            while (Stepper <= num)
            {
                foreach (long i in RetValue)
                {
                    if (Stepper % i == 0)
                    {
                        Check = 0;
                        break;
                    }
                    if (Math.Sqrt(Stepper) < i)
                    {
                        break;
                    }
                }
                if (Check == 1)
                {
                    //Console.WriteLine(((float)Stepper / (float)num) * 100);
                    RetValue.Add(Stepper);
                }
                Check = 1;
                Stepper++;
                Stepper++;
            }
            return RetValue;
        }
	}
}

So problem #120 says:

Let r be the remainder when (a−1)^n + (a+1)^n is divided by a^2.

For example, if a = 7 and n = 3, then r = 42: 6^3 + 8^3 = 728 ≡ 42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that rmax = 42.

For 3 ≤ a ≤ 1000, find ∑ rmax.

If we start putting various values into the equation for n and expanding the equation we notice a pattern emerging. If n is even the last term which is the only term not evenly divisible by a^2 is 2 which is a constant. However for odd values of n the last term ends up being 2*n*a. A little more tinkering on pencil and paper shows us that n = (a – 1)/2 so that means for any value a the rmax is equal to 2*a*((a-1)/2).

The solution below runs in about 3 hundredths of a second (according to linux’s time command). Provided in mono/c#.

using System;
using System.Diagnostics;

namespace Problem120
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            int sum = 0;
            for (int a = 3; a <= 1000; a++)
            {
                sum += 2 * a * ((a - 1) / 2);
            }
            Console.WriteLine(sum);
            sw.Stop();
            Console.WriteLine(sw.Elapsed);
            Console.ReadLine();
        }
    }
}

Problem #203 says:

A positive integer n is called squarefree if no square of a prime divides n. Of the twelve distinct numbers in the first eight rows of Pascal’s triangle, all except 4 and 20 are squarefree. The sum of the distinct squarefree numbers in the first eight rows is 105.

Find the sum of the distinct squarefree numbers in the first 51 rows of Pascal’s triangle.

This is a easy problem to brute force as it is given. If we start with the Pascal Tree in a comma separated string we can use linq to get the distinct values; we then need to generate some primes to check the square free property of the numbers. A simple function to check the numbers against the squared primes then print the sum of the ones that pass the test.

Solution provided in c#/mono. Only the first couple of rows are provided for the pascal tree; as shown below it will give the answer to the sample in the problem. This solution runs in about 6 seconds.

using System;
using System.Linq;
using System.Collections.Generic;

namespace Problem203
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			string tri = "1," +
						"1,1," +
						"1,2,1," +
						"1,3,3,1," +
						"1,4,6,4,1," +
						"1,5,10,10,5,1," +
						"1,6,15,20,15,6,1," +
						"1,7,21,35,35,21,7,1";

			string[] items = tri.Split(',');

			List<long> litems = new List<long>();
			foreach (string s in items.Distinct())
			{

				litems.Add(long.Parse(s));
			}
			Console.WriteLine(litems.Distinct().Count());

			List<long> primes = GeneratePrimes(9000000L);
			primes = primes.Select(s => s*s).ToList();

			long sum = litems.Distinct().Where(s=> squarefree(s,primes)).ToList().Sum();

			Console.WriteLine(sum);

		}
		static bool squarefree (long num, List<long> primes)
		{
			foreach (long p in primes)
			{
				if (p > num)
					break;
				else
				{
					if (num % p == 0L)
						return false;
				}
			}

			return true;
		}
		static List<long> GeneratePrimes(long num)
        {
            List<long> RetValue = new List<long>();
            RetValue.Add((long)2);
            RetValue.Add((long)3);
            long Stepper = 5;
            long Check = 1;
            while (Stepper <= num)
            {
                foreach (long i in RetValue)
                {
                    if (Stepper % i == 0)
                    {
                        Check = 0;
                        break;
                    }
                    if (Math.Sqrt(Stepper) < i)
                    {
                        break;
                    }
                }
                if (Check == 1)
                {
                    //Console.WriteLine(((float)Stepper / (float)num) * 100);
                    RetValue.Add(Stepper);
                }
                Check = 1;
                Stepper++;
                Stepper++;
            }
            return RetValue;
        }

	}
}

Problem #104 says:

Given that F(k) is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

First of all the Fibonacci number F(k) is some 68 thousand digits long. It’s insane to try to and brute force this using a big int class and a couple of variables; and it only gets worse if one tries to use a recursive algorithm. Even if you use some caching of previous Fibonacci terms the program still won’t get close to the answer before running out of memory.

So how can we solve this? Well consider what we need to look at; the first and last 9 digits. Which means of some 68 thousand digits we care about 18 of them so why bother calculating the rest? To do this for the last 9 digits should be pretty obvious. If we have the two previous Fibonacci numbers that are added to get the next Fibonacci number what we can do is only remember the Fibonacci number mod one billion. This will chop off all the numbers except for the last few which is what we want. We can then use a long data type to store and calculate the Fibonacci series (or at least the last couple of digits of it).

How then do we get the first couple of digits to check that? We can use a formula called Binet’s formula.
\[F(n) = \frac{\Phi^{n}-(1-\Phi)^{n}}{\sqrt{5}}\]
This helps because we only need to give it the k term we’re looking for and it will give back the first digits of the term F(k) without calculating the intervening terms. We modify it a bit to fit into c#/mono data types (basically we use it log base ten) with some other magic built it.

So the solution is provided below in c#/mono developed in monodevelop; runs in about 2 seconds.

using System;
using System.Linq;

namespace Problem104
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			long fnm2 = 1L;
			long fnm1 =1L;
			long fn = 0L;
			decimal k = 2;
			bool found = false;

			while (!found)
			{
				k++;

				fn = fnm2 + fnm1;

				if (CheckBottomDigits(fn))
				{
					if (CheckTopDigits(k))
						found = true;
				}

				fnm2 = fnm1 % 1000000000;
				fnm1 = fn % 1000000000;

				if (k % 500 == 0)
					Console.WriteLine(k);

			}

			Console.WriteLine(k);

		}
		public static decimal philog10 = decimal.Parse("0.2089876402499787");
		public static decimal sqrt5log10 = decimal.Parse("-0.349485002168009");
		public static bool CheckTopDigits (decimal n)
		{

			decimal td = (n * philog10) + sqrt5log10;
			double t = Math.Pow(10,(double)(td - (int)td + 8));

			if (t.ToString().Length < 9)
				return false;

			if (PanDigital(t.ToString().Substring(0,9)))
				return true;
			else
				return false;

		}

		public static bool CheckBottomDigits (long check)
		{
			string num = check.ToString();
			if ( num.Length >= 9)
			{
				if (PanDigital(num.Substring(num.Length - 9,9)))
					return true;
			}
			return false;
		}

		public static bool PanDigital (string num)
		{
			bool pan = true;
			if (!num.Contains('1'))
				pan = false;
			if (!num.Contains('2'))
				pan = false;
			if (!num.Contains('3'))
				pan = false;
			if (!num.Contains('4'))
				pan = false;
			if (!num.Contains('5'))
				pan = false;
			if (!num.Contains('6'))
				pan = false;
			if (!num.Contains('7'))
				pan = false;
			if (!num.Contains('8'))
				pan = false;
			if (!num.Contains('9'))
				pan = false;

			return pan;
		}
	}
}