Project Euler in C#

PROJECT EULER #79

2009-04-30T14:12:00.002+02:00

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

2009-04-30T11:43:00.003+02:00

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

2009-04-29T14:52:00.003+02:00

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

2009-04-29T10:59:00.003+02:00

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

2009-04-28T23:51:00.003+02:00

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

2009-04-28T14:47:00.005+02:00

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

2009-04-28T13:51:00.004+02:00

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

2009-04-28T10:10:00.005+02:00

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

2009-04-27T10:15:00.003+02:00

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

2009-04-25T09:47:00.005+02:00

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

2009-04-24T22:15:00.004+02:00

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

2009-04-24T13:53:00.004+02:00

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

2009-04-23T12:08:00.004+02:00

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

2009-04-23T11:46:00.005+02:00

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

2009-04-21T23:52:00.004+02:00

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

2009-04-21T18:19:00.006+02:00

Link to Project Euler problem 64

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

N = a₀ +	1
	a₁ +	1
		a₂ +	1
			a₃ + ...

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:

a₀ = 4,	1 23—4	=	23+4 7	= 1 +	23—3 7
a₁ = 1,	7 23—3	=	7(23+3) 14	= 3 +	23—3 2
a₂ = 3,	2 23—3	=	2(23+3) 14	= 1 +	23—4 7
a₃ = 1,	7 23—4	=	7(23+4) 7	= 8 +	23—4
a₄ = 8,	1 23—4	=	23+4 7	= 1 +	23—3 7
a₅ = 1,	7 23—3	=	7(23+3) 14	= 3 +	23—3 2
a₆ = 3,	2 23—3	=	2(23+3) 14	= 1 +	23—4 7
a₇ = 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();
   }
}
}

PROJECT EULER #63

2009-04-20T11:22:00.008+02:00

Link to Project Euler problem 63

The 5-digit number, 16807=7⁵, is also a fifth power. Similarly, the 9-digit number, 134217728=8⁹, is a ninth power.
How many n-digit positive integers exist which are also an nth power?

Using BigInt was one way, but there is a more elegant solution using logs:
number of digits in 100 = 3, 1000 = 4,
log 100 = 2, log 1000 = 3.
number of digits in 567 = (int)((log 567)+1) = (int)2.75 + 1 = 3
number of digits in x = (int)(log x) + 1
number of digits in x^y = (int)((y * log x) + 1)
number of digits in 10^y = y + 1, so only x = 1 to 9 hold solutions
then if x^y = y digits, =>
y = (int) y * log x + 1, => (divide by y)
1 = (int) log x + 1 / y, => (subtract log x)
1 / y = (int)(1 - log x), => (invert)
y = (int)(1/(1 - log x)).

The BigInt solution:


using System;

namespace ProjectEuler
{
   class Program
   {
       static void Main()
       {
           //Problem 63
           DateTime start = DateTime.Now;
           int count = 0;
           for (int i = 1; i < 10; i++)
           {
               BigInt n = new BigInt(1);
               for (int j = 1; j < 25; j++)
               {
                   n *= i;
                   if (n.ToString().Length==j)
                       count++;
               }
           }
           Console.WriteLine(count);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
   }
}

The log solution:


using System;

namespace ProjectEuler
{
   class Program
   {
       static void Main()
       {
           //Problem 63
           DateTime start = DateTime.Now;
           int count = 0;
           for (int i = 1; i < 10; i++)
               count += (int) (1/(1 - Math.Log10(i)));
           Console.WriteLine(count);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
   }
}

Triple-click for answer: 49

PROJECT EULER #62

2009-04-20T09:16:00.003+02:00

Link to Project Euler problem 62

The cube, 41063625 (345³), can be permuted to produce two other cubes: 56623104 (384³) and 66430125 (405³). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.
Find the smallest cube for which exactly five permutations of its digits are cube.


using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 62
            DateTime start = DateTime.Now;

            bool success = false;
            Dictionary<int, string> sortedStrings = new Dictionary<int, string>();

            for (int i = 5000; i < 10000; i++)
            {
                BigInt cube = new BigInt(i);
                cube *= i * i;
                char[] c = cube.ToString().ToCharArray();
                Array.Sort(c);
                string s = new string(c);
                if (s.StartsWith("-"))
                    s.Remove(0, 1);
                sortedStrings.Add(i, s);
            }
            for (int i = 5000; i < 9999; i++)
            {
                string s;
                sortedStrings.TryGetValue(i, out s);
                int[] allCubes = new int[5];
                allCubes[0] = i;
                int count = 1;
                for (int j = i + 1; j < 10000; j++)
                {
                    string t;
                    sortedStrings.TryGetValue(j, out t);
                    if (s == t)
                    {
                        count++;
                        allCubes[count - 1] = j;
                    }
                    if (count == 5)
                    {
                        for (int k = 0; k < 5; k++)
                        {
                            int n = allCubes[k];
                            BigInt number = new BigInt(n);
                            number *= n*n;
                            Console.WriteLine(allCubes[k]);
                            Console.WriteLine(number);
                        }
                        Console.WriteLine();
                        success = true;
                        break;
                    }
                }
                if (success) break;
            }
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

Triple-click for answer: 127035954683

PROJECT EULER #61

2009-04-19T23:38:00.006+02:00

Link to Project Euler problem 61

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

Triangle	P_3,n=n(n+1)/2	1, 3, 6, 10, 15, ...
Square	P_4,n=n²	1, 4, 9, 16, 25, ...
Pentagonal	P_5,n=n(3n-1)/2	1, 5, 12, 22, 35, ...
Hexagonal	P_6,n=n(2n-1)	1, 6, 15, 28, 45, ...
Heptagonal	P_7,n=n(5n-3)/2	1, 7, 18, 34, 55, ...
Octagonal	P_8,n=n(3n-2)	1, 8, 21, 40, 65, ...

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
Each polygonal type: triangle (P_3,127=8128), square (P_4,91=8281), and pentagonal (P_5,44=2882), is represented by a different number in the set.
This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

This has to be the ugliest thing I've written, but at 375 ms what the heck! I worked out the smallest number in the set for each figurate type which would result in a 4 digit number, then I create them and add them all to a dictionary with a key specifying the type and the number from the set, then I do 6 nested foreaches (yes it smells!) with conditions. The program finds 6 identical solutions (of course) so I stop it when 1 is found. The keys and values are printed to make sure I got it right!


using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
  static void Main()
  {
      //Problem 61
      DateTime start = DateTime.Now;
      bool finished = false;
      var numbers = new Dictionary<string, string>();
      for (int i = 45; i * (i + 1) / 2 < 10000; i++)
          numbers.Add("tri" + i, (i * (i + 1) / 2).ToString());
      for (int j = 32; j * j < 10000; j++)
          numbers.Add("squ" + j, (j * j).ToString());
      for (int k = 26; k * (3 * k - 1) < 10000; k++)
          numbers.Add("pen" + k, (k * (3 * k - 1) / 2).ToString());
      for (int l = 23; l * (2 * l - 1) < 10000; l++)
          numbers.Add("hex" + l, (l * (2 * l - 1)).ToString());
      for (int m = 21; m * (5 * m - 3) / 2 < 10000; m++)
          numbers.Add("hep" + m, (m * (5 * m - 3) / 2).ToString());
      for (int n = 19; n * (3 * n - 2) < 10000; n++)
          numbers.Add("oct" + n, (n * (3 * n - 2)).ToString());
      //pick a number, find its type and original int,
      foreach (KeyValuePair<string, string> pair1 in numbers)
      {
          string s = pair1.Value;
          string sk = pair1.Key;
          string sn = sk.Substring(3, sk.Length - 3);
          string sm = sk.Substring(0, 3);
          foreach (KeyValuePair<string, string> pair2 in numbers)
              if (!pair2.Key.StartsWith(sm) &&
                  pair2.Key.Substring(3, pair2.Key.Length - 3) != sn)
                  if (pair2.Value.StartsWith(s.Substring(2, 2)))
                  {
                      string t = pair2.Value;
                      string tk = pair2.Key;
                      string tn = tk.Substring(3, tk.Length - 3);
                      string tm = tk.Substring(0, 3);
                      foreach (KeyValuePair<string, string> pair3 in numbers)
                          if (!pair3.Key.StartsWith(sm) &&
                              !pair3.Key.StartsWith(tm) &&
                              pair3.Key.Substring(3, pair3.Key.Length - 3) != sn &&
                              pair3.Key.Substring(3, pair3.Key.Length - 3) != tn)
                              if (pair3.Value.StartsWith(t.Substring(2, 2)))
                              {
                                  string u = pair3.Value;
                                  string uk = pair3.Key;
                                  string un = uk.Substring(3, uk.Length - 3);
                                  string um = uk.Substring(0, 3);
                                  foreach (KeyValuePair<string, string> pair4 in numbers)
                                      if (!pair4.Key.StartsWith(sm) &&
                                          !pair4.Key.StartsWith(tm) &&
                                          !pair4.Key.StartsWith(um) &&
                                          pair4.Key.Substring(3, pair4.Key.Length - 3) != sn &&
                                          pair4.Key.Substring(3, pair4.Key.Length - 3) != tn &&
                                          pair4.Key.Substring(3, pair4.Key.Length - 3) != un)
                                          if (pair4.Value.StartsWith(u.Substring(2, 2)))
                                          {
                                              string v = pair4.Value;
                                              string vk = pair4.Key;
                                              string vn = vk.Substring(3, vk.Length - 3);
                                              string vm = vk.Substring(0, 3);
                                              foreach (KeyValuePair<string, string> pair5 in numbers)
                                                  if (!pair5.Key.StartsWith(sm) &&
                                                      !pair5.Key.StartsWith(tm) &&
                                                      !pair5.Key.StartsWith(um) &&
                                                      !pair5.Key.StartsWith(vm) &&
                                                      pair5.Key.Substring(3, pair5.Key.Length - 3) != sn &&
                                                      pair5.Key.Substring(3, pair5.Key.Length - 3) != tn &&
                                                      pair5.Key.Substring(3, pair5.Key.Length - 3) != un &&
                                                      pair5.Key.Substring(3, pair5.Key.Length - 3) != vn)
                                                      if (pair5.Value.StartsWith(v.Substring(2, 2)))
                                                      {
                                                          string w = pair5.Value;
                                                          string wk = pair5.Key;
                                                          string wn = wk.Substring(3, wk.Length - 3);
                                                          string wm = wk.Substring(0, 3);
                                                          foreach (KeyValuePair<string, string> pair6 in numbers)
                                                              if (!pair6.Key.StartsWith(sm) &&
                                                                  !pair6.Key.StartsWith(tm) &&
                                                                  !pair6.Key.StartsWith(um) &&
                                                                  !pair6.Key.StartsWith(vm) &&
                                                                  !pair6.Key.StartsWith(wm) &&
                                                                  pair6.Key.Substring(3, pair6.Key.Length - 3) != sn &&
                                                                  pair6.Key.Substring(3, pair6.Key.Length - 3) != tn &&
                                                                  pair6.Key.Substring(3, pair6.Key.Length - 3) != un &&
                                                                  pair6.Key.Substring(3, pair6.Key.Length - 3) != vn &&
                                                                  pair6.Key.Substring(3, pair6.Key.Length - 3) != wn)
                                                                  if (pair6.Value.StartsWith(w.Substring(2, 2)) &&
                                                                      pair6.Value.Substring(2, 2) == s.Substring(0, 2))
                                                                  {
                                                                      string x = pair6.Value;
                                                                      string xk = pair6.Key;
                                                                      int sum = int.Parse(s) +
                                                                                int.Parse(t) +
                                                                                int.Parse(u) +
                                                                                int.Parse(v) +
                                                                                int.Parse(w) +
                                                                                int.Parse(x);
                                                                      Console.WriteLine(sum);
                                                                      Console.WriteLine(sk + " " + tk + " " + uk + " " + vk + " " + wk + " " + xk);
                                                                      Console.WriteLine(s + " " + t + " " + u + " " + v + " " + w + " " + x);
                                                                      finished = true;
                                                                      break;
                                                                  }
                                                          if (finished) break;
                                                      }
                                              if (finished) break;
                                          }
                                  if (finished) break;
                              }
                      if (finished) break;
                  }
          if (finished) break;
      }
      TimeSpan time = DateTime.Now - start;
      Console.WriteLine("This took {0}", time);
      Console.ReadKey();
  }
}
}

Triple-click for answer: 28684

PROJECT EULER #60

2009-04-19T19:16:00.005+02:00

Link to Project Euler problem 60

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.

A more brute-force approach is probably not possible to achieve...but it runs in less than 8 seconds so I'm not complaining! I also took for granted that the first result would be the lowest sum.

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
  static void Main()
  {
      //Problem 60
      DateTime start = DateTime.Now;
      List<int> primes = GeneratePrimes(10000);
      int sum;
      bool finished = false;
      for (int i = 0; i < primes.Count-4; i++)
      {
          string s = primes[i].ToString();
          for (int j = i+1; j < primes.Count-3; j++)
          {
              string t = primes[j].ToString();
              if (IsPrime(int.Parse(s + t)) &&
                  IsPrime(int.Parse(t + s)))
              {
                  for (int k = j+1; k < primes.Count-2; k++)
                  {
                      string u = primes[k].ToString();
                      if (IsPrime(int.Parse(s + u)) &&
                          IsPrime(int.Parse(u + s)) &&
                          IsPrime(int.Parse(t + u)) &&
                          IsPrime(int.Parse(u + t)))
                      {
                          for (int l = k+1; l < primes.Count-1; l++)
                          {
                              string v = primes[l].ToString();
                              if (IsPrime(int.Parse(s + v))&&
                                  IsPrime(int.Parse(t + v))&&
                                  IsPrime(int.Parse(u + v))&&
                                  IsPrime(int.Parse(v + s))&&
                                  IsPrime(int.Parse(v + t))&&
                                  IsPrime(int.Parse(v + u)))
                              {
                                  for (int m = l+1; m < primes.Count; m++)
                                  {
                                      string w = primes[m].ToString();
                                      if (IsPrime(int.Parse(s + w))&&
                                          IsPrime(int.Parse(t + w))&&
                                          IsPrime(int.Parse(u + w))&&
                                          IsPrime(int.Parse(v + w))&&
                                          IsPrime(int.Parse(w + s))&&
                                          IsPrime(int.Parse(w + t))&&
                                          IsPrime(int.Parse(w + u))&&
                                          IsPrime(int.Parse(w + v)))
                                      {
                                          sum = primes[i] +
                                                primes[j] +
                                                primes[k] +
                                                primes[l] +
                                                primes[m];
                                          //min = sum < min ? sum : min;
                                          Console.WriteLine(sum);
                                          Console.WriteLine(primes[i] + " " +
                                                            primes[j] + " " +
                                                            primes[k] + " " +
                                                            primes[l] + " " +
                                                            primes[m]);
                                          finished = true;
                                          break;
                                      }
                                  }
                                  if (finished) break;
                              }
                          }
                          if (finished) break;
                      }
                  }
                  if (finished) break;
              }
           }
          if (finished) break;
      }
      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 primes = new List<int> { 2, 3 };
      for (int i = 5; i <= n; i += 2)
          if (IsPrime(i))
              primes.Add(i);
      return primes;
  }
}
}

Triple-click for answer: 26033

PROJECT EULER #59

2009-04-19T16:39:00.004+02:00

Link to Project Euler problem 59

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using cipher1.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

Read in the string, split up the letters in a string array, generate every possible password and do the XOR (^) on the relevant chars, adding them to a List. Make a string of this and see if it contains " and " (with the spaces). Took a gamble on this and I'm sure there are better RegEx's to check for intelligent text, but as it's sunday today I'll write it off to divine inspiration (clue). Only one of the 17576 possible results seemed to contain " and ". The program prints it out (the password is interesting too ;-)).

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Text.RegularExpressions;

namespace project_euler
{
class Program
{
   static void Main()
   {
       //Problem 59
       //17576 possible combinations of letters
       DateTime start = DateTime.Now;
       StreamReader sr = new StreamReader(@"../../cipher1.txt");
       int sum = 0;
       List<List<char>> decodedValues = new List<List<char>>();
       string s = sr.ReadToEnd();
       string[] letters = s.Split(',');
       Regex test = new Regex(" and ");
       for (int i = 97; i < 123; i++)
           for (int j = 97; j < 123; j++)
               for (int k = 97; k < 123; k++)
               {
                   List<char> decodedString = new List<char>();
                   int n = 0;
                   while (n < letters.Length)
                   {
                       decodedString.Add((char) (int.Parse(letters[n]) ^ i));
                       if (n + 1 < letters.Length)
                           decodedString.Add((char) (int.Parse(letters[n + 1]) ^ j));
                       if (n + 2 < letters.Length)
                           decodedString.Add((char) (int.Parse(letters[n + 2]) ^ k));
                       n += 3;
                   }
                   StringBuilder sb = new StringBuilder();
                   foreach (char c in decodedString)
                       sb.Append(c);
                   string t = sb.ToString();
                   if (test.IsMatch(t))
                       decodedValues.Add(decodedString);
               }
       string decoded="";
       foreach (List<char> words in decodedValues)
       {
           foreach (char ch in words)
           {
               decoded += ch.ToString();
               sum += ch;
           }
           Console.WriteLine(decoded);
           Console.WriteLine(sum);
       }
       TimeSpan time = DateTime.Now - start;
       Console.WriteLine("This took {0}", time);
       Console.ReadKey();
   }
}
}

Triple-click for answer: 107359

PROJECT EULER #58

2009-04-18T21:02:00.002+02:00

Link to Project Euler #58

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

for a n x n anticlockwise spiral, the corners are given by:
top right: n^2 - 3n + 3,
top left: n^2 - 2n + 2,
bottom left: n^2 - n + 1,
bottom right: n^2.


using System;
namespace project_euler
{
class Program
{
 static void Main()
 {
     //Problem 58
     DateTime start = DateTime.Now;
     int i = 1,n;
     double primeCount = 0, numberCount = 1;
     do
     {
         n = 2*i + 1;
         if (IsPrime(n*n - 3*n + 3))
             primeCount++;
         if (IsPrime(n*n - 2*n + 2))
             primeCount++;
         if (IsPrime(n*n - n + 1))
             primeCount++;
         numberCount += 4;
         i++;
     } while (primeCount/numberCount > 0.1);
     Console.WriteLine(n);
     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;
 }
}
}

Triple-click for answer: 26241

PROJECT EULER #57

2009-04-18T20:13:00.006+02:00

Link to Project Euler problem 57

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

Sqrt(2) = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

using System;

namespace project_euler
{
class Program
{
    static void Main()
    {
        //Problem 57
        //(a+b)/b, where b = previous a+2*b and a = previous a + b.
        DateTime start = DateTime.Now;
        int count=0;
        BigInt a = new BigInt(3);
        BigInt b = new BigInt(2);
        for (int i = 1; i < 1000; i++)
        {
            if (a.ToString().Length > b.ToString().Length)
                count++;
            a = 2*b + a;
            b = a - b;
        }
        Console.WriteLine(count);
        TimeSpan time = DateTime.Now - start;
        Console.WriteLine("This took {0}", time);
        Console.ReadKey();
    }
}
}

PROJECT EULER #56

2009-04-18T15:16:00.003+02:00

Link to Project Euler problem 56

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, a^b, where a, b <100,>


using System;

namespace project_euler
{
 class Program
 {
     static void Main()
     {
         //Problem 56
         DateTime start = DateTime.Now;
         int max = 0,number=0,power=0;
         for (int i = 99; i >90; i--)
         {
             BigInt n = i;
             for (int k = 2; k <100; k++)
             {
                 n *= i;
                 string s = n.ToString();
                 int sum = 0;
                 foreach (char c in s)
                     sum += int.Parse(c.ToString());
                 if (sum > max)
                 {
                     max = sum;
                     number = i;
                     power = k;
                 }
             }
         }
         Console.WriteLine(max+" "+number+" to the "+power+" power");
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
 }
}

PROJECT EULER #55

2009-04-18T13:15:00.004+02:00

Link to Project Euler problem 55

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

I used BigInt again here.


using System;

namespace project_euler
{
class Program
{
   static void Main()
   {
       //Problem 55
       DateTime start = DateTime.Now;
       int lychrel=0;
       for (int i = 1; i < 10000; i++)
       {
           BigInt j = i;
           int count = 0;
           while(count<51)
           {
               j =ReverseAndAdd(j);
               if (IsPalindrome(j.ToString()))
                   break;
               count++;
               if (count == 50)
                   lychrel++;
           }
       }
       Console.WriteLine(lychrel);
       TimeSpan time = DateTime.Now - start;
       Console.WriteLine("This took {0}", time);
       Console.ReadKey();
   }
   public static BigInt ReverseAndAdd(BigInt n)
   {
       char[] c = n.ToString().ToCharArray();
       Array.Reverse(c);
       string s = new string(c);
       return n + s;
   }
   public static bool IsPalindrome(string s)
   {
       char[] q = s.ToCharArray();
       Array.Reverse(q);
       string r = new string(q);
       if (s.Equals(r))
           return true;
       return false;
   }
}
}

PROJECT EULER #54

2009-04-18T09:42:00.005+02:00

Link to Project Euler problem 54

In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:

High Card: Highest value card.
One Pair: Two cards of the same value.
Two Pairs: Two different pairs.
Three of a Kind: Three cards of the same value.
Straight: All cards are consecutive values.
Flush: All cards of the same suit.
Full House: Three of a kind and a pair.
Four of a Kind: Four cards of the same value.
Straight Flush: All cards are consecutive values of same suit.
Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

The cards are valued in the order:
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.

Consider the following five hands dealt to two players:

Hand	Player 1	Player 2	Winner
1	5H 5C 6S 7S KD Pair of Fives	2C 3S 8S 8D TD Pair of Eights	Player 2
2	5D 8C 9S JS AC Highest card Ace	2C 5C 7D 8S QH Highest card Queen	Player 1
3	2D 9C AS AH AC Three Aces	3D 6D 7D TD QD Flush with Diamonds	Player 2
4	4D 6S 9H QH QC Pair of Queens Highest card Nine	3D 6D 7H QD QS Pair of Queens Highest card Seven	Player 1
5	2H 2D 4C 4D 4S Full House With Three Fours	3C 3D 3S 9S 9D Full House with Three Threes	Player 1

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1's cards and the last five are Player 2's cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player's hand is in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?

I'd previously made a simple class library for constructing card games as an exercise in OOD. This creates a deck and shuffles etc but the only relevant class for this problem is the Card class and it's Enum:

Card.cs:

using System;
namespace CardLibrary
{
/// <summary>
/// A Card Object has a suit, a value (A - K) and a rank (1 - 52)
/// </summary>
public class Card : IComparable<Card>
{
 /// <summary>
 /// default constructor
 /// </summary>
 public Card()
 {
 }
 /// <summary>
 /// standard constructor. Also calculates the rank (1-52) 
 /// </summary>
 /// <param name="suit">(Suits)0 = Clubs, (Suits)1 = Diamonds
 /// (Suits)2 = Hearts, (Suits)3 = Spades</param>
 /// <param name="type">(CardType)0 = 2 etc.</param>
 public Card(Suits suit,CardType type)
 {
     Suit = suit;
     FaceValue = type;
     CardRank = ((int) suit*13) + (int) type;
 }

 public Suits Suit { get;  set; }
 public CardType FaceValue { get; set; }
 public int TrueValue
 {
     get { return ((int)FaceValue)+2; }
     private set { }
 }

 public int CardRank
 {
     get { return ((int)Suit * 13) + (int)FaceValue; }
     private set { }
 }

 #region IComparable Members

 public int CompareTo(Card other)
 {
     return FaceValue - other.FaceValue;
 }

 #endregion

}
}

CardTypes.cs


/// <summary>
/// The suits
/// </summary>
public enum Suits
{
Clubs=0,
Diamonds=1,
Hearts=2,
Spades=3
}
/// <summary>
/// The values
/// </summary>
public enum CardType
{
Two=0,
Three=1,
Four=2,
Five=3,
Six=4,
Seven=5,
Eight=6,
Nine=7,
Ten=8,
Jack=9,
Queen=10,
King=11,
Ace=12
}

Then comes program.cs:


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

namespace project_euler
{
 class Program
 {
     static void Main()
     {
         //Problem 54
         DateTime start = DateTime.Now;
         StreamReader sr = new StreamReader(@"../../poker.txt");
         List<string> allHands = new List<string>();
         int player1score = 0;
         while (!sr.EndOfStream)
         {
             allHands.Add(sr.ReadLine());
         }
         int i = 0;
         foreach (string s in allHands)
         {
             i++;
             string[] cards1 = s.Substring(0, 14).Split(' ');
             string[] cards2 = s.Substring(15, 14).Split(' ');
             Hand Player1 = GeneratePokerHand(cards1);
             Hand Player2 = GeneratePokerHand(cards2);
             double p1score = EvaluatePokerHand(Player1);
             double p2score = EvaluatePokerHand(Player2);
             Console.WriteLine(i+" "+p1score + "\t\t\t"+p2score);
             if (p1score > p2score)
                 player1score++;
         }
         Console.WriteLine(player1score);
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
     public static Hand GeneratePokerHand(string[] cards)
     {
         Hand hand = new Hand("player");
         foreach (string s in cards)
         {
             char[] c = s.ToCharArray();
             Card card = new Card();
             hand.Add(card);
             switch (c[0])
             {
                 case '2':
                     card.FaceValue = 0;
                     break;
                 case '3':
                     card.FaceValue = (CardType)1;
                     break;
                 case '4':
                     card.FaceValue = (CardType)2;
                     break;
                 case '5':
                     card.FaceValue = (CardType)3;
                     break;
                 case '6':
                     card.FaceValue = (CardType)4;
                     break;
                 case '7':
                     card.FaceValue = (CardType)5;
                     break;
                 case '8':
                     card.FaceValue = (CardType)6;
                     break;
                 case '9':
                     card.FaceValue = (CardType)7;
                     break;
                 case 'T':
                     card.FaceValue = (CardType)8;
                     break;
                 case 'J':
                     card.FaceValue = (CardType)9;
                     break;
                 case 'Q':
                     card.FaceValue = (CardType)10;
                     break;
                 case 'K':
                     card.FaceValue = (CardType)11;
                     break;
                 case 'A':
                     card.FaceValue = (CardType)12;
                     break;
             }
             switch (c[1])
             {
                 case 'C':
                     card.Suit = 0;
                     break;
                 case 'D':
                     card.Suit = (Suits)1;
                     break;
                 case 'H':
                     card.Suit = (Suits)2;
                     break;
                 case 'S':
                     card.Suit = (Suits)3;
                     break;
             }
         }
         hand.Sort();
         return hand;
     }
     public static double EvaluatePokerHand(Hand hand)
     {
         //TrueValue = (int)FaceValue + 2.
         //High card value of hand: 23457 (0,200718) to 9JQKA (0,493269) = (highest card * 14^4 + next highest card * 14^3...etc)/1000000.
         //Pair: 22345 (2,000617) to AAKQJ (14,002305) =  TrueValue of pair (2 = 2) + high card value of rest of hand.
         //Two Pairs: 22334(15,000002) to AAKKQ (169,00001) = 13*TrueValue of highest pair + TrueValue of second pair + high card value of last card.
         //Tres: 22234 (202) to AAAKQ (214) = 200 + TrueValue of tres.
         //Straight: 23456 (256) to AKQJ10 (264) =  250 + TrueValue of highest card.
         //Flush: 23457 (300,200718) to 9JQKA (300,493269) = 300 + high card value of hand.
         //House: 22233 (352) to AAAKK(364) = 350 + TrueValue of tres.
         //Four: 22223 (402) to AAAAK (414) = 400 + TrueValue of four.
         //Straight Flush: 23456 (456) to AKQJ10 (464) = 450 + trueValue of highest card.
         double points = 0;
         int flush = 1, straight = 1;
         //flushes and straights
         for (int i = 1; i < hand.Count; i++)
         {
             if (hand[0].Suit == hand[i].Suit)
                 flush++;
             if (hand[i].FaceValue == hand[0].FaceValue + i)
                 straight++;
         }
         if (straight == 5)
         {
             points = flush == 5
                          ? 450 + hand[4].TrueValue
                          : 250 + hand[4].TrueValue;
             return points;
         }
         if (flush == 5)
             return 300 + EvaluateCards(hand);

         int numberOfPairs = 0, numberOfTres = 0, cardValue = 0;
         //check for pairs/threes/fours
         for (int i = 0; i < hand.Count - 1; i++)
         {
             int sameValue = 1;
             for (int j = i + 1; j < hand.Count; j++)
             {
                 if (hand[i].FaceValue == hand[j].FaceValue)
                     sameValue++;
                 if (sameValue == 4)
                     return 400 + hand[j].TrueValue;
             }
             if (sameValue == 3)
             {
                 numberOfTres++;
                 numberOfPairs--;
                 cardValue = hand[i].TrueValue;
             }
             if (sameValue == 2)
                 numberOfPairs++;
         }
         //two pairs
         if (numberOfPairs == 2)
         {
             int pairNumber = 2;
             int i = hand.Count - 1;
             while (hand.Count > 1)
             {
                 if (hand[i - 1].FaceValue == hand[i].FaceValue)
                 {
                     if (pairNumber == 2)
                     {
                         points = 13 * (int)hand[i].FaceValue;
                         pairNumber--;
                     }
                     else
                         points += hand[i].TrueValue;
                     hand.Remove(hand[i]);
                     hand.Remove(hand[i - 1]);
                     i -= 2;
                 }
                 else
                     i--;
             }
             return points + EvaluateCards(hand);
         }
         //pair
         if (numberOfPairs == 1 && numberOfTres == 0)
         {
             int i = hand.Count - 1;
             while (hand.Count > 3)
             {
                 if (hand[i - 1].FaceValue == hand[i].FaceValue)
                 {
                     points += hand[i].TrueValue;
                     hand.Remove(hand[i]);
                     hand.Remove(hand[i - 1]);
                     return points + EvaluateCards(hand);
                 }
                     i--;
             }
         }
         //3 of a kind or house
         if (numberOfTres == 1)
         {
             if (numberOfPairs == 1)
                 return 350 + cardValue;
             return 200 + cardValue;
         }
         //high card
         return EvaluateCards(hand);
     }
     public static double EvaluateCards(List<Card> cards)
     {
         double points = 0;
         for (int i = cards.Count-1; i >= 0; i--)
             points += (int)cards[i].FaceValue * ((Math.Pow(14, i) / 1000000));
         return points;
     }
 }
}

Triple-click for answer: 376

PROJECT EULER #53

2009-04-17T14:45:00.007+02:00

Link to Project Euler problem 53

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ⁵C₃ = 10.

In general,

ⁿC_r =

n!
______
r!(n-r)!

,where r <= n, n! = n*(n-1)*...*3*2*1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ²³C₁₀ = 1144066.

How many, not necessarily distinct, values of ⁿC_r, for 1 <= n <= 100, are greater than one-million

My first effort, using the BigInt class, used 25 seconds so I found a much better way using Pascal's Triangle (of course):

effort #1:

using System;

namespace ProjectEuler
{
 class Program
 {
     static void Main()
     {
         //Problem 53
         DateTime start = DateTime.Now;
         int count = 0;
         for (int i = 22; i < 101; i++)
         {
             BigInt n = FactorialBigInt(i);
             for (int j = i; j > 0; j--)
             {
                 BigInt r = FactorialBigInt(j);
                 BigInt s = FactorialBigInt(i - j);
                 BigInt result = n / (r * s);
                 count += result > 1000000 ? 1 : 0;
             }
         }
         Console.WriteLine(count);
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
     public static BigInt FactorialBigInt(int n)
     {
         n = n == 0 ? 1 : n;
         BigInt factorial = 1;
         for (int i = 1; i <= n; i++)
         {
             factorial *= i;
         }
         return factorial;
     }
 }
}

effort #2:


using System;
using System.Collections.Generic;

namespace ProjectEuler
{
 class Program
 {
     static void Main()
     {
         //Problem 53
         DateTime start = DateTime.Now;
         int count = 0;
         List<int[]> pascT = new List<int[]>();
         for (int i = 0; i < 101; i++)
         {
             int[] line=new int[i+1];
             pascT.Add(line);
         }
         pascT[0][0] = 1;
         for (int i = 1; i < pascT.Count; i++)
             for (int j = 0; j <= i; j++)
                 if (j == 0  j == i)
                     pascT[i][j] = 1;
                 else if (pascT[i - 1][j] + pascT[i - 1][j - 1] >= 1000000)
                 {
                     pascT[i][j] = 1000000;
                     count++;
                 }
                 else
                     pascT[i][j] = pascT[i - 1][j] + pascT[i - 1][j - 1];
         Console.WriteLine(count);
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
 }
}

PROJECT EULER #52

2009-04-17T12:17:00.004+02:00

Link to Project Euler problem 52

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.


using System;
using System.Collections.Generic;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 52
           DateTime start = DateTime.Now;
           long i = 1, result = 0;
           bool test = true;
           while (test)
           {
               if (SameDigits(i,2*i)&&SameDigits(i,3*i)&&SameDigits(i,4*i)&&SameDigits(i,5*i)&&SameDigits(i,6*i))
               {
                   result = i;
                   test = false;
               }
               i++;
           }
           Console.WriteLine(result);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }

       public static bool SameDigits(long n,long m)
       {
           List<char> firstNumber = new List<char>();
           List<char> secondNumber = new List<char>();
           char[] c = n.ToString().ToCharArray();
           char[] d = m.ToString().ToCharArray();
           if (c.Length != d.Length)
               return false;
           foreach (var c1 in c)
               firstNumber.Add(c1);
           firstNumber.Sort();
           foreach (var d1 in d)
               secondNumber.Add(d1);
           secondNumber.Sort();
           for (int i = 0; i < firstNumber.Count; i++)
           {
               if (firstNumber[i] != secondNumber[i])
                   return false;
           }
           return true;
       }
   }
}

PROJECT EULER #51

2009-04-17T11:58:00.003+02:00

Link to Project Euler problem 51

By replacing the 1st digit of *57, it turns out that six of the possible values: 157, 257, 457, 557, 757, and 857, 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, 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.


using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 51
            string number = "";
            int count = 0;
            List<int> primes = GeneratePrimes(1000000);
            while (primes[0] < 100000)
                primes.Remove(primes[0]);
            DateTime start = DateTime.Now;
            foreach (int i in primes)
            {
                string s = i.ToString();
                for (int j = 0; j < s.Length; j++)
                {
                    char d = s[j];
                    count = 0;
                    for (int k = 0; k < 10; k++)
                    {
                        string t = s.Replace(d, char.Parse(k.ToString()));
                        if (IsPrime(int.Parse(t)) && int.Parse(t) > 100000)
                            count++;
                    }
                    if (count > 7)
                    {
                        number = s;
                        break;
                    }
                }
                if (count > 7)
                    break;
            }
            Console.WriteLine("the number {0} creates an 8 prime family", number);
            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 primes = new List<int> { 2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primes.Add(i);
            return primes;
        }
    }
}

Triple-click for answer: 121313

PROJECT EULER #50

2009-04-16T20:28:00.004+02:00

Link to Project Euler problem 50

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?


using System;
using System.Collections.Generic;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 50
           DateTime start = DateTime.Now;
           List<int> primes = GeneratePrimes(1000000);
           int max = 0, total = 0, initial = 0;
           for (int i = 0; i < 5; i++)
           {
               int sum = 0, number = 0;
               for (int j = i; j < primes.Count; j++)
               {
                   sum += primes[j];
                   if (sum > 1000000) break;
                   number++;
                   if (primes.Contains(sum))
                       if (number > total)
                       {
                           total = number;
                           max = sum;
                           initial = primes[i];                                                     
                       }
               }
           }
           Console.WriteLine("{0} steps from {1} give {2}", total, initial, max);
           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 primes = new List<int> { 2, 3 };
           for (int i = 5; i <= n; i += 2)
           {
               if (IsPrime(i))
                   primes.Add(i);
           }
           return primes;
       }
   }
}

PROJECT EULER #49

2009-04-16T20:22:00.004+02:00

Link to Projrct Euler poblem 49

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?


using System;
using System.Collections.Generic;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 49
           DateTime start = DateTime.Now;
           List<int> primes = GeneratePrimes(10000);
           while (primes[0] < 1000)
               primes.Remove(primes[0]);
           for (int i = 0; i < primes.Count; i++)
           {
               char[] c = primes[i].ToString().ToCharArray();
               Array.Sort(c);
               string s = new string(c);
               for (int j = i + 1; j < primes.Count; j++)
               {
                   char[] d = primes[j].ToString().ToCharArray();
                   Array.Sort(d);
                   string t = new string(d);
                   if (s == t)
                       if (primes.Contains(primes[i] + 2 * (primes[j] - primes[i])))
                       {
                           int third = primes[i] + 2 * (primes[j] - primes[i]);
                           char[] e = third.ToString().ToCharArray();
                           Array.Sort(e);
                           string u = new string(e);
                           if (u == t && u != "1478")
                           {
                               string result = primes[i].ToString() + primes[j] + third;
                               Console.WriteLine(result);
                           }
                       }
               }
           }
           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 primes = new List<int> { 2, 3 };
           for (int i = 5; i <= n; i += 2)
           {
               if (IsPrime(i))
                   primes.Add(i);
           }
           return primes;
       }
   }
}

PROJECT EULER #48

2009-04-16T18:50:00.005+02:00

Link to Project Euler problem 48

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.
Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

Keep doing the math and only keep the last 10 digits after every multiplication.


using System;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 48
           DateTime start = DateTime.Now;
           long answer = 0;
           for (int i = 1; i < 1001; i++)
           {
               long temp = i;
               for (int j = 1; j < i; j++)
               {
                   temp *= i;
                   temp %= 10000000000;
               }
               answer += temp;
               answer %= 10000000000;
           }
           Console.WriteLine(answer % 10000000000);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #47

2009-04-16T18:31:00.006+02:00

Link to Project Euler problem 47

The first two consecutive numbers to have two distinct prime factors are:
14 = 2 x 7
15 = 3 x 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.
Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

Took me some time to work this one out. The hard work is done by the method distinctPrimeFactors which divides the number by the smallest prime factor, then checks to see if it can divide it again by this number. It increments only if the prime divisor is a new number.

using System;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 47
           DateTime start = DateTime.Now;
           int startNumber = 644;
           while (true)
           {
               if (distinctPrimeFactors(startNumber)==4&&
                   distinctPrimeFactors(startNumber+1)==4&&
                   distinctPrimeFactors(startNumber+2)==4&&
                   distinctPrimeFactors(startNumber+3)==4)
               {
                   break;
               }
               startNumber++;
           }
           Console.WriteLine(startNumber);

           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
       public static int distinctPrimeFactors(int number)
       {
           int numFactors = 0;
           int prime = 2;
           bool newPrime = true;
           while (!IsPrime(number))
               if (number%prime == 0)
               {
                   number /= prime;
                   if (newPrime)
                       numFactors++;
                   newPrime = false;
               }
               else
               {
                   do
                       prime++; while (!IsPrime(prime));
                   newPrime = true;
               }
           numFactors++;
           return numFactors;
       }
       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;
       }
   }
}

PROJECT EULER #46

2009-04-13T14:41:00.004+02:00

Link to Project Euler problem 46

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 + 2x1²
15 = 7 + 2x2²
21 = 3 + 2x3²
25 = 7 + 2x3²
27 = 19 + 2x2²
33 = 31 + 2x1²

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?


using System;

namespace project_euler
{
class Program
{
    static void Main()
    {
        //Problem 46
        DateTime start = DateTime.Now;
        bool test=false;
        for (int i = 3; i < 1000000; i++)
        {
            if (!IsPrime(i) && i % 2 != 0)
            {
                for (int j = 1; j <= i - 2; j += 2)
                {
                    if (IsPrime(j))
                    {
                        test = false;
                        double k = i - j;
                        if (k % 2 == 0)
                        {
                            k = k / 2;
                            if (Math.Sqrt(k) == Math.Floor(Math.Sqrt(k)))
                            {
                                test = true;
                                break;
                            }
                        }
                    }
                }
                if (!test)
                {
                    Console.WriteLine(i);
                    break;
                }
            }
        }
        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;
    }
}
}

Triple-click for answer: 5777

PROJECT EULER #45

2009-04-13T12:51:00.006+02:00

Link to Project Euler problem 45

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle	T_n=n(n+1)/2	1, 3, 6, 10, 15, ...
Pentagonal	P_n=n(3n-1)/2	1, 5, 12, 22, 35, ...
Hexagonal	H_n=n(2n-1)	1, 6, 15, 28, 45, ...

It can be verified that T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755.

Find the next triangle number that is also pentagonal and hexagonal.


using System;

namespace ProjectEuler
{
class Program
{
 static void Main()
 {
     //Problem 45
     DateTime start = DateTime.Now;
     for (double i = 1; i < 1000000; i++)
     {
         double triangle = i/2*(i + 1);
         for (double j = 1; j <= i; j++)
         {
             double pentagonal = j/2*(3*j - 1);
             if (triangle == pentagonal)
             {
                 for (double k = 1; k <= j; k++)
                 {
                     double hexagonal = k*(2*k - 1);
                     if ( triangle==hexagonal&&triangle>40755)
                     {
                         Console.WriteLine(triangle +" "+ pentagonal +" "+ hexagonal);
                         TimeSpan time = DateTime.Now - start;
                         Console.WriteLine("This took {0}", time);
                         Console.ReadKey();
                     }
                 }
             }
         }
     }
 }
}
}

PROJECT EULER #44

2009-04-13T12:44:00.006+02:00

Link to Project Euler problem 44

Pentagonal numbers are generated by the formula, P_n=n(3n-1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. However, their difference, 70 - 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference is pentagonal and D = |P_k - P_j| is minimised; what is the value of D?


using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
 static void Main()
 {
     //Problem 44
     DateTime start = DateTime.Now;
     int diff;
     double n;
     List<int> pent = new List<int>(10000);
     for (int i = 0; i < 10000; i++)
     {
         //add pentagonals to list
         pent.Add((i+1)*(3*(i+1) - 1)/2);
         for (int j = 0; j < i; j++)
         {
             diff = pent[i] - pent[j];
             //check if diff is pentagonal
             n = (Math.Sqrt(24*diff + 1) + 1)/6;
             //if n is an integer
             if (n == Math.Floor(n))
             {
                 n = (Math.Sqrt(24*(diff + pent[i]) + 1) + 1)/6;
                 if (n == Math.Floor(n))
                     Console.WriteLine(pent[j]);
             }
         }
     }
     TimeSpan time = DateTime.Now - start;
     Console.WriteLine("This took {0}", time);
     Console.ReadKey();
 }
}
}

PROJECT EULER #43

2009-04-13T09:49:00.008+02:00

Link to Project Euler problem 43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

d₂d₃d₄=406 is divisible by 2
d₃d₄d₅=063 is divisible by 3
d₄d₅d₆=635 is divisible by 5
d₅d₆d₇=357 is divisible by 7
d₆d₇d₈=572 is divisible by 11
d₇d₈d₉=728 is divisible by 13
d₈d₉d₁₀=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

The clue here was to find d₈d₉d₁₀ first as there are only 58 multiples of 17 under 1000, then to remove these digits from the List. The next digit is added and we check if d₇d₈d₉ is divisible by 13. If so, remove this digit from the list. The next digit is added etc.

As we step back up the for-loops we put the digits back into the list. When there are only two digits left, both will produce d₂d₃d₄ divisible by 2. Numbers with a leading zero (d₁ = 0) are excluded.


using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
static void Main()
{
    //Problem 43
    DateTime start = DateTime.Now;
    long sum = 0;
    //find numbers divisible by 17
    for (int i = 17; i < 1000; i += 17)
    {
        List<string> test = new List<string> { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
        //Add leading zero if < 100
        string ia = i < 100 ? "0" + i : i.ToString();

        //Check uniqueness
        if (ia[0] != ia[1] && ia[0] != ia[2] && ia[1] != ia[2])
        {
            //remove from list
            for (int j = 0; j < 3; j++)
                test.Remove(ia[j].ToString());//7 left
            for (int j = 0; j < test.Count; j++)
            {
                string js = test[j];
                if (int.Parse(js + ia[0] + ia[1]) % 13 == 0)
                {
                    test.Remove(js);//6 left
                    for (int k = 0; k < test.Count; k++)
                    {
                        string ks = test[k];
                        if (int.Parse(ks + js + ia[0]) % 11 == 0)
                        {
                            test.Remove(ks);//5 left
                            for (int l = 0; l < test.Count; l++)
                            {
                                string ls = test[l];
                                if (int.Parse(ls + ks + js) % 7 == 0)
                                {
                                    test.Remove(ls);//4 left
                                    for (int m = 0; m < test.Count; m++)
                                    {
                                        string ms = test[m];
                                        if (int.Parse(ms + ls + ks) % 5 == 0)
                                        {
                                            test.Remove(ms);//3 left
                                            for (int n = 0; n < test.Count; n++)
                                            {
                                                string ns = test[n];
                                                if (int.Parse(ns + ms + ls) % 3 == 0)
                                                {
                                                    test.Remove(ns);//2 left
                                                        if (int.Parse(ms) % 2 ==0)
                                                        {
                                                            sum += long.Parse(test[1] + test[0] + ns + ms + ls + ks + js + ia);
                                                            if (test[0]!="0")
                                                            {
                                                                sum += long.Parse(test[0] + test[1] + ns + ms + ls + ks + js + ia);
                                                            }
                                                        }
                                                    test.Add(ns);
                                                    test.Sort();
                                                }
                                            }
                                            test.Add(ms);
                                            test.Sort();
                                        }
                                    }
                                    test.Add(ls);
                                    test.Sort();
                                }
                            }
                            test.Add(ks);
                            test.Sort();
                        }
                    }
                    test.Add(js);
                    test.Sort();
                }
            }
        }
    }
    Console.WriteLine(sum);
    TimeSpan time = DateTime.Now - start;
    Console.WriteLine("This took {0}", time);
    Console.ReadKey();
}
}
}

PROJECT EULER #42

2009-04-12T21:12:00.005+02:00

Link to Project Euler problem 42

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?


using System;
using System.IO;

namespace ProjectEuler
{
class Program
{
   static void Main()
   {
       //Problem 42
       DateTime start = DateTime.Now;
       StreamReader sr = new StreamReader(@"../../words.txt");
       string s = sr.ReadToEnd().ToUpper();
       string[] sa = s.Split(',');
       int tWords = 0;
       foreach (string s1 in sa)
       {
           int sum = 0;
           string s2 = s1.Substring(1, s1.Length - 2);
           s2.ToCharArray();
           foreach (char c in s2)
           {
               sum += c - 64;
           }
           for (double j = 0; j < 25; j++)
           {
               tWords += j/2*(j + 1) == sum ? 1 : 0;
           }
       }
       Console.WriteLine(tWords);
       TimeSpan time = DateTime.Now-start;
       Console.WriteLine("This took {0}", time);
       Console.ReadKey();
   }
}
}

PROJECT EULER #41

2009-04-12T21:03:00.006+02:00

Link to Project Euler problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

I can rule out 9 and 8 digit pandigitals because the sum of the digits is divisible by 9 which means they are not prime


using System;

namespace project_euler
{
class Program
{
   static void Main()
   {
       //Problem 41
       DateTime start = DateTime.Now;
       string test = "1234567";
       int max = 0;
       for (int i = 3; i < 7654321; i += 2)
       {
           string s = i.ToString();
           if (!s.Contains("0")||!s.EndsWith("5"))
           {
               char[] c = s.ToCharArray();
               Array.Sort(c);
               string t = new string(c);
               if (t == test.Substring(0, t.Length))
                   if (IsPrime(int.Parse(s)))
                       max = int.Parse(s) > max
                                 ? int.Parse(s)
                                 : max;
           }
       }
       Console.WriteLine(max);
       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;
   }
}
}

PROJECT EULER #40

2009-04-12T17:47:00.006+02:00

Link to Project Euler problem 40

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12^th digit of the fractional part is 1.

If d_n represents the n^th digit of the fractional part, find the value of the following expression.

d₁ x d₁₀ x d₁₀₀ x d₁₀₀₀ x d₁₀₀₀₀ x d₁₀₀₀₀₀ x d_1000000

using System;
using System.Text;

namespace project_euler
{
class Program
{
  static void Main()
  {
      //Problem 40
      DateTime start = DateTime.Now;
      StringBuilder sb = new StringBuilder();
      for (int i = 1; i < 200000; i++)
              sb.Append(i.ToString());
      string s = sb.ToString();
      long sum = int.Parse(s[0].ToString())*int.Parse(s[9].ToString())*int.Parse(s[99].ToString())*int.Parse(s[999].ToString())*int.Parse(s[9999].ToString())*int.Parse(s[99999].ToString())*int.Parse(s[999999].ToString());
      Console.WriteLine(sum);
      TimeSpan time = DateTime.Now - start;
      Console.WriteLine("This took {0}", time);
      Console.ReadKey();
  }
}
}

PROJECT EULER #39

2009-04-12T17:38:00.004+02:00

Link to Project Euler problem 39

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p <= 1000, is the number of solutions maximised?


using System;
using System.Collections.Generic;

namespace project_euler
{
  class Program
  {
      static void Main()
      {
          //Problem 39
          DateTime start = DateTime.Now;
          int max = 0,number=0;
          Dictionary<int,int> score=new Dictionary<int, int>();
          for (int i = 1000; i > 0; i--)
              for (int j = i - 1; j > 0; j--)
                  for (int k = j; k > 0; k--)
                      if ((k*k + j*j) == (i*i))
                          if (i + j + k <= 1000)
                              if (score.ContainsKey(i + j + k))
                                  score[i + j + k] += 1;
                              else
                                  score.Add(i + j + k, 1);
          foreach (KeyValuePair<int, int> pair in score)
              if (pair.Value > max)
              {
                  max = pair.Value;
                  number = pair.Key;
              }
          Console.WriteLine(number);
          TimeSpan time = DateTime.Now - start;
          Console.WriteLine("This took {0}", time);
          Console.ReadKey();
      }
  }
}

PROJECT EULER #38

2009-04-12T17:32:00.004+02:00

Link to Project Euler problem 38

Take the number 192 and multiply it by each of 1, 2, and 3:

192 x 1 = 192
192 x 2 = 384
192 x 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?


using System;
using System.Text;

namespace project_euler
{
class Program
{
    static void Main()
    {
        //Problem 37
        DateTime start = DateTime.Now;
        string test = "123456789";
        long max = 0;
        for (int i = 1; i < 10000; i++)
        {
            StringBuilder sb = new StringBuilder();
            for (int j = 1; j < 10; j++)
            {
                sb.Append(i*j);
                if (sb.Length == 9)
                {
                    string result = sb.ToString();
                    char[] c = result.ToCharArray();
                    Array.Sort(c);
                    string s = new string(c);
                    if (s == test)
                        max = int.Parse(result) > max
                                  ? int.Parse(result)
                                  : max;
                }
            }
        }
        Console.WriteLine(max);
        TimeSpan time = DateTime.Now - start;
        Console.WriteLine("This took {0}", time);
        Console.ReadKey();
    }
}
}

PROJECT EULER #37

2009-04-12T16:56:00.003+02:00

Link to Project Euler problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

using System;

namespace project_euler
{
class Program
{
    static void Main()
    {
        //Problem 37
        DateTime start = DateTime.Now;
        int sum = 0;
        for (int i = 9; i < 1000000; i+=2)
        {
            string s = i.ToString();
            if (!s.Contains("0") || !s.Contains("4") || !s.Contains("6") || !s.Contains("8"))
            {
                bool test = true;
                for (int j = 0; j < s.Length; j++)
                    if (!IsPrime(int.Parse(s.Substring(j, s.Length - j))) || !IsPrime(int.Parse(s.Substring(0, j + 1))))
                        test = false;
                if (test)
                    sum += i;
            }
        }
        Console.WriteLine(sum);
        TimeSpan time = DateTime.Now - start;
        Console.WriteLine("This took {0}", time);
        Console.ReadKey();
    }
    //test if prime
    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;
    }
}
}

PROJECT EULER #36

2009-04-12T16:15:00.002+02:00

Link to Project Euler problem 36

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

using System;
using System.Text;

namespace ProjectEuler
{
 class Program
 {
     static void Main()
     {
         //Problem 36
         DateTime start = DateTime.Now;
         int sum = 0;
         for (int i = 1; i < 1000000; i++)
         {
             if(IsPalindrome(i.ToString()))
             {
                 sum += IsPalindrome(ToBinary(i))
                            ? i
                            : 0;
             }
         }
         Console.WriteLine(sum);
         TimeSpan time = DateTime.Now-start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
     public static string ToBinary(int n)
     {
         var number = new StringBuilder();
         int rem;
         while(n!=0)
         {
             n=Math.DivRem(n, 2, out rem);
             switch (rem)
             {
                 case 0:
                     number.Append(0);
                     break;
                 case 1:
                     number.Append(1);
                     break;
                 default:
                     break;
             }
         }
         var c = number.ToString().ToCharArray();
         Array.Reverse(c);
         string s = new string(c);
         while (s.StartsWith("0"))
         {
             s.Remove(0, 1);
         }
         return s;
     }
     public static bool IsPalindrome (string s)
     {
         char[] q = s.ToCharArray();
         Array.Reverse(q);
         string r = new string(q);
         if (s.Equals(r))
             return true;
         return false;
     }
 }
}

PROJECT EULER #35

2009-04-12T16:09:00.004+02:00

Link to Project Euler problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

using System;

namespace project_euler
{
class Program
{
   static void Main()
   {
       //Problem 35
       DateTime start = DateTime.Now;
       int result = 0;
       for (int i = 0; i < 1000000; i++)
           if (IsCircularPrime(i))
               result ++;
       Console.WriteLine( result );
       TimeSpan time = DateTime.Now - start;
       Console.WriteLine("This took {0}", time);
       Console.ReadKey();
   }
   //check if number is circular prime
   public static bool IsCircularPrime( int number )
   {
       if (!IsPrime(number))
           return false;
       string s = number.ToString();
       //if the numbers 2,4,6,8,0 or 5 are in there it can't be a circular prime.
       foreach (char ch in s)
           if (number != 2)
               if(number!=5)
                   if (int.Parse(ch.ToString())%2 == 0 || ch == '5')
                       return false;
       string[] c = CircularCombinations( s );
       for( int i=0; i<c.Length; i++ )
       {
           int n = int.Parse( c[i] );
           if (!IsPrime(n))
               return false;
       }
       return true;
   }
   //Make the combinations
   public static string[] CircularCombinations(string number)
   {
       string[] c = new string[number.Length];
       c[0] = number;
       for (int i = 1; i < c.Length; i++)
           c[i] = number.Substring(i, c.Length - i) + number.Substring(0, i);
       return c;
   }
   //test if prime
   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;
   }
}
}

PROJECT EULER #34

2009-04-12T16:04:00.004+02:00

Link to Project Euler problem 34

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.


using System;

namespace project_euler
{
 class Program
 {
     static void Main()
     {
         //Problem 34
         DateTime start = DateTime.Now;
         long total = 0;
         for (int i = 3; i < 50000; i++)
         {
             long sum = 0;
             string s = i.ToString();
             for (int j = 0; j < s.Length; j++)
                 sum += Factorial(int.Parse(s[j].ToString()));
             if (sum == i)
                 total += sum;
         }
         Console.WriteLine(total);
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
     public static int Factorial(int n)
     {
         int number = n;
         if (n == 0) return 1;
         for (int i = 1; i < n; i++)
             number *= i;
         return number;
     }
 }
}

PROJECT EULER #33

2009-04-12T15:57:00.004+02:00

Link to Project Euler problem 33

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.


using System;

namespace project_euler
{
 class Program
 {
     static void Main()
     {
         //Problem 33
         DateTime start = DateTime.Now;
         double numerator = 1, denominator = 1;
         double temp1=0,temp2=0;
         for (double i = 10; i < 100; i++)
         {
             string a = i.ToString();
             for (double j = i+1; j < 100; j++)
             {
                 string b = j.ToString();
             
                 if (a[0] == b[1] && b[0] != '0'&& a[1]!='0')
                 {
                     temp1 = double.Parse(a[1].ToString())/double.Parse(b[0].ToString());
                     if (temp1==i/j)
                     {
                         numerator *= i;
                         denominator *= j;
                     }
                 }
                 else if (a[1] == b[0] && b[1] != '0' && a[0]!='0')
                 {
                     temp2 = double.Parse(a[0].ToString())/double.Parse(b[1].ToString());
                     if (temp2==i/j)
                     {
                         numerator *= i;
                         denominator *= j;
                     }
                 }
             }
         }
         bool test = true;
         while(test)
         {
             for (int i = 1; i <= numerator; i++)
                 if (numerator%i == 0 && denominator%i == 0)
                 {
                     numerator /= i;
                     denominator /= i;
                 }
             if (denominator%numerator != 0 || numerator == 1)
                 test = false;
         }
         Console.WriteLine(denominator);
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
 }
}

PROJECT EULER #32

2009-04-12T14:55:00.006+02:00

Link to Project Euler problem 32

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.


using System;
using System.Collections.Generic;

namespace project_euler
{
 class Program
 {
     static void Main()
     {
         //Problem 55
         DateTime start = DateTime.Now;
         List<int> products = new List<int>();
         string test = "123456789";
         int product = 0;
         for (int i = 1; i < 2000; i++)
         {
             string c = i.ToString();
             for (int j = 1; j < 50; j++)
             {
                 int temp = i * j;
                 string d = j.ToString();
                 string e = temp.ToString();
                 string s = c + d + e;
                 if (!s.Contains("0") && s.Length == 9)
                 {
                     char[] f = s.ToCharArray();
                     Array.Sort(f);
                     string compare = new string(f);
                     if (compare == test)
                     {
                         if (!products.Contains(temp))
                         {
                             products.Add(temp);
                             product += temp;
                         }
                     }
                 }
             }
         }
         Console.WriteLine(product);
         TimeSpan time = DateTime.Now - start;
         Console.WriteLine("This took {0}", time);
         Console.ReadKey();
     }
 }
}

PROJECT EULER #31

2009-04-12T14:48:00.004+02:00

Link to page

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?


using System;

namespace project_euler
{
    class Program
    {
        static void Main()
        {
            //Problem 31
            DateTime start = DateTime.Now;
            int count = 0;
            for (int a = 0; a <= 200; a += 200)
                for (int b = 0; a + b <= 200; b += 100)
                    for (int c = 0; a + b + c <= 200; c += 50)
                        for (int d = 0; a + b + c + d <= 200; d += 20)
                            for (int e = 0; a + b + c + d + e <= 200; e += 10)
                                for (int f = 0; a + b + c + d + e + f <= 200; f += 5)
                                    for (int g = 0; a + b + c + d + e + f + g <= 200; g += 2)
                                        for (int h = 0; a + b + c + d + e + f + g + h <= 200; h++)
                                            if (a + b + c + d + e + f + g + h == 200)
                                                count++;
            Console.WriteLine(count);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

Triple-click for answer: 73682

PROJECT EULER #30

2009-04-12T00:43:00.003+02:00

Link to page

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

using System;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 19
            DateTime start = DateTime.Now;
            int sum = 0;
            for (int i = 2; i < 1000000; i++)
            {
                int temp=0;
                foreach (var c in i.ToString().ToCharArray())
                {
                    temp += (int)Math.Pow(double.Parse(c.ToString()),5);
                }
                sum += temp == i ? temp : 0;
            }
            Console.WriteLine(sum);
            TimeSpan time = DateTime.Now-start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

Triple-click for answer: 443839

PROJECT EULER #29

2009-04-12T00:32:00.005+02:00

Link to Project Euler problem 29

Consider all integer combinations of a^b for 2 <= a <= 5 and 2 <= b <= 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 <= a <= 100 and 2 <= b <= 100?

using System;
using System.Collections.Generic;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 29
           DateTime start = DateTime.Now;
           var uniques = new List<string>();
           for (int a = 2; a <= 100; a++)
           {
               BigInt n = new BigInt(a);
               for (int b = 2; b <= 100; b++)
               {
                   n *= a;
                   string s = n.ToString();
                   if (!uniques.Contains(s))
                       uniques.Add(s);
               }
           }
           Console.WriteLine(uniques.Count);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #28

2009-04-12T00:03:00.006+02:00

Link to Project Euler problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

using System;

namespace ProjectEuler
{
  class Program
  {
      static void Main()
      {
          //Problem 28
          //for a n x n spiral, the corners are given by
          //tr: n^2, tl: n^2 - n + 1, bl: n^2 - 2n + 2, br: n^2 - 3n + 3.
          //so for each square we get 4n^2 - 6n + 6.
          DateTime start = DateTime.Now;
          int sum = 0;
          for (int i = 3; i < 1002; i+=2)
          {
              sum += 4*i*i - 6*i + 6;
          }
          //The middle number (1) is counted twice ;-)
          sum += 1;
          Console.WriteLine(sum);
          TimeSpan time = DateTime.Now-start;
          Console.WriteLine("This took {0}", time);
          Console.ReadKey();
      }
  }
}

PROJECT EULER #27

2009-04-11T23:55:00.007+02:00

Link to Project Euler problem 27

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.

Considering quadratics of the form:

n² + an + b, where a < 1000 and b < 1000

where n is the modulus/absolute value of n
e.g. 11 = 11 and -4 = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

using System;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 27
           DateTime start = DateTime.Now;
           int result = 0, max = 0;
           for (int i = -999; i < 1000; i++)
           {
               for (int j = -999; j < 1000; j++)
               {
                   int n = 0, number = 0;
                   while (true)
                   {
                       number = n*n + i*n + j;
                       if (!IsPrime(number))
                           break;
                       n++;
                   }
                   if (n>max)
                   {
                       max = n;
                       result = i*j;
                   }
               }
           }
           Console.WriteLine(result);
           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;
       }
   }
}

PROJECT EULER #26

2009-04-11T23:27:00.007+02:00

Link to Project Euler problem 26

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

¹/₂ = 0.5
¹/₃ = 0.(3)
¹/₄ = 0.25
¹/₅ = 0.2
¹/₆ = 0.1(6)
¹/₇ = 0.(142857)
¹/₈ = 0.125
¹/₉ = 0.(1)
¹/₁₀ = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ 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.

using System;
using System.Collections.Generic;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 26
           DateTime start = DateTime.Now;
           int maxLength = 0, result=0;
           for( int i=1; i<1000; i++ )
           {
           int length = LengthOfCycle(i);
               if( length > maxLength )
               {
                   result = i;
                   maxLength = length;
               }
           }
           Console.WriteLine(result);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
       public static int LengthOfCycle(int n)
       {
           var quotients = new List<int>(1000){0};
           var remainders = new List<int>(1000) {1};
           for (int i = 1; i < 1000; i++)
           {
               quotients.Add(remainders[i - 1]*10/n);
               remainders.Add(remainders[i - 1]*10 - quotients[i]*n);
               for (int j = 0; j < i; j++)
                   if (quotients[j] == quotients[i] && remainders[j] == remainders[i])
                       return i - j;
           }
           return -1;
       }
   }
}

PROJECT EULER #25

2009-04-11T15:45:00.006+02:00

Link to Project Euler problem 25

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n-1 + F_n-2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
   class Program
   {
       static void Main()
       {
           //Problem 25
           DateTime start = DateTime.Now;
           //again we use base 100000, saving the
           //chunks of the big number in a List<int>
           int digits = 0,carry=0,fibNo =2;
           var a = new List<int>{1};
           var b = new List<int>{1};
           var c = new List<int>();
           while (digits<1000)
           {
               fibNo+=1;
               //add the chunks carrying over to the next chunk
               for (int i = 0; i < b.Count; i++)
               {
                   int temp = a[i] + b[i] + carry;
                   int number;
                   carry =(Math.DivRem(temp, 100000, out number));
                   c.Add(number);
               }
               //if a has more chunks than b....
               if(a.Count>b.Count)
               {
                   c.Add(a[a.Count-1] + carry);
                   carry = 0;
               }
               //if the sum of a and b makes a new chunk...
               if (carry > 0)
               {
                   c.Add(carry);
               }
               //swap the numbers around
               b.Clear();
               foreach (int i in a)
               {
                   b.Add(i);
               }
               a.Clear();
               foreach (int i in c)
               {
                   a.Add(i);
               }
               c.Clear();
               //calculate how many digits, check the last chunk (MSB)
               //for less than 5 digits
               digits = a.Count*5;
               char[] ch = a[a.Count-1].ToString().ToCharArray();
               digits -= 5-ch.Length;
           }
           Console.WriteLine(fibNo + " has " + digits + " digits.");
           TimeSpan time = DateTime.Now-start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #24

2009-04-11T15:38:00.005+02:00

Link to Project Euler problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

using System;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 24
           //There are 10! permutations of 0123456789
           //There are 9! permutations of 123456789 = 362880
           //So for numbers beginning with 0 and 1 there are 725760 permutations
           //Thus we want the 1000000 - 725760 = 274240. permutation in the 2xxxxxxxxx group.
           //20xxxxxxxx has 8! permutations = 40320. 274240/40320 = 6.8....etc
           DateTime start = DateTime.Now;
           char[] result= new char[10];
           double permutation = 1000000;
           string s = "0123456789";
           for (int i = s.Length-1; i >= 0; i--)
           {
               double index = Math.Ceiling(permutation/FactorialSmallInt(s.Length-1))-1;
               result[i] = s[(int) index];
               s=s.Remove((int) index, 1);
               permutation -= FactorialSmallInt(i)*index;
           }
           Array.Reverse(result);
           Console.WriteLine(new string(result));
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
       public static double FactorialSmallInt(int n)
       {
           int factorial=1;
           for (int i = 1; i <= n; i++)
           {
               factorial *= i;
           }
           return factorial;
       }
   }
}

PROJECT EULER #23

2009-04-11T10:02:00.015+02:00

Link to Project Euler problem 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number whose proper divisors are less than the number is called deficient and a number whose proper divisors exceed the number is called abundant.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.


using System;
using System.Collections.Generic;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 23
           DateTime start = DateTime.Now;
           int result = 0;
           List<int> abundantNumbers = new List<int>();
           List<int> numbers = new List<int>();

           for (int i = 0; i < 28123; i++)
           {
               numbers.Add(i+1);
               result += numbers[i];
               if (IsAbundant(numbers[i]))
                   abundantNumbers.Add(numbers[i]);
           }
           for (int i = 0; i < abundantNumbers.Count; i++)
               for (int j = i; j < abundantNumbers.Count; j++)
               {
                   int temp = abundantNumbers[i] + abundantNumbers[j] - 1;
                   if (temp < numbers.Count)
                   {
                       result -= numbers[temp];
                       numbers[temp] = 0;
                   }
               }
           Console.WriteLine(result);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }

       public static bool IsAbundant(int n)
       {
           int sum = 0;
           for (int i = 1; i < n; i++)
               if (n%i == 0)
                   sum += i;
           if (sum > n)
               return true;
           return false;
       }
   }
}71

PROJECT EULER #22

2009-04-11T09:46:00.019+02:00

Link to Project Euler problem 22

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 x 53 = 49714.

What is the total of all the name scores in the file?

I live and work in Norway, where 'CAA' comes after 'CAZ' in the alphabet (because we have the letter 'Å' here which can be written 'AA' and which comes after 'Z'). This meant that I had to change the CurrentCulture settings to English to make this work.


using System;
using System.Collections.Generic;
using System.IO;
using System.Globalization;
using System.Threading;

namespace ProjectEuler
{
   class Program
   {
       static void Main()
       {
           //Problem 22
           DateTime start = DateTime.Now;
           Thread.CurrentThread.CurrentCulture = new CultureInfo("en-GB");
           StreamReader sr = new StreamReader(@"../../names.txt");
           string s = sr.ReadToEnd().Replace('"',' ').ToUpper();
           char[] c = {','};
           string[] split = s.Split(c);
           List<string> names = new List<string>();
           long sum=0;
           for (int i = 0; i < split.Length; i++)
           {
               names.Add(split[i].Trim());
           }
           names.Sort();
           for (int i = names.Count-1; i >=0 ; i--)
           {
               int value=0;
               char[] d = names[i].ToCharArray();
               foreach (char c1 in d)
               {
                   value += c1-64;
               }
               value *= (i+1);
               sum += value;
           }
           Console.WriteLine(sum);
           TimeSpan time = DateTime.Now-start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #21

2009-04-11T01:46:00.015+02:00

Link to Project Euler problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

using System;

namespace project_euler
{
class Program
{
    static void Main()
    {
        //Problem 21
        DateTime start = DateTime.Now;
        int sum=0;
        for (int i = 1; i < 10000; i++)
        {
            int n=IsAmicable(i);
            if (i!=n && i == IsAmicable(n))
                sum += i;
        }
        Console.WriteLine(sum);
        TimeSpan time = DateTime.Now - start;
        Console.WriteLine("This took {0}", time);
        Console.ReadKey();
    }
     public static int IsAmicable(int n)
    {
        int temp=0;
        for (int j = 1; j <= n/2; j++)
            if (n%j == 0)
                temp += j;
        return temp;
    }
}
}

PROJECT EULER #20

2009-04-10T22:03:00.013+02:00

Link to page

n! means n x (n - 1) x ... x 3 x 2 x 1

Find the sum of the digits in the number 100!

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
   class Program
   {
       static void Main(string[] args)
       {
           //Problem 20
           DateTime start = DateTime.Now;
           int carry = 0, sum =0;
           List<int> factorial100 = new List<int>() {100};
           List<int> temp = new List<int>();
           for(int i=99;i>1;i--)
           {
               //multiply each 'digit' (base million) with present multiplier (i)
               //and add carry from previous calculation
               //divide by 1000000 to get carry and new 'digit' (nice method DivRem gives both)
               foreach (int j in factorial100)
               {
                   int digitInBaseMillion;
                   int k = j*i + carry;
                   carry = Math.DivRem(k, 1000000,out digitInBaseMillion);
                   temp.Add(digitInBaseMillion);
               }
               if (temp.Count==factorial100.Count && carry != 0)
                   temp.Add(carry);
               carry = 0;
               factorial100.Clear();
               foreach(int j in temp)
                   factorial100.Add(j);
               temp.Clear();
           }
           foreach (int j in factorial100)
           {
               char[] c = j.ToString().ToCharArray();
               for (int i = 0; i < c.Length; i++)
                   sum += Convert.ToInt32(c[i].ToString());
           }
           TimeSpan time = DateTime.Now-start;
           Console.WriteLine("{0}\nThis took {1}", sum, time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #19

2009-04-10T20:24:00.013+02:00

Link to page

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?


using System;

namespace ProjectEuler
{
   class Program
   {
       static void Main()
       {
           //Problem 19
           DateTime start = DateTime.Now;
           DateTime date = new DateTime(1901,1,1);
           int sundays = 0;
           while (date.Year<2001)
           {
               if(date.Day==1 && date.DayOfWeek==DayOfWeek.Sunday)
               {
                   sundays++;
               }
               date=date.AddDays(1);
           }
           Console.WriteLine("There were {0} sundays in the 20th Century",sundays);
           TimeSpan time = DateTime.Now-start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #18

2009-04-10T20:20:00.009+02:00

Link to page

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 of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)


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

namespace ProjectEuler
{
   class Program
   {
       static void Main()
       {
           //Problem 18
           DateTime start = DateTime.Now;
           StreamReader sr = new StreamReader(@"../../littleTriangle.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 < 15; 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 < 15; 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();
       }
   }
}

¹/₂	=	0.5
¹/₃	=	0.(3)
¹/₄	=	0.25
¹/₅	=	0.2
¹/₆	=	0.1(6)
¹/₇	=	0.(142857)
¹/₈	=	0.125
¹/₉	=	0.(1)
¹/₁₀	=	0.1