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

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

So I found myself working on a small personal project in F# to gain more familiarity in the language when I decided the best way to solve my data storage needs would be a small local database file. So I went looking for ways to get sqlite into F# projects and couldn’t find a decent example. So I’ve started going through an example project in c# and trying to make it work in F#. I’ve got database creation and item insertion working so I figured what the heck I’ll post it here to make up for all of the posts I haven’t been writing lately.

I’m using the sqlite-net class from here compiled as a dll in a c# project. I’m then using that dll in my F# project. So if you’re looking for a pure f# implementation you at the wrong place. However its all il code at that level anyway. So armed with this dll I then create a f# type that looks a little something like this:

type Site (url:string) =
    let mutable id = new int()
    let mutable BD = ""
    let mutable site = url
    let mutable shown = false
    let mutable exemplarcontributor = false
    [<PrimaryKey>] [<AutoIncrement>]
    member x.ID with get() = id
                and set v = id <- v
    member x.ExemplarContributor with get() = exemplarcontributor
                                    and set v = exemplarcontributor <- v
    member x.Shown with get() = shown
                        and set v = shown <- v
    member x.BreakDown with get() = BD
                        and set v = BD <- v
    [<Indexed>]
    member x.Site with get() = site
                   and set v = site <- v
    member x.Url = url
    new() = Site "www.google.com"

now I should mention that this is directly from the test applet I’ve been using to get sqlite to work. as such it can probably be cleaned up quite a bit. Basically we have a URL and a few other details of a site and a few attributes. The ID is a primary key and auto incremented as shown above, note that this NEEDS to be put on the member declaration not the actual id. Also note that we need getter and setters on anything that we want to show up in the database, as such we need to make everything mutable. I’m still looking to see if there is another way to do that but this works for now. Anyways, armed with this type we can go to the next section, creating a database type that we’ll be adding custom stuff to in addition to inheriting from SQLiteConnection. And that looks like:

type Database (path) =
    inherit SQLiteConnection(path)
    member this.Setup = base.CreateTable<Site>()

Pretty basic right? All we’ve done is give the Database type a setup method that can be used to add the Site table to the database. If the database already has a Site table it’s not replaced but a safety check could easily be added to this method to make sure we don’t overwrite anything; however this is a throw away app and I’m not going to add it. Next we start doing stuff with these types. In fact we do this:

let D = new Database("test.sqlitedb")
D.Setup |> ignore

let s = new Site "www.google.com"

D.Insert(s) |> ignore

D.Commit|>ignore

Here we create a Database that we call D, call its setup method and pipe that to ignore (it returns an int to indicate errors, but I don’t want to catch it). Then we create a new instance of the Site type, do an insert again piping it to ignore and finally we commit everything and pipe that to ignore. And that’s it. We have a simple program that builds a useless database and adds a single entry to it. If you run this program multiple times it’ll just keep adding instances of Site to the database because it doesn’t overwrite the file.