Problem #95 says:

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

An extremely easy problem to solve despite the fact that it’s quite far down the list when sorted by difficulty. We can instantly stop generating the chain if it exceeds one million at any point in the chain. Also we need to check to make sure the chain ends up where we started or it isn’t valid for the problem; this means that we need to make sure we don’t get stuck in an infinite loop where the chain starts over and we miss it. Solution is written using a simple sum of divisors function that simply brute forces the sum instead of a more elaborate prime factor function; I don’t think the prime factor version would be too much faster because the magnitude of the numbers (under one million) just isn’t enough to warrant such an effort.

Solution written in mono/c# with a helping hand from the linq name-space (mainly for list.min and list.max functions without having to write my own) runs in about 6 seconds on a modern machine. Interestingly enough this could be made parallel if one so desired with a few simple modifications but it runs fast enough already.

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

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

			List<long> chain = new List<long>();
			List<long> tmp = new List<long>();

			for (long i = 1; i <= 100000; i++)
			{
				tmp = GenerateChain(i);
				if (tmp.Count() > chain.Count())
				{
					List<long> ch = tmp.Where(x=> x > 1000000).ToList();
					if (ch.Count() == 0)
						chain = GenerateChain(i);
				}
			}
			Console.WriteLine(chain[0].ToString() + " :: " + chain.Min().ToString());
		}
		public static List<long> GenerateChain (long num)
		{
			List<long> chain = new List<long>();
			long previous = num;
			while (!chain.Contains(previous) && previous < 1000000L)
			{
				chain.Add(previous);

				previous = NextInChain(previous);
			}

			if (previous != chain[0])
				chain.Clear();

			if (previous > 1000000L)
				chain.Add(9999999L);

			return chain;
		}
		public static long NextInChain (long num)
		{
			return ProperDivisors(num).Sum();
		}
		public static List<long> ProperDivisors (long num)
		{
			long max = (long)Math.Ceiling(Math.Sqrt((double)num));

			List<long> RetValue = new List<long>();
			RetValue.Add(1L);
			if (num % max == 0d)
				RetValue.Add(max);

			for(long i = 2; i < max; i++)
			{
				if (num % i == 0L)
				{
					RetValue.Add(i);
					RetValue.Add(num/i);
				}
			}

			return RetValue.Distinct().ToList();
		}
	}
}

Problem #61 asks

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

There are several things to look out for when writing a solution to this problem. 1) If the last two digits of a number are less than ten it cannot be part of a chain (because the question doesn’t allow numbers of the form 0XXX). 2) it doesn’t matter what type of number you start out with: because it’s a cyclical chain if you find one number you’ll find the others. 4) Don’t throw out duplicate numbers if they only differ by type: just because a triangle number and a heptagonal number are the same doesn’t mean that you can throw one away they can be valid parts of different chains. 4) Recursion.

Because we are told that the chain of numbers we’re looking for is cyclical a recursive approach is perhaps the easiest to write. We use a tiny class to keep track of the first two digits, the last two digits, the type of number (tri,hep,oct etc) and lastly the value of the number itself (so we can calculate the sum of the chain later). We generate all numbers of all types between 1,000 and 10,000 using this class and put them into a list. We then strip invalid numbers from the list; those with ending digits less than 10 so if a number ends with 09 then it cannot be part of a valid chain. Then we just loop through this giant list. To get the next number in the chain we make sure we don’t already have a number of that type in the chain and we don’t have a number with that value in the chain. If the number is a valid new addition to the solution chain we attempt to find the next number to the chain using the same rules. If a chain cannot be found with 6 members or the required cyclical property then we go up a level and remove the last number added and continue to check for a valid chain. Eventually using this solution we’ll find the chain and if we don’t stop with the first chain we’ll get all permutations of the chain; still we only need the first one because the sum of the numbers in the chain are all going to be the same regardless of the order they appear in.

Solution written in mono/c# and runs in less than 1/10th of a second.

using System;
using System.Diagnostics;
using System.Collections.Generic;

namespace Problem61
{
	public class ChainNum
	{
		public int starts = 0;
		public int ends = 0;
		public int num = 0;
		public int type = 0;

		public ChainNum (int i,int t)
		{
			num = i;
			starts = i/100;
			ends = i % 100;
			type = t;
		}

	}
	class MainClass
	{
		public static List<ChainNum> Nums = new List<ChainNum>();

		public static Stopwatch sw = new Stopwatch();
		public static void Main (string[] args)
		{
			sw.Start();
			FillLists();
			List<ChainNum> inv = new List<ChainNum>();
			foreach (ChainNum c in Nums)
			{
				if (c.ends < 10)
					inv.Add(c);
			}
			foreach (ChainNum c in inv)
			{
				Nums.Remove(c);
			}
			foreach(ChainNum n in Nums)
			{
				var c = new List<ChainNum>();
				c.Add(n);
				var sol = BuildSolution(1,c);
				int count = 0;
				if (sol != null)
				{
					foreach (ChainNum s in sol)
						count += s.num;
				}
				if (count != 0)
				{
					Console.WriteLine(count);
					break;
				}
			}
			sw.Stop();
			Console.WriteLine(sw.Elapsed);
		}
		public static List<ChainNum> BuildSolution (int level, List<ChainNum> solution)
		{
			if (level > 6)
				return null;
			if (solution.Count == 6 && solution[0].starts == solution[5].ends)
				return solution;
			if (solution.Count == 6)
				return null;

			foreach (ChainNum c in Nums)
			{
				bool alreadyhastypeornumber = false;
				foreach(ChainNum temp in solution)
				{
					if (temp.type == c.type || temp.num == c.num)
						alreadyhastypeornumber = true;
				}
				if (alreadyhastypeornumber)
					continue;
				else
				{
					if (solution[solution.Count-1].ends == c.starts)
					{
						solution.Add(c);
						var sol = BuildSolution(level++,solution);
						if (sol != null)
							return sol;
						else
							solution.Remove(c);

					}
				}

			}
			return null;
		}
		public static void FillLists ()
		{
			int i = 1;
			while(TriangleNum(i) < 10000)
			{
				if (TriangleNum(i) > 1000)
					Nums.Add(new ChainNum(TriangleNum(i),3));
				i++;
			}
			i = 0;

			while(SquareNum(i) < 10000)
			{
				if (SquareNum(i) > 1000)
					Nums.Add(new ChainNum(SquareNum(i),4));
				i++;
			}
			i = 0;

			while(PentagonalNum(i) < 10000)
			{
				if (PentagonalNum(i) > 1000)
					Nums.Add(new ChainNum(PentagonalNum(i),5));
				i++;
			}
			i = 0;

			while(HexagonalNum(i) < 10000)
			{
				if (HexagonalNum(i) > 1000)
					Nums.Add(new ChainNum(HexagonalNum(i),6));
				i++;
			}
			i = 0;

			while(HeptagonalNum(i) < 10000)
			{
				if (HeptagonalNum(i) > 1000)
					Nums.Add(new ChainNum(HeptagonalNum(i),7));
				i++;
			}
			i = 0;

			while(OctagonalNum(i) < 10000)
			{
				if (OctagonalNum(i) > 1000)
					Nums.Add(new ChainNum(OctagonalNum(i),8));
				i++;
			}

		}

		public static int TriangleNum (int n)
		{
			return (n*(n+1))/2;
		}
		public static int SquareNum (int n)
		{
			return n*n;
		}
		public static int PentagonalNum (int n)
		{
			return (n*(3*n-1))/2;
		}
		public static int HexagonalNum (int n)
		{
			return n*(2*n-1);
		}
		public static int HeptagonalNum (int n)
		{
			return (n*(5*n -3))/2;
		}
		public static int OctagonalNum (int n)
		{
			return n*(3*n -2);
		}

	}
}

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;
        }

	}
}