Euler Problem 24

 http://projecteuler.net/index.php?section=problems&id=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?

_______________

Found this one kinda tricky in C#.. but in Python using the powerful itertools module it’s just 2 lines!

import itertools
print [d for d in itertools.permutations(range(10))][999999]

_________________

Euler Problem 23

Abundant numbers… those whose factors summed are greater than the number.

The challenge here is to find all abundant numbers up to 28123, then to find all those numbers which can’t be written as the sum of two abundant numbers.

So 12 is the first abundant number, whose factors add up to 16… making the smallest number with a sum of abundant numbers = 24.

http://projecteuler.net/index.php?section=problems&id=23

This works.. but fairly dumb code…. still .. enough to get me to the next challenge!

_______________

 

static void Main(string[] args)
      {
          List<int> abundantnumbers = new List<int>();

         int sum=0; //non abundant numbers factors

          for (int i=1;i<28123;i++)
          {

              if (i < sumofdivisors(divisors(i)))
              {
                  abundantnumbers.Add(i);
              }
         
          //can i be found using all abundant numbers found so far
              if (!issumofabundantnumners(abundantnumbers, i))
              {
                  sum += i;
              }
             
          }

      Console.WriteLine(sum);
      Console.ReadLine();

      }

      static List<int> divisors(int n)
      {
          List<int> div = new List<int>();
          for (int d = 1; d < n; d++)
          {
              if (n % d == 0) { div.Add(d); }
          }

          return div;

      }

      static int sumofdivisors(List<int> div)
      {
          int sum = 0;

          foreach (int i in div)
          {
              sum += i;
          }

          return sum;

      }

      static bool issumofabundantnumners(List<int> ab, int i)
      {
          foreach (int i1 in ab)
          {

              foreach (int i2 in ab)
              {

                  if (i == (i1 + i2))
                  {
                      return true;
                  }

              }
          }

          return false;

      }

Euler Problem 22

So you download a list of names.. and have to order them.. then calculate a value based on the characters (a-z) and position in the list… EASY! or is it????

Yes it is… C# has all the tools for this… build a list..then sort it.. pretty much job done… the only tip is to remember that the first place in the list (pos=0) is the 1st place in the list!!!

http://projecteuler.net/index.php?section=problems&id=22

______________

static void Main(string[] args)
        {
        List<string> names = new List<string>();
     
        //all names are in 1 line!
        System.IO.StreamReader sr = new System.IO.StreamReader("o:\\names.txt");
           
        foreach (string s in sr.ReadLine().Split(','))
        {
            names.Add(s);
        }

        names.Sort();

        long wordssum=0;

        for (int i = 0; i < names.Count; i++)
        {
            wordssum += wordvalue(names[i]) * (i+1);
        }

        Console.WriteLine(wordssum);
        Console.ReadLine();

        }

    static int wordvalue(string s)
      {
        // a=1 b=2 etc
          int val=0;
         
          foreach (char c in s.ToLower())
          {
              if (c > 96 && c < 123)
              {
                  val += Convert.ToInt16(c) - 96;
              }
          }

          return val;
    }

Euler Problem 21

http://projecteuler.net/index.php?section=problems&id=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.

___________________

static void Main(string[] args)
    {
        long sumofallpairs = 0;

        for (int n = 1; n < 10000; n++)
        {
            if (isamicablepair(n))
            {
                sumofallpairs +=n;
            }

        }

        Console.WriteLine(sumofallpairs);

 
    Console.ReadLine();

    }

    static bool isamicablepair (int n)
{
    int sum1 = 0;
    int sum2 = 0;

    foreach (int i in divisors(n))
    {
        sum1 += i;
    }

    foreach (int i in divisors(sum1))
    {
        sum2 += i;
    }

    if (n == sum2 && n != sum1)
    {
        return true;
    }
    else
    {
        return false;
    }

}

    static List<int> divisors(int n)
    {
        List<int> div = new List<int>();
        for (int d = 1; d < n; d++)
        {
            if (n % d == 0) { div.Add(d); }
        }

        return div;

    }

Euler Problem 20

Ahhh now this one uses something we built before.. around problem 16 I think… just a slight change needed… job done!! Nice to have an easy one for a change!

Problem = sum the numbers from the answer of 100!

http://projecteuler.net/index.php?section=problems&id=20

_________

 

static void Main(string[] args)
        {
           int[] c = new int[999];

            c[0] = 1; //starting condition

            for (int i = 1; i < 100; i++)   //go to the power of 1000
            {
                //do mult in place
                for (int n = 0; n < 999; n++)
                {
                    c[n] *= i;
                }

                //sort out carries across to right
                for (int n = 0; n < 999; n++)
                {
                    while (c[n]>9)
                    {
                    if (c[n] >= 10)
                    {
                        c[n + 1] += 1;
                        c[n] -= 10;
                    }
                    }
                }

            }

            //now add up all the columns
            long sum = 0;

            for (int n = 0; n < 999; n++)
            {
                sum += c[n];
            }

 

            Console.WriteLine(sum);
        Console.ReadLine();

        }

Euler Problem 19

How many Sundays on the first of the month in the 20th Century from 1 Jan 1901 to 31 Dec 2000?

http://projecteuler.net/index.php?section=problems&id=19

Luckily C# can do this really easily!!

 

static void Main(string[] args)
        {

            int counter=0;
            DateTime d = new DateTime(1901,1,1);
           
            while (d.Year<2001)
            {
                if (d.DayOfWeek == DayOfWeek.Sunday && d.Day == 1)
                {
                    counter++;
                }

               d= d.AddDays(1);
            }

 

        Console.WriteLine(counter);
        Console.ReadLine();

        }

Euler Problem 18

http://projecteuler.net/index.php?section=problems&id=18

OK so a triangle.. of costs.. and you need to find the most expensive way across it… so the best way is to work backwards from all possible endings and calculate the most expensive way to get there.

A simple example

      1

  2    5  

7   3   5 

Ending positions are 7,3,5,6…

To get to 7 we can have arrived from 2 or 5.. the most expensive route would be 5+7=13

To get to 3 we can have either come from 2 or 5.. the most expensive route would be 3+5 = 8..

etc  to get a new triangle of max routes which looks like this..

  11

9  10

7  3  5

 

giving us the answer of 11… for the most expensive path thru the triangle….. so repeat this formula for any size of triangle.. using code as follows:

______________________

 

       static void Main(string[] args)
        {

            int[,] a= new int[15,15];
          

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

//start at the last row - work back to top of triangle from all end possibilities
for (int row = 13; row > -1; row--)
{
    //now work thru all the columns
    for (int col = 0; col < 14; col++)
    {
        //find in the row below the max val possible from option1 or option 2 (l or r linked cell)
        if (a[col,row+1] > a[col + 1,row+1])
        {
            a[col,row] = a[col,row+1] + a[col,row];
        }
        else
        {
            a[col,row] = a[col+1, row+1] + a[col,row];
        }

    }

}

        Console.WriteLine(a[0,0]);
        Console.ReadLine();

        }