PROJECT EULER #79

Link to Project Euler problem 79

A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

Did this by hand but then I felt like I had to come up with a coded solution too.

using System;
using System.Collections.Generic;
using System.IO;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 79
            DateTime start = DateTime.Now;
            var sr = new StreamReader(@"../../keylog.txt");
            var keys = new List<string>();
            while (!sr.EndOfStream)keys.Add(sr.ReadLine());
            for (int i = 0; i < keys.Count - 1; i++)
                for (int j = i + 1; j < keys.Count; j++)
                    if (keys[i] == keys[j])
                        keys.Remove(keys[j]);
            var cList = new List<char>();
            foreach (string s in keys)
            {
                char[] c = s.ToCharArray();
                foreach (char c1 in c)
                    if (!cList.Contains(c1))
                        cList.Add(c1);
            }
            var answer=new char[cList.Count];
            foreach (char c in cList)
            {
                var digitsRight = new List<char>();
                foreach (string s in keys)
                    if (s.Contains(c.ToString()))
                    {
                        int n = s.IndexOf(c);
                        if (n != s.Length - 1)
                            for (int i = n + 1; i < s.Length; i++)
                            {
                                char d = char.Parse(s.Substring(i, 1));
                                if (!digitsRight.Contains(d))
                                    digitsRight.Add(d);
                            }
                    }
                answer[cList.Count-(digitsRight.Count+1)] = c;
            }
            Console.WriteLine(new string(answer));
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

PROJECT EULER #78

Link to Project Euler problem 78

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.

Well this was difficult, not to mention memory hungry. This solution ate about 4-5 gigs of ram before coming up with the answer in the nick of time. It's a variation on the two previous problems.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 78
            DateTime start = DateTime.Now;
            var pOfN = new List<int[]> { new[] { 1 }, new[] { 1,1 } };
            int max = 0;
            bool success = false;
            int n = 1;
            while (!success)
            {
                n++;
                int[] thisN = new int[n+1];
                thisN[0] = 0;
                thisN[1] = 1;
                for (int i = 2; i < n+1; i++)
                {
                    int k = n - i;
                    if (k < 0)
                        thisN[i] = thisN[i - 1];
                    else if (i < k)
                        thisN[i] = thisN[i - 1] + pOfN[k][i];
                    else
                        thisN[i] = thisN[i - 1] + pOfN[k][k];
                    if (thisN[i] > 10000000)
                        thisN[i] = thisN[i]%1000000;
                }
                if (thisN[thisN.Length - 1]%10000 == 0)
                    Console.WriteLine(thisN[thisN.Length - 1] + ", " + n);
                pOfN.Add(thisN);
                if (thisN[thisN.Length-1]%1000000==0)
                {
                    max = n;
                    success = true;
                }
            }
            Console.Write(pOfN[max][max]+", "+max);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

PROJECT EULER #77

Link to Project Euler problem 77

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

A modification of the previous algorithm

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 77
            DateTime start = DateTime.Now;
            var primes = GeneratePrimes(80);
            int maxNumber = 80,target=0,sum=0;
            int[,] a = new int[maxNumber + 1, maxNumber + 1];
            for (int i = 0; i < maxNumber + 1; i++)
            {
                a[i, 0] = 0;
                a[0, i] = 1;
            }
            int n = 2;
            while (sum < 5000)
            {
                    if (n%2 == 0) a[n, 1] = 1;
                    else a[n, 1] = 0;
                    for (int j = 2; j < primes.Count; j++)
                    {
                        int k = n - primes[j];
                        if (k < 0)
                            a[n, j] = a[n, j - 1];
                        else
                            a[n, j] = a[n, j - 1] + a[k, j];
                        if (a[n, j] > 5000)
                        {
                            target = n;
                            sum = a[n, j];
                            break;
                        }
                    }
                n++;
            }
            Console.WriteLine(sum + "  " +target);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static bool IsPrime(int n)
        {
            if (n < 2) return false;
            if (n == 2) return true;
            for (long i = 2; i <= Math.Sqrt(n); i++)
                if (n % i == 0) return false;
            return true;
        }
        public static List<int> GeneratePrimes(int n)
        {
            var primeNumbers = new List<int> { 0,2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primeNumbers.Add(i);
            return primeNumbers;
        }
    }
}

PROJECT EULER #76

Link to Project Euler problem 76

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Here we go...yet more virgin territory for me, but isn't that the point?
Partitions....the clue is to store values somewhere, so we do it in a 2-D grid.

using System;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 76
            DateTime start = DateTime.Now;
            int n = 100;
            int[,] a = new int[n + 1, n + 1];
            for (int i = 0; i < n + 1; i++)
            {
                a[i, 0] = 0;
                a[0, i] = 1;
            }
            for (int i = 1; i < n + 1; i++)
            {
                a[i, 1] = 1;
                for (int j = 2; j < n + 1; j++)
                {
                    int k = i - j;
                    if (k < 0)
                        a[i, j] = a[i, j - 1];
                    else
                        a[i, j] = a[i, j - 1] + a[k, j];
                }
            }
            Console.WriteLine(a[n, n - 1]);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

PROJECT EULER #75

Link to Project Euler problem 75

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L 2,000,000 can exactly one integer sided right angle triangle be formed?

Using the two integer (m,n) technique for generating Pythagorean triples,I verify that they are primitive (using the IsRelativelyPrime method) then generate the non-primitives by simple scaling. Most of the time used goes to generate the list of prime factors of every number up to 2100000. The rest of the code uses 600 ms.

using System;
using System.Collections.Generic;

namespace project_euler
{
  class Program
  {
      public static Dictionary<int,List<int>> primeFactors = GeneratePrimeFactors(2100000);
      static void Main()
      {
          //Problem 75
          DateTime start = DateTime.Now;
          var pythagorasRecord = new Dictionary<long, int>();
          int count = 0;
          for (int m = 2; m < 1000000/m; m++)
              for (int n = 1; n < m; n++)
              {
                  long littleLeg = 2*m*n;
                  long bigLeg = m*m - n*n;
                  long hypotenuse = m*m + n*n;
                  if (IsRelativelyPrime(bigLeg, littleLeg))
                  {
                      long perimeter = littleLeg + bigLeg + hypotenuse;
                      long sum = perimeter;
                      while (sum <= 2000000)
                      {
                          if (pythagorasRecord.ContainsKey(sum))
                              pythagorasRecord[sum] += 1;
                          else
                              pythagorasRecord.Add(sum, 1);
                          sum += perimeter;
                      }
                  }
              }
          foreach (KeyValuePair<long, int> pair in pythagorasRecord)
              if (pair.Value == 1)
                  count++;
          Console.WriteLine(count);
          TimeSpan time = DateTime.Now - start;
          Console.WriteLine("This took {0}", time);
          Console.ReadKey();
      }
      public static bool IsRelativelyPrime (long m,long n)
      {
          foreach (long i in primeFactors[(int)m])
              if (n % i == 0) return false;
          return true;
      }
      public static Dictionary<int,List<int>> GeneratePrimeFactors(int n)
      {
          var primes = GeneratePrimes(n);
          var pF = new Dictionary<int, List<int>>();
          pF.Add(0,new List<int>{0});
          for (int i = 1; i <= n; i++)
              pF.Add(i,new List<int>());
          if (n == 1) return pF;
          foreach (int i in primes)
              for (int j = i; j <= n; j += i)
                  pF[j].Add(i);
          return pF;
      }
      public static bool IsPrime(int n)
      {
          if (n < 2) return false;
          if (n == 2) return true;
          for (long i = 2; i <= Math.Sqrt(n); i++)
              if (n % i == 0) return false;
          return true;
      }
      public static List<int> GeneratePrimes(int n)
      {
          var primeNumbers = new List<int> { 2, 3 };
          for (int i = 5; i <= n; i += 2)
              if (IsPrime(i))
                  primeNumbers.Add(i);
          return primeNumbers;
      }
  }
}

PROJECT EULER #74

Link to Project Euler problem 74

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:
169 -> 363601 -> 1454 -> 169
871 -> 45361 -> 871
872 -> 45362 -> 872
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 -> 363600 -> 1454 -> 169 -> 363601 (-> 1454)
78 -> 45360 -> 871 -> 45361 (-> 871)
540 -> 145 (-> 145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

This took too long (38 s) but I don't see any obvious optimisations (yet).

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        public static List<long> factorials = GenerateFactorials(9);
        static void Main()
        {
            //Problem 74
            DateTime start = DateTime.Now;
            int sixties = 0;
            for (int i = 1; i < 1000000; i++)
            {
                int count = 0;
                var cycle = new List<long>();
                long number = i;
                while (!cycle.Contains(number))
                {
                    count++;
                    cycle.Add(number);
                    number = GenerateSumOfFactorials(number);
                }
                if (count == 60)
                    sixties++;
            }
            Console.WriteLine(sixties);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static List<long> GenerateFactorials(int n)
        {
            var factorialList = new List<long> { 1 };
            for (int i = 1; i <= n; i++)
            {
                long factorial = 1;
                for (int j = 1; j <= i; j++)
                    factorial *= j;
                factorialList.Add(factorial);
            }
            return factorialList;
        }
        public static long GenerateSumOfFactorials(long n)
        {
            string s = n.ToString();
            long sum = 0;
            for (int i = 0; i < s.Length; i++)
                sum += factorials[int.Parse(s.Substring(i, 1))];
            return sum;
        }
    }
}

PROJECT EULER #73

Link to Project Euler problem 73

Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 10,000?

Yet again a big thanks to my mentor: After trying to brute-force this by generating all the fractions using the a/b < c/d ...insert (a+c) /(b+d) if b+d = n, type of solution (I stopped the program after 40 mins) he suggested looking at this strategy (took 1.05 s):

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 73
            DateTime start = DateTime.Now;
            int number =10000;
            var primeFactors = GeneratePrimeFactors(number);
            int max = 0,min=0,sum=0;
            for (int i = number; i > 3; i--)
            {
                int count = 0;
                max = (int) Math.Floor((decimal) i/2);
                min=(int)Math.Ceiling((decimal) i/3);
                for (int j = min; j <=max; j++)
                {
                    int test = primeFactors[i].Count;
                    foreach (int k in primeFactors[i])
                        if (j%k == 0)
                            test--;
                    if (test == primeFactors[i].Count)
                        count++;
                }
                sum += count;
            }
            Console.WriteLine(sum);
            Console.WriteLine();
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static List<List<int>> GeneratePrimeFactors(int n)
        {
            var primes = GeneratePrimes(n);
            var primeFactors = new List<List<int>> {new List<int> {0}};
            for (int i = 1; i <= n; i++)
                primeFactors.Add(new List<int>());
            if (n==1) return primeFactors;
            foreach (int i in primes)
                for (int j = i; j <= n; j += i)
                    primeFactors[j].Add(i);
            return primeFactors;
        }
        public static bool IsPrime(int n)
        {
            if (n < 2) return false;
            if (n == 2) return true;
            for (long i = 2; i <= Math.Sqrt(n); i++)
                if (n % i == 0) return false;
            return true;
        }
        public static List<int> GeneratePrimes(int n)
        {
            var primeNumbers = new List<int> { 2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primeNumbers.Add(i);
            return primeNumbers;
        }
    }
}

PROJECT EULER #72

Link to Project Euler problem 72

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d <= 1,000,000?

This was really beautiful. First I brute-forced it, using 35 minutes and then I searched the solution-forum for a better algorithm, without success. Then my mentor suggested this approach, which is so elegant that it deserves a name: The Sieve of Senehtsotare...16 seconds!

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 72
            DateTime start = DateTime.Now;
            int number = 1000000;
            BigInt sum = new BigInt("1");
            var tots = GenerateTotients(number);
            foreach (KeyValuePair<int, int> pair in tots)
                sum += pair.Value;
            Console.WriteLine(sum-2);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static List<List<int>> GeneratePrimeFactors(int n)
        {
            var primes = GeneratePrimes(n);
            var primeFactors = new List<List<int>>();
            primeFactors.Add(new List<int>{0});
            for (int i = 1; i <= n; i++)
                primeFactors.Add(new List<int>());
            if (n==1) return primeFactors;
            foreach (int i in primes)
                for (int j = i; j <= n; j += i)
                    primeFactors[j].Add(i);
            return primeFactors;
        }
        public static Dictionary<int, int> GenerateTotients(int n)
        {
            var totients = new Dictionary<int, int>{{0,0}};
            List<List<int>> primeFactors = GeneratePrimeFactors(n);
            for (int i = 1; i < primeFactors.Count; i++)
            {
                double totient = i;
                foreach (int j in primeFactors[i])
                    totient *= 1 - 1/(double) j;
                totients.Add(i,(int)totient);
            }
            return totients;
        }
        public static bool IsPrime(int n)
        {
            if (n < 2) return false;
            if (n == 2) return true;
            for (long i = 2; i <= Math.Sqrt(n); i++)
                if (n % i == 0) return false;
            return true;
        }
        public static List<int> GeneratePrimes(int n)
        {
            var primeNumbers = new List<int> { 2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primeNumbers.Add(i);
            return primeNumbers;
        }
    }
}

PROJECT EULER #71

Link to Project Euler problem 71

Consider the fraction, n/d, where n and d are positive integers. If nd and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

This turned out to be too easy, althought the wording of the problem does say

By listing the set of reduced proper fractions......

and I didn't do that...

using System;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 71
            DateTime start = DateTime.Now;
            int a=2,b=5,c=3,d=7;
            while (b+d<=1000000)
            {
                a = a + c;
                b = b + d;
            }
            Console.WriteLine(a + "/"+b);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

PROJECT EULER #70

Link to Project Euler problem 70

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to 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.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < src="http://projecteuler.net/index.php?section=problems&id=70" style="display: none;" alt="^(">⁷, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

Have to admit that I tried to brute-force this one and fell asleep on the couch. On awakening the answer lay there but the program would have happily run for some days (?) before completing. Armed with advice from the forum I learned that there are many ways to skin a totient...

Euler (from projecteuler.net) wrote:

Given n=p1e1p2e2...p1e1, φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pk).

Now for n/φ(n) to be minimised, φ(n) must be as close to n as possible; that is, we want to maximise φ(n).

When evaluating φ(n), we note that each time we multiply by (1-1/pi), it gets smaller, so we need to minimise the number of distinct prime factors in n.

If n were prime, it would end in 1,3,7, or 9, and subtracting 1 only changes the last digit (to 0,2,6, or 8), so it could not be a permutation.

Hence n=p1*p2 and we only need to search through a list of known prime pairs.

In addition, φ(p1*p2)=p1*p2*(1-1/p1)(1-1/p2)=(p1-1)(p2-1), so we can compute φ(n) more efficiently.

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
  private static List<int> primes = GenerateRangeOfPrimes(1000,5000);

  static void Main()
  {
      //Problem 70
      DateTime start = DateTime.Now;
      decimal min = 100;
      int number = 1;

      for (int j = primes.Count - 1; j >= 0; j--)
          for (int k = j - 1; k >= 1; k--)
          {
              int i = primes[j]*primes[k];
              if (i < 10000000)
              {
                  int totient = (primes[j] - 1)*(primes[k] - 1);
                  if (IsPermutation(i, totient))
                      if ((decimal) i/totient < min)
                      {
                          min = (decimal) i/totient;
                          number = i;
                          Console.WriteLine(number + ": " + min + " p1: " + primes[k] + " p2: " + primes[j]);
                      }
              }
          }
      TimeSpan time = DateTime.Now - start;
      Console.WriteLine("This took {0}", time);
      Console.ReadKey();
  }

  private static bool IsPermutation(int m,int n)
  {
      char[] c = m.ToString().ToCharArray();
      char[] d = n.ToString().ToCharArray();
      Array.Sort(c);
      Array.Sort(d);
      string s = new string(c);
      string t = new string(d);
      if (s == t) return true;
      return false;
  }

  private static bool IsPrime(int n)
  {
      if (n < 2) return false;
      if (n == 2) return true;
      for (long i = 2; i <= Math.Sqrt(n); i++)
          if (n % i == 0) return false;
      return true;
  }

  private static List<int> GenerateRangeOfPrimes(int m,int n)
  {
      var p = new List<int> { 2, 3 };
      for (int i = 5; i <= n; i += 2)
          if (IsPrime(i))
              p.Add(i);
      while (p[0] < m)
          p.Remove(p[0]);
      return p;
  }
}
}

PROJECT EULER #69

Link to Project Euler problem 69

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.

n	Relatively Prime	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

It can be seen that n=6 produces a maximum n/φ(n) for n 10.

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

Brute-forcing the totients up to a million would take hours (?) so I found a more elegant formula:

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
    private static List<int> primes = GeneratePrimes((int)Math.Sqrt(1000000));
    static void Main()
    {
        //Problem 69
        DateTime start = DateTime.Now;
        double max = 0;
        int number = 1;
        for (int i = 1000000; i >= 2; i--)
            if (i / Totient(i) > max)
            {
                max = i / Totient(i) > max ? i / Totient(i) : max;
                number = i;
            }
        Console.WriteLine(number);
        TimeSpan time = DateTime.Now - start;
        Console.WriteLine("This took {0}", time);
        Console.ReadKey();
    }

    public static double Totient(int n)
    {
        double totient = n;
        var primeFactorsOfN = new List<int>();
        foreach (int i in primes)
        {
            if (n % i == 0 && n != i) primeFactorsOfN.Add(i);
            if (i > Math.Sqrt(n)) break;
        }
        foreach (int i in primeFactorsOfN)
            totient *= 1 - 1 / (double)i;
        return totient;
    }

    public static bool IsPrime(int n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        for (long i = 2; i <= Math.Sqrt(n); i++)
            if (n % i == 0) return false;
        return true;
    }

    public static List<int> GeneratePrimes(int n)
    {
        var primes = new List<int> { 2, 3 };
        for (int i = 5; i <= n; i += 2)
            if (IsPrime(i))
                primes.Add(i);
        return primes;
    }
}
}

PROJECT EULER #68

Link to Project Euler problem 68

Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.

Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.

Total	Solution Set
9	4,2,3; 5,3,1; 6,1,2
9	4,3,2; 6,2,1; 5,1,3
10	2,3,5; 4,5,1; 6,1,3
10	2,5,3; 6,3,1; 4,1,5
11	1,4,6; 3,6,2; 5,2,4
11	1,6,4; 5,4,2; 3,2,6
12	1,5,6; 2,6,4; 3,4,5
12	1,6,5; 3,5,4; 2,4,6

By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?

Thanks to Michael, my employer and mentor, I managed to see the wisdom of creating a data structure (an Ngon) to hold the data. Well there's hope for me yet. This is only the second time during these problems that I've made an object as part of the solution. The permutation code is lifted from here, although I must add that I read Knuth's "The Art of Computer Programming - pre-fascicle 3A" to understand the concepts involved.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
   class Program
   {
       static void Main()
       {
           //Problem 68
           DateTime start = DateTime.Now;
           var numbers = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
           var result = Permute(numbers);
           List<long> allResults = new List<long>();
           foreach (int[] ints in result)
           {
               Ngon newNgon = new Ngon(ints);
               if (newNgon.IsMagic)
                   allResults.Add(newNgon.SolutionSet);
           }
           allResults.Sort();
           Console.WriteLine(allResults[allResults.Count - 1]);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }

       public static List<int[]> Permute(int[] values)
       {
           List<int[]> permList = new List<int[]>();
           permuteWorker(values, 0, values.Length, ref permList);
           return permList;
       }

       private static void permuteWorker(int[] values, int start, int n, ref List<int[]> permList)
       {
           if (start == n - 1)
           {
               int[] thisValues = new int[values.Length];
               values.CopyTo(thisValues, 0);
               permList.Add(thisValues);
           }
           else
           {
               for (int i = start; i < n; i++)
               {
                   int tmp = values[i];
                   values[i] = values[start];
                   values[start] = tmp;
                   permuteWorker(values, start + 1, n, ref permList);
                   values[start] = values[i];
                   values[i] = tmp;
               }
           }
       }

       public class Ngon
       {
           public List<int> Numbers { get; set; }
           //we have a pentagon, with point at top, and 5 'external' numbers
           //extending the sides of the pentagon to create 5 lines of numbers.
           //we number the internal points 0 to 4, and the external ones 5 to 9.
           //point 9 is always = 10. Numbers are clockwise with point 4 and point 9 at top.
           public Ngon(int[] numbers)
           {
               Point0 = numbers[0];
               Point1 = numbers[1];
               Point2 = numbers[2];
               Point3 = numbers[3];
               Point4 = numbers[4];
               Point5 = numbers[5];
               Point6 = numbers[6];
               Point7 = numbers[7];
               Point8 = numbers[8];
               Point9 = 10;
           }
           public int Point0 { get; private set; }
           public int Point1 { get; private set; }
           public int Point2 { get; private set; }
           public int Point3 { get; private set; }
           public int Point4 { get; private set; }
           public int Point5 { get; private set; }
           public int Point6 { get; private set; }
           public int Point7 { get; private set; }
           public int Point8 { get; private set; }
           public int Point9 { get; private set; }

           public int Line1Sum { get { return Point9 + Point4 + Point0; } }
           public int Line2Sum { get { return Point5 + Point0 + Point1; } }
           public int Line3Sum { get { return Point6 + Point1 + Point2; } }
           public int Line4Sum { get { return Point7 + Point2 + Point3; } }
           public int Line5Sum { get { return Point8 + Point3 + Point4; } }
           public int Line1
           {
               get
               {
                   int[] i = new int[3] { Point9, Point4, Point0 };
                   return 100 * i[0] + 10 * i[1] + i[2];
               }
           }
           public int Line2
           {
               get
               {
                   int[] i = new int[3] { Point5, Point0, Point1 };
                   return 100 * i[0] + 10 * i[1] + i[2];
               }
           }
           public int Line3
           {
               get
               {
                   int[] i = new int[3] { Point6, Point1, Point2 };
                   return 100 * i[0] + 10 * i[1] + i[2];
               }
           }
           public int Line4
           {
               get
               {
                   int[] i = new int[3] { Point7, Point2, Point3 };
                   return 100 * i[0] + 10 * i[1] + i[2];
               }
           }
           public int Line5
           {
               get
               {
                   int[] i = new int[3] { Point8, Point3, Point4 };
                   return 100 * i[0] + 10 * i[1] + i[2];
               }
           }
           public bool IsMagic
           {
               get
               {
                   if (Line1Sum == Line2Sum && Line1Sum == Line3Sum &&
                       Line1Sum == Line4Sum && Line1Sum == Line5Sum)
                       return true;
                   return false;
               }
           }

           public long SolutionSet
           {
               get
               {
                   int[] solutionSet = new int[5];
                   List<int> temp = new List<int>();
                   int min = 1000, index = 0;
                   temp.Add(Line1);
                   temp.Add(Line2);
                   temp.Add(Line3);
                   temp.Add(Line4);
                   temp.Add(Line5);
                   for (int i = 0; i < temp.Count; i++)
                       if (temp[i] < min)
                       {
                           min = temp[i];
                           index = i;
                       }
                   for (int i = 0; i < index; i++)
                       temp.Add(temp[i]);
                   temp.CopyTo(index, solutionSet, 0, 5);
                   string solution = "";
                   for (int i = 0; i < solutionSet.Length; i++)
                       solution += solutionSet[i];
                   return long.Parse(solution);
               }
           }
       }
   }
}

PROJECT EULER #67

Link to Project Euler problem 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 5
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.
NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

I solved this when I did problem 18 just because I found a good algorithm back then.

using System;
using System.Collections.Generic;
using System.IO;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 67
            DateTime start = DateTime.Now;
            StreamReader sr = new StreamReader(@"../../triangle.txt");
            //Treat the triangle as a 2 dimensional array[][]
            List<List<int>> triangle = new List<List<int>>();
            //make the triangle
            for (int i = 0; i < 100; i++)
            {
                string s = sr.ReadLine();
                char[] c = { ' ' };
                string[] sa = s.Split(c);
                List<int> line = new List<int>();
                foreach (string s1 in sa)
                    line.Add(int.Parse(s1));
                triangle.Add(line);
            }
            //row
            for (int i = 1; i < 100; i++)
                //column
                for (int j = 0; j <= i; j++)
                    //do the edges
                    if (j == 0)
                        triangle[i][0] = triangle[i][0] + triangle[i - 1][0];
                    else if (j == triangle[i].Count - 1)
                        triangle[i][triangle[i].Count - 1] = triangle[i][triangle[i].Count - 1] +
                                                             triangle[i - 1][triangle[i - 1].Count - 1];
                        //do the middle
                    else
                        triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j] > triangle[i - 1][j] + triangle[i][j]
                                             ? triangle[i - 1][j - 1] + triangle[i][j]
                                             : triangle[i - 1][j] + triangle[i][j];
            int max = 0;
            foreach (int i in triangle[triangle.Count - 1])
                max = i > max ? i : max;
            Console.WriteLine(max);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

PROJECT EULER #66

Link to Project Euler problem 66

Consider quadratic Diophantine equations of the form:
x² – Dy² = 1
For example, when D = 13, the minimal solution in x is 649² – 13 x 180² = 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 x 2² = 1
2² – 3 x 1² = 1
9² – 5 x 4² = 1
5² – 6 x 2² = 1
8² – 7 x 3² = 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.

This was the synthesis of the two previous questions, with a bit of study at wolfram.com (here and here) and some pencil and paper walkthroughs it was do-able. I guess I've used 15 hours to do these three problems. Uncommenting the commented statements prints the [a₀;(a₁,a₂,....a_r,a_r+1)] series and the p_r / q_r or p_2r+1 / q_2r+1 (depending on the parity of the series) convergents for each number.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
   class Program
   {
       static void Main()
       {
           //Problem 66
           DateTime start = DateTime.Now;
           //first the code from problem 64
           Dictionary<int, List<int>> numbers = new Dictionary<int, List<int>>();
           for (int number = 2; number <= 1000; number++)
           {
               bool repeat;
               int a = (int)Math.Sqrt(number);
               List<int> sequence = new List<int> { a };
               numbers.Add(number, sequence);
               int x = 1;
               do
               {
                   if (Math.Sqrt(number) - (int)Math.Sqrt(number) == 0) break;
                   int b = number - a * a;
                   int integerPart = x * ((int)Math.Sqrt(number) + a) / b;
                   numbers[number].Add(integerPart);
                   a = -(a - integerPart * (b / x));
                   x = (b / x);
                   repeat = integerPart == 2 * numbers[number][0] ? true : false;
               } while (!repeat);
           }
           //then the modified code from problem 65
           BigInt maxNumerator=0;
           int d = 0;
           for (int i = 2; i <= 1000; i++)
           {
               if (Math.Sqrt(i) - (int)Math.Sqrt(i)!=0)
               {
                   int r = numbers[i].Count-1;
                   BigInt numerator_2 = 0, numerator_1 = 1, numerator = 0;
                   BigInt denominator_2 = 1, denominator_1 = 0, denominator = 0;
                   //var sequence = numbers[i];
             
                   if ((r) % 2 != 0)//is odd
                   {
                       //Console.Write("r is even ");
                       //Console.Write("Sqrt " + i + ": [");
                       //Console.Write(sequence[0] + ";(");
                       //for (int j = 1; j < sequence.Count; j++)
                       //    if (j < sequence.Count - 1)
                       //        Console.Write(sequence[j] + ",");
                       //    else
                       //        Console.WriteLine(sequence[j] + ")]");
                       //Console.WriteLine();
                       for (int j = 0; j < numbers[i].Count; j++)
                       {
                           numerator = numbers[i][j] * numerator_1 + numerator_2;
                           numerator_2 = numerator_1;
                           numerator_1 = numerator;
                           denominator = numbers[i][j] * denominator_1 + denominator_2;
                           denominator_2 = denominator_1;
                           denominator_1 = denominator;
                       }
                       for (int j = 1; j < numbers[i].Count-1; j++)
                       {
                           numerator = numbers[i][j] * numerator_1 + numerator_2;
                           numerator_2 = numerator_1;
                           numerator_1 = numerator;
                           denominator = numbers[i][j] * denominator_1 + denominator_2;
                           denominator_2 = denominator_1;
                           denominator_1 = denominator;
                       }
                   }
                   else//is even
                   {
                       //Console.Write("r is odd");
                       //Console.Write("Sqrt " + i + ": [");
                       //Console.Write(sequence[0] + ";(");
                       //for (int j = 1; j < sequence.Count; j++)
                       //    if (j < sequence.Count - 1)
                       //        Console.Write(sequence[j] + ",");
                       //    else
                       //        Console.WriteLine(sequence[j] + ")]");
                       //Console.WriteLine();
                       for (int j = 0; j < numbers[i].Count-1; j++)
                       {
                           numerator = numbers[i][j] * numerator_1 + numerator_2;
                           numerator_2 = numerator_1;
                           numerator_1 = numerator;
                           denominator = numbers[i][j] * denominator_1 + denominator_2;
                           denominator_2 = denominator_1;
                           denominator_1 = denominator;
                       }
                   }
                   if (numerator > maxNumerator)
                   {
                       maxNumerator = numerator;
                       d = i;
                   }
                   //Console.WriteLine("x = " + numerator.ToString());
                   //Console.WriteLine("y = " + denominator.ToString());
                   //Console.WriteLine("-----------------------------------------");
               }
           }
           Console.WriteLine(d);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #65

Link to Project Euler problem 65

The square root of 2 can be written as an infinite continued fraction.

2 = 1 +	1
	2 +	1
		2 +	1
			2 +	1
				2 + ...

The infinite continued fraction can be written, 2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, 23 = [4;(1,3,1,8)].

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for 2.

1 +	1	= 3/2
	2

1 +	1		= 7/5
	2 +	1
		2

1 +	1			= 17/12
	2 +	1
		2 +	1
			2

1 +	1				= 41/29
	2 +	1
		2 +	1
			2 +	1
				2

Hence the sequence of the first ten convergents for 2 are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...

What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

The first ten terms in the sequence of convergents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...

The sum of digits in the numerator of the 10^th convergent is 1+4+5+7=17.

Find the sum of digits in the numerator of the 100^th convergent of the continued fraction for e.

using System;

namespace project_euler
{
  class Program
  {
      static void Main()
      {
          //Problem 65
          DateTime start = DateTime.Now;
          //e = [2;1,2,1,1,4,1,1,6,1,....,1,2k,1,...]
          //numerator_n = a_n * numerator_n-1 + numerator_n-2
          //denominator_n = a_n * denominator_n-1 + denominator_n-2
          BigInt numerator_2 = 2, numerator_1 = 3, numerator=0;
          //BigInt denominator_1 = 1,denominator_2 = 1, denominator;
          int    sum = 0;
          for (int i = 2; i < 100; i++)
          {
              int a = (i + 1) % 3 == 0 ? 2 * ((i + 1) / 3) : 1;
              numerator = numerator_1 * a + numerator_2;
              numerator_2 = numerator_1;
              numerator_1 = numerator;
              //denominator = a * denominator_1 + denominator_2;
              //denominator_2 = denominator_1;
              //denominator_1 = denominator;
              //Console.WriteLine(numerator);
              //Console.WriteLine("-----------------------------------------");
              //Console.WriteLine(denominator);
          }
          char[] c = numerator.ToString().ToCharArray();
          foreach (char c1 in c)
              sum += int.Parse(c1.ToString());
          Console.WriteLine(sum);
          TimeSpan time = DateTime.Now - start;
          Console.WriteLine("This took {0}", time);
          Console.ReadKey();
      }
  }
}

PROJECT EULER #64

Link to Project Euler problem 64

All square roots are periodic when written as continued fractions and can be written in the form:

N = a0 +	1
	a1 +	1
		a2 +	1
			a3 + ...

For example, let us consider 23:

23 = 4 + 23 — 4 = 4 +	1	= 4 +	1
	1 23—4		1 +	23 – 3 7

If we continue we would get the following expansion:

23 = 4 +	1
	1 +	1
		3 +	1
			1 +	1
				8 + ...

The process can be summarised as follows:

a0 = 4,		1 23—4	=	23+4 7	= 1 +	23—3 7
a1 = 1,		7 23—3	=	7(23+3) 14	= 3 +	23—3 2
a2 = 3,		2 23—3	=	2(23+3) 14	= 1 +	23—4 7
a3 = 1,		7 23—4	=	7(23+4) 7	= 8 +	23—4
a4 = 8,		1 23—4	=	23+4 7	= 1 +	23—3 7
a5 = 1,		7 23—3	=	7(23+3) 14	= 3 +	23—3 2
a6 = 3,		2 23—3	=	2(23+3) 14	= 1 +	23—4 7
a7 = 1,		7 23—4	=	7(23+4) 7	= 8 +	23—4

It can be seen that the sequence is repeating. For conciseness, we use the notation 23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

2=[1;(2)], period=1
3=[1;(1,2)], period=2
5=[2;(4)], period=1
6=[2;(2,4)], period=2
7=[2;(1,1,1,4)], period=4
8=[2;(1,4)], period=2
10=[3;(6)], period=1
11=[3;(3,6)], period=2
12= [3;(2,6)], period=2
13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N 13, have an odd period.

How many continued fractions for N 10000 have an odd period?

This was certainly an education in continued fractions. Having understood them the trick is to find a way to calculate the salient numbers for the next iteration. 62.5 ms. Uncomment the foreach loop to print the series.

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
   static void Main()
   {
       //Problem 64
       DateTime start = DateTime.Now;
       Dictionary<int, List<int>> numbers = new Dictionary<int, List<int>>();
       for (int number = 2; number <= 10000; number++)
       {
           bool repeat = false;
           int a = (int)Math.Sqrt(number);
           List<int> sequence = new List<int> { a };
           numbers.Add(number, sequence);
           int x = 1;
           do
           {
               if (Math.Sqrt(number) - (int)Math.Sqrt(number) == 0) break;
               int b = number - a * a;
               int integerPart = x * ((int)Math.Sqrt(number) + a) / b;
               numbers[number].Add(integerPart);
               a = -(a - integerPart * (b / x));
               x = (b / x);
               if (integerPart == 2 * numbers[number][0]) repeat = true;
           } while (!repeat);
       }
       int oddSequence=0;
       foreach (KeyValuePair<int, List<int>> pair in numbers)
       {
           if ((pair.Value.Count - 1)%2 != 0)
               oddSequence++;
           //Console.Write(pair.Key + ": ");
           //foreach (int sequence in pair.Value)
           //    Console.Write(sequence + ", ");
           //Console.WriteLine();
       }
       Console.WriteLine(oddSequence);
       TimeSpan time = DateTime.Now - start;
       Console.WriteLine("This took {0}", time);
       Console.ReadKey();
   }
}
}