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

Problem #66 says:

Consider quadratic Diophantine equations of the form:

x^(2) – Dy^(2) = 1

For example, when D=13, the minimal solution in x is 649^(2) – 13×180^(2) = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

3^(2) – 2×2^(2) = 1
2^(2) – 3×1^(2) = 1
9^(2) – 5×4^(2) = 1
5^(2) – 6×2^(2) = 1
8^(2) – 7×3^(2) = 1

Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

So there are several ways to tackle this problem at first glance; Just role a pair of nested loops and try all the possible combinations until you get a working one then keeping track of the max value for X and D, the second is to find something else because the problems after number 10 are not conducive to a brute force approach. The first option isn’t feasible because the number of X,Y pairs you have to check to find a solution is exponentially greater than it appears at first glance. So we need to find something else.

What we can find with a simple Wikipedia search is that this particular form of equation is called a “Pell Equation” (Oddly enough it seems to be misnamed — look it up). This gives us some information that was already in the problem statement and a method for attacking the problem more efficiently. We’ve read in two different sources now that we don’t want D to be a perfect square; so the first thing we need is a simple test to check if a number is a perfect square.

//This is separated out because it's useful in other problems too.
let PerfectSquare (d:int) =
    let sqrtd = Math.Sqrt((double d))
    if ((double d) %  sqrtd = 0.0) then
        true
    else
        false

Just grab the square root of a number and then take the number mod it’s square root. if you end up with no remainder you have a perfect square and we want to skip that number. There might be faster methods but for this solution and the amount of time we call it this works well enough. So what next? Well the solution I went with is the continued fraction method; so we’ll need a method to generate continued fractions. Specifically we want to generate a Continued fraction set going towards the square root of the D value we’re currently checking. Then those values are used to calculate the fundamental solution to the Pell Equation which gives us the minimal X value for a given D value.

Full solution provided in F# and was developed with the F# mono-develop plug-in. Runs in under a second and prints the D value and the maximum X value; the X value should explain why using a nested loop is a really bad idea.

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

let GenerateCFraction (target:int64) =
    let e = new System.Collections.Generic.List<int64>()
    let SqrtTarget = int64 (Math.Sqrt(double target))
    let a = ref SqrtTarget
    let p = ref 0L
    let q = ref 1L
    e.Add(!a)
    p := !a * !q - !p
    q := (target - !p * !p) / !q
    a := (!p + SqrtTarget) / !q
    while !q <> 1L do
        e.Add(!a)
        p := !a * !q - !p
        q := (target - !p * !p) / !q
        a := (!p + SqrtTarget) / !q
    e.Add(!a)
    e

let SolvePell (cFrac:System.Collections.Generic.List<int64>) =
    let l = cFrac.Count - 1
    let per =
        if l % 2 = 0 then
            l - 1
        else
            2 * l - 1
    let a  = ref (BigInteger cFrac.[0])
    let a1 = ref 1I
    let b  = ref 1I
    let b1 = ref 0I
    let t = ref 0I
    a := (BigInteger cFrac.[0])
    b  := ((BigInteger cFrac.[0]) * !b + !b1)
    for i = 1 to (per) do
        t := !a
        a := (BigInteger cFrac.[(i-1)% l + 1]) * !a + !a1
        a1 := !t
        t := !b
        b := (BigInteger cFrac.[(i-1)% l + 1]) * !b + !b1
    !a

let PerfectSquare (d:int) =
    let sqrtd = Math.Sqrt((double d))
    if ((double d) %  sqrtd = 0.0) then
        true
    else
        false

[<EntryPoint>]
let main args =
    let sw = new Stopwatch()
    sw.Start()
    let x = ref 0I
    let maxx = ref 0I
    let maxd = ref 0
    for d = 2 to 1001 do
        if (PerfectSquare d) then
            ignore
        else
            let c = GenerateCFraction (int64 d)
            x := (SolvePell c)
            if (!x > !maxx) then
                maxx := !x
                maxd := d
            ignore
    sw.Stop()
    Console.WriteLine sw.Elapsed
    Console.WriteLine !maxd
    Console.WriteLine !maxx
    0