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

Problem #108 says:

In the following equation x, y, and n are positive integers.

\[ \frac {1}{x} + \frac {1}{y} = \frac{1}{n} \]

What is the least value of n for which the number of distinct solutions exceeds one-thousand?

NOTE: This problem is an easier version of problem 110; it is strongly advised that you solve this one first.

So two things help us with this solution. First, the number of solutions can be calculated as Solutions = ((NumberOfDivisors(n*n) + 1) / 2), Second we can maximize the number of divisors and keep N small by making N a product of small prime numbers. So what this solution does is create a step value out of small primes and then steps through a range looking for solutions. Once it has the list it simply sorts it by the smallest N value and prints it out.

This solution calculates the number of divisors by factoring the number and using one plus the exponents of the factors times one plus the other factors exponents to get the number of divisors. E.g. 2^4 = 16 and 16 has the divisors 1,2,4,8,16 or (4+1). We also get to keep the factorization simple by using our step value this keeps the number of primes we need to factor N down by simply repeating primes that have already been used. However if we search too large a space we will eventually need to expand our list of prime numbers so our factor function doesn’t stop working because it cannot factor part of the number.

This solution works for problem #108 but extending the range it searches shows that it will be too slow for problem #110. I do however have a lead on a solution for #110 that should be much faster than this solution could ever be even though the numbers are far larger.

Solution in F# written in monodevelop. Runs in well under a second.

open System
open System.Collections.Generic
open System.Numerics
open System.Diagnostics

let generatePrimeNumbers max =
    let rec generate number numberSequence =
        if number * number > max then numberSequence else
        let filteredNumbers = numberSequence
                              |> Seq.filter (fun v -> v = number || v % number <> 0I)
                              |> Seq.toArray |> Array.toSeq
        let newNumber = filteredNumbers |> Seq.find (fun v -> v > number)
        generate newNumber filteredNumbers
    generate 2I (seq { for i in 2I..max -> i })

let primes = generatePrimeNumbers 50I |> Seq.toArray

let Factor x =
    let factors = new Dictionary<BigInteger,int64>()
    let factoree = ref x
    for f in primes do
        if (!factoree = 1I) then
            ignore
        else
            while (!factoree % f = 0I) do
                if factors.ContainsKey(f) then
                    factors.[f] <- factors.[f] + 1L
                    factoree := !factoree / f
                else
                   factors.Add (f,1L)
                   factoree := !factoree / f
            ignore
    factors

let DivisorsFromFactoring x =
    let divisors = ref 1L
    let factors = Factor x
    for k in factors.Keys do
        divisors := !divisors * (factors.[k] + 1L)
    !divisors

let SolutionsForGivenN n =
    ((DivisorsFromFactoring (n*n)) + 1L) / 2L

let step = (2L*3L*5L*7L*11L)*2L
let lower = step
let upper = 500000L

let Answer =
    seq[
        for n in [lower .. step .. upper] do
            yield (n , SolutionsForGivenN (BigInteger n))
    ]
    |> Seq.sortBy (fun x -> (fst x))
    |> Seq.filter (fun x -> (snd x) > 1000L)
    |> Seq.take 1

for i in Answer do
    Console.WriteLine i  

Problem #78 says:

Let p(n) represent the number of different ways in which n coins can be separated into piles.
For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O

Find the least value of n for which p(n) is divisible by one million.

This question is actually a slightly more complicated version of #76; and once again we’re dealing with integer partitions. This time however we include the number itself in the list of partitions. Also, the method for generating integer partitions provided in my solution for #76 is too slow for this problem witch deals with many more numbers and much larger numbers.

So the solution is to use Euler’s Pentagonal Theorm and this will let us generate the number of partitions are a good clip. To speed things up we’ll use a Dictionary to store all of the previously computed Pentagonal numbers. We do this mostly because BigInteger operations are slow and duplicating those operations adds up quickly. Another possible speedup could be found in Parallelizing the whole mess and checking multiple numbers in our testing range at the same time. As this is basically an embarrisingly parallel program doing this in parallel should give close to the optimal speedup. If one were to use the f# powerpack the answer function could be rewritten to use PSeq with minimal changes. Another thing that would speedup this program is modifiying it to only tracks the last 7 digits of the number of paritions (7 digits is the minimum number of digits needed to check if a number divides evenly by one million) which would allow the program to use float or decimal values instead of BigInt; which would make the math faster. Lastly one could also add logic to terminate the program when a working number is found provided the program checks the numbers in order; as provided below the program will continue to run untill it has generated the entire list. However this solution runs in about one minute on my machine and that works for me.

Solution provided in f# written in monodevelop.

open System
open System.Diagnostics
open System.Collections.Generic
open System.Numerics

let Pentagonal x = x*(3I*x-1I)/2I

let GeneralPentagonal x =
    if x<0I then
        0I
    else
        if x%2I = 0I then
            Pentagonal ((x/2I)+1I)
        else
            Pentagonal (-((x/2I)+1I))

let mem = new System.Collections.Generic.Dictionary<BigInteger,BigInteger>()
let MemPentagonal x =
    if mem.ContainsKey(x) then
        mem.[x]
    else
        mem.Add(x,GeneralPentagonal x)
        mem.[x]     

let sw = new Stopwatch()
sw.Start()    

let answer =
    List [
        let pt = new System.Collections.Generic.List<BigInteger>()
        pt.Add 1I
        for n = 1 to 60000 do
            let r = ref 0I
            let f = ref -1I
            let i = ref 0I
            let cont = ref true
            let k = ref 0I
            while !cont do
                k := MemPentagonal !i
                if !k > (BigInteger n) then
                    cont := false
                else
                    if !i % 2I = 0I then
                        f := 0I - !f
                    r := !r + (!f * pt.[n - (int32 !k)])
                    i := !i + 1I

            let consumeandignore = pt.Add !r
            yield (!r,n)
    ]
    |> Seq.filter (fun n -> (fst n) % 1000000I = 0I)
    |> Seq.head

[<EntryPoint>]
let main args =
    Console.WriteLine answer
    sw.Stop()
    Console.WriteLine sw.Elapsed
    0