Problem #69 says:

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of
numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than
nine and relatively prime to nine, φ(9)=6.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

For this problem I created a class that held the number and it’s totient and then create them in parallel.
Then I loop through the mess looking for the instance with the highest check value. The Parallelism is handled by
the PSeq object from the F# power pack.

Solution in f# and requires .net 4 and the F# power pack from codeplex. Runs in ~48 seconds.

#light

open System
open System.Diagnostics
open Microsoft.FSharp.Linq
open Microsoft.FSharp.Collections

//set the limit and bound
let UpperLimit = 1000000.
let UpperBound = (Math.Sqrt(UpperLimit))

//generate numbers to check
let Primes = ref [2. .. (UpperLimit)] in

// loop through all numbers
// keep removing numbers that divide evenly
for div = 2 to int UpperBound do
  Primes := List.filter(fun num -> (num % (float div) <> 0. || (float div) >= num))
        !Primes
done;

let rec factorise (n:float) =
    if n = 1. then [] else
    let a = !Primes |> List.find (fun x -> n % x = 0.)
    a :: factorise (n / a)

let Totient (x:float) =
    (factorise x)
    |> Seq.distinct
    |> Seq.map (fun x -> 1. - (1./x))
    |> Seq.fold(fun acc a -> acc * a) x

type TestCase (Num:float) =
    let mutable _num = Num
    let _tot = Totient (float _num)
    member x.num
        with get() = _num
        and set(v) = _num <- v

    member x.Check
        with get() = x.num / _tot

Console.WriteLine("Starting Check")
let watch = new Stopwatch()
watch.Start()

let Answer =
    let mutable Ans = new TestCase(1.)
    let Tests =
        [2. .. 1000000.]
        |> PSeq.map (fun x -> new TestCase(x))
    for t in Tests do
        if t.Check > Ans.Check then
            Ans <- t
    Ans.num

Console.WriteLine(Answer)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.ReadKey() |> ignore

Problem #51 says:

By replacing the 1st digit of *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

For this problem what we need to look for are prime numbers that have repeating digits. We replace all of the similar digits with a new value. This means that the digits we replace cannot include the last digit because this will make the number non-prime for almost every replacement. The simplest way to do this is to pre-compute the digit that we are going to replace before going through all of the numbers and swapping digits out. So we have a class called CheckSet which does this for us allowing us to focus on swapping the digits and checking to see if the result is prime.

Solution below is in c#/mono and runs in about 18 seconds.

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

namespace ProjectEuler
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			Stopwatch sw = new Stopwatch();
			sw.Start();
			ArrayList p = GeneratePrimes(999999);
			ArrayList sub_p = new ArrayList();
			foreach (long l in p)
			{
				if (l > 100000)
				{
					CheckSet c = new CheckSet(l);
					if (c.DigitCount >= 1)
					{
						sub_p.Add(c);
					}
				}
			}

			foreach (CheckSet c in sub_p)
			{
				int size = FamilySize(ref p,c);
				if (size >=8)
				{
					Console.WriteLine(c.ToString());
					sw.Stop();
					Console.WriteLine(sw.Elapsed);
					Console.ReadLine();
					break;
				}
			}

		}
		static bool IsPrime(ref ArrayList primes, long num)
		{
			bool RetVal = true;
			long check = Convert.ToInt64(Math.Ceiling(Math.Sqrt(Convert.ToDouble(num))));
			foreach (long l in primes)
			{
				if (l > check)
					break;
				if (num % l == 0)
					RetVal = false;
			}
			return RetVal;
		}
        static ArrayList GeneratePrimes(long num)
        {
            ArrayList RetValue = new ArrayList();
            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;
        }
		static int FamilySize (ref ArrayList primes, CheckSet c)
		{
			int RetVal = 0;
			int[] digits = new int[10] {0,1,2,3,4,5,6,7,8,9};
			string num = c.Number.ToString();
			string cha = c.Digit;

			for (int i = 0; i<10;i++)
			{
				if (primes.Contains(long.Parse(num.Replace(cha,digits[i].ToString())))
                    && long.Parse(num.Replace(cha,digits[i].ToString())).ToString().Length == 6)
				{
					RetVal++;
				}
			}

			return RetVal;
		}
	}
	class CheckSet
	{
		public long Number;
		public string Digit;
		public int DigitCount;
		public CheckSet(long number)
		{
			Number = number;
			string s = number.ToString();
			string lastc = s[s.Length-1].ToString();
			int lengthcheck = s.Length;
			int[] digits = new int[10] {0,0,0,0,0,0,0,0,0,0};
			if (lastc != "0")
			{
				s = s.Replace("0","");
				digits[0] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "1")
			{
				s = s.Replace("1","");
				digits[1] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "2")
			{
				s = s.Replace("2","");
				digits[2] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "3")
			{
				s = s.Replace("3","");
				digits[3] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "4")
			{
				s = s.Replace("4","");
				digits[4] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "5")
			{
				s = s.Replace("5","");
				digits[5] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "6")
			{
				s = s.Replace("6","");
				digits[6] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "7")
			{
				s = s.Replace("7","");
				digits[7] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "8")
			{
				s = s.Replace("8","");
				digits[8] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			if (lastc != "9")
			{
				s = s.Replace("9","");
				digits[9] = lengthcheck - s.Length;
				lengthcheck = s.Length;
			}
			int MostCommonDigit = 0;
			int MostCommonDigitCount = 0;

			for (int i = 0;i<10;i++)
			{
				if (digits[i] > MostCommonDigitCount)
				{
					MostCommonDigit = i;
					MostCommonDigitCount = digits[i];
				}
			}

			Digit = MostCommonDigit.ToString();
			DigitCount = MostCommonDigitCount;
		}
		public override string ToString ()
		{
			return string.Format(Number.ToString() + " :: " + Digit+ " :: " + DigitCount.ToString());
		}

	}
}

Problem #60 says:

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

At first I thought of writing a class that would generate all permutations for the possible answers. It was simpler to write a simple program that generates a list of primes and loops through it. Solution below is c#/mono and runs in 20 or so seconds.

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

namespace ProjectEuler
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			Stopwatch sw = new Stopwatch();
			sw.Start();
			ArrayList p = GeneratePrimes(10000);

			foreach (long i1 in p)
			{
				foreach (long i2 in p)
				{
					if (i2 <= i1) continue;
					if (!IsPrime(ref p, long.Parse(i1.ToString() + i2.ToString())) ||
                                            !IsPrime(ref p, long.Parse(i2.ToString() + i1.ToString())))
					{
						continue;
					}
					foreach (long i3 in p)
					{
						if (i3 <= i2) continue;
						if (!IsPrime(ref p, long.Parse(i1.ToString() + i3.ToString())) ||
                                                    !IsPrime(ref p, long.Parse(i3.ToString() + i1.ToString())) ||
						    !IsPrime(ref p, long.Parse(i2.ToString() + i3.ToString())) ||
                                                    !IsPrime(ref p, long.Parse(i3.ToString() + i2.ToString())))
						{
							continue;
						}
						foreach(long i4 in p)
						{
							if (i4 <= i3) continue;
							if (!IsPrime(ref p, long.Parse(i4.ToString() + i3.ToString())) ||
                                                            !IsPrime(ref p, long.Parse(i3.ToString() + i4.ToString())) ||
						       	    !IsPrime(ref p, long.Parse(i2.ToString() + i4.ToString())) ||
                                                            !IsPrime(ref p, long.Parse(i4.ToString() + i2.ToString())) ||
							    !IsPrime(ref p, long.Parse(i1.ToString() + i4.ToString())) ||
                                                            !IsPrime(ref p, long.Parse(i4.ToString() + i1.ToString())))
							{
								continue;
							}
							foreach(long i5 in p)
							{
								if (i5 <= i4) continue;
								if (!IsPrime(ref p, long.Parse(i5.ToString() + i3.ToString())) ||
                                                                    !IsPrime(ref p, long.Parse(i3.ToString() + i5.ToString())) ||
							    	    !IsPrime(ref p, long.Parse(i2.ToString() + i5.ToString())) ||
                                                                    !IsPrime(ref p, long.Parse(i5.ToString() + i2.ToString())) ||
								    !IsPrime(ref p, long.Parse(i1.ToString() + i5.ToString())) ||
                                                                    !IsPrime(ref p, long.Parse(i5.ToString() + i1.ToString())) ||
								    !IsPrime(ref p, long.Parse(i4.ToString() + i5.ToString())) ||
                                                                    !IsPrime(ref p, long.Parse(i5.ToString() + i4.ToString())))
								{
									continue;
								}
								else
								{
									Console.WriteLine(i1+i2+i3+i4+i5);
									sw.Stop();
									Console.WriteLine(sw.Elapsed);
									Console.ReadLine();
								}
							}
						}
					}
				}
			}

			sw.Stop();
			Console.WriteLine(sw.Elapsed);
			Console.ReadLine();
		}
		static bool IsPrime(ref ArrayList primes, long num)
		{
			bool RetVal = true;
			long check = Convert.ToInt64(Math.Ceiling(Math.Sqrt(Convert.ToDouble(num))));
			foreach (long l in primes)
			{
				if (l > check)
					break;
				if (num % l == 0)
					RetVal = false;
			}
			return RetVal;
		}
        static ArrayList GeneratePrimes(long num)
        {
            ArrayList RetValue = new ArrayList();
            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;
        }

	}
}

Note: This solution marks my completion of 1- 50 in the project euler problem set. bringing the total number of problems I’ve solved to 64.

Problem #26 says

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that ^(1)/_(7) has a 6-digit recurring cycle.

Find the value of d < 1000 for which ^(1)/_(d) contains the longest recurring cycle in its decimal fraction part.

The trick to this one is to realize that the decimals your going to end up dealing with are not going to fit into and standard decimal class. So you could go and try to find an arbitrary precision decimal class and then convert it to a string and hook that into some pattern detection. Or you can use a simple trick to build an array of quotients using nothing but integer math and check to see if you start going through the same sequence.

Solution provided below is in f# and requires .net 4. runs in under one second.

// Learn more about F# at http://fsharp.net
#light
open System
open System.Diagnostics
open System.Collections.Generic

//get some prime numbers
//set the limit and bound
let UpperLimit = 1000.
let UpperBound = 1000
//generate numbers to check
let LNums = ref [2..(int UpperLimit)] in
// loop through all numbers
// keep removing numbers that divide evenly
for div = 2 to UpperBound do
  LNums := List.filter(fun num -> (num % div <> 0 || div >= num))
        !LNums
done;
let Primes:list<int> = !LNums

let divby rem div =
    let y =
        [0..4]
        |> Seq.filter (fun x -> (rem * int (float 10 ** float x)) > div)
    if (y |> Seq.length) <> 0 then
        let miny = Seq.min y
        rem * int (float 10 ** float miny) % div
    else
        0

let rec patternlength init (rems:list<int>) d =
    let rem = divby init d
    if (List.exists (fun x -> x = rem) rems) then
        (rems.Length - (List.findIndex (fun y -> y = rem) rems))
    else
        patternlength rem (List.append rems [rem]) d

Console.WriteLine("Starting check")
let watch = new Stopwatch()
watch.Start()

let Check =
    let mutable Longest = 0
    let mutable Nlongest = 0
    for p in Primes do
        let l = patternlength 1 [] p
        if l > Longest then
            Longest <- l
            Nlongest <- p
    Nlongest

watch.Stop()
Console.WriteLine(Check)
Console.WriteLine(watch.Elapsed)
Console.ReadKey() |> ignore

Problem #46 says

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^(2)
15 = 7 + 2×2^(2)
21 = 3 + 2×3^(2)
25 = 7 + 2×3^(2)
27 = 19 + 2×2^(2)
33 = 31 + 2×1^(2)

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Solution below uses the method of generating a list of primes and then using a set list of numbers to square and checking the combination’s to see if we can find one that makes the number we’re looking for.

Solution provided in f# and requires .net 4. runs in ~50 seconds. could be made much faster by rewriting the “Check” function to use a set of recursive functions instead of for loops so we could break out of them.

#light
open System
open System.Diagnostics
open System.Collections.Generic

//get some prime factors
//set the limit and bound
let UpperLimit = 10000.
let UpperBound = 10000
//generate numbers to check
let LNums = ref [2..(int UpperLimit)] in
// loop through all numbers
// keep removing numbers that divide evenly
for div = 2 to UpperBound do
  LNums := List.filter(fun num -> (num % div <> 0 || div >= num))
        !LNums
done;
let Primes:list<int> = !LNums

//numbers to check
let nums = [13 .. 6000]

let NonPrime =
     (Set.ofList nums) - (Set.ofList Primes) |> Set.toList |> List.filter (fun x -> x % 2 <> 0)

Console.WriteLine("Starting check")
let watch = new Stopwatch()
watch.Start()

let Check number =
    let mutable RetValue = true
    for n in Primes do
        for c in [1..100] do
            if (n + (2 * (c * c))) = number then
                RetValue <- false
    RetValue

let N =
    NonPrime
    |> Seq.filter Check
    |> Seq.toArray

watch.Stop()
Console.WriteLine(N.[0])
Console.WriteLine(watch.Elapsed)
Console.ReadKey()