Euler Problem 37

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

______

so the first thing I did wrong was to consider 1 to be a prime.. once I’d sorted that out I got this list.. which is 11 primes…  so those must be what they’re after!

23
37
53
73
313
317
373
797
3137
3797
739397

_________________

 

static void Main(string[] args)
       {
           long sum = 0;
           int found = 0;
           long i = 11;
           while (found<11)
           {
              int c=0;
              i++;
              int l = i.ToString().Length;

              for (int x = 0; x < l; x++)
              {

                  long t1 = Convert.ToInt64(i.ToString().Substring(x, l - x));
                  long t2 = Convert.ToInt64(i.ToString().Substring(0, x+1));

                  if (isprime(t1) && isprime(t2) && t1 != 1 && t2 != 1 )
                  {
                      c++;
                  }
                  else
                  {
                      c = 0;
                  }

              }
              
               if (c == i.ToString().Length)
                   {
                       sum += i;
                       found++;
                       Console.WriteLine(i);
                   }

           }

           Console.WriteLine("Answer>>>"+sum);
           Console.ReadLine();

       }

static bool isprime(long n)
       {
           if (n == 2 || n == 3 || n == 5) { return true; }

          if (n%2==0) {return false;}
          if (n%3 == 0) { return false;}
          if (n%5 == 0) { return false;}

          for (int t = 7; t < Math.Sqrt(n); t++)
          {
              if (n % t== 0)
              {
                  return false;
              }
          }

          return true;

       }

Euler Problem 36

Just count from 1 to n, find equivalent binary, check both base 10 and base 2 values are palindromic.. job done!

Interestingly in .NET to turn binary into base 10 then just do this!

Convert.ToInt32("1001",2)    

1001 ==>> 9

________________

 

static void Main(string[] args)
       {
           int counter = 0;
           int sum = 0;

           for (int i = 1; i < 1000000; i++)
           {
               string binary = IntToString(i, new char[] { '0', '1' });

               if (palindromic(i.ToString()) && palindromic(binary))
               {
                   sum += i;
               }

           }

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

       }

       static bool palindromic(string s)
       {
           string rev="";
           for (int i = s.Length;i>0;i--)
           {
               rev += s.Substring(i-1,1);
           }

           if (s == rev)
           {
               return true;
           }

           return false;

       }

Euler Problem 35

Fairly straight forward this one…

________________

static void Main(string[] args)
        {
            int counter = 0;

            for (long i = 2; i < 1000000; i++)
            {
                string s = i.ToString();
                int l= s.ToString().Length;

                int c = 0;

                for (int x = 0; x <l; x++)
                {
                    string sr = s.Substring(x, l - x) + s.Substring(0,x);
                    if (!isprime(Convert.ToInt32(sr)))
                    {
                        break;
                    }
                    else
                    {
                        c++;
                    }

                }

                if (c==l) {
                    counter++;}

            }

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

        }

 

static bool isprime(int n)
       {
           if (n == 2 || n == 3 || n == 5) { return true; }

          if (n%2==0) {return false;}
          if (n%3 == 0) { return false;}
          if (n%5 == 0) { return false;}

          for (int t = 7; t < Math.Sqrt(n); t++)
          {
              if (n % t== 0)
              {
                  return false;
              }
          }

          return true;

       }

Euler Problem 34

This was an easy one.. at last!

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

______________________

static void Main(string[] args)
       {

           long bigsum = 0;

           for (long i = 3; i < 1000000; i++)
           {
               string s = i.ToString();
               long sum = 0;
               foreach (char c in s)  //split up to chars
               {
                  sum+= factorial(c-48);   //convert from ASCII to numerical value of char (c)
                  if (sum > i) { break; }
               }

               if (sum == i) {bigsum += sum;
               }

           }

           Console.WriteLine(bigsum);
           Console.ReadLine();

       }

static long factorial(long n)
        {
            long tot = 1;
            for (long i = 1; i < n+1; i++)
            {
                tot *= i;

            }
            return tot;
        }

Euler Problem 33

I found this puzzle quite tricky to understand… perhaps the question could be written more clearly…

Essentially you just need to find all the fractions which have no more than 2 digits in top/bottom (ie <99/99), which are equal to <1, and which have the same number in the top and bottom which when that number is removed from the fraction the result is the same as the full fraction… anything using factors of 10 is ignored.

So 10/20 = 1/2 (remove 0 from top and base) – but this simple example is ignored.. they only want more complex ones like…

16/64 = 0.25 … remove those common 6s and you’d have 1/4 which is also 0.25 so this what they’re after…! In fact you now only need find the other 3!

I did it by using MOD10 to get the last number, and (Convert.ToInt16(t/10)) to get the first… then just compare these to find when numbers match… could be done using string conversions otherwise..

_______________________

static void Main(string[] args)
{
double sum = 1;

for (int b = 1; b < 100; b++) //t/b has to be <1
{
for (int t = 1; t < b; t++) //only check up to 99/98
{
double f= Convert.ToDouble(t) / Convert.ToSingle(b);
double i= Convert.ToDouble(Convert.ToInt16(t/10));
double j= Convert.ToDouble(Convert.ToInt16(b/10));
double x = 0;

//skip easy ones that divide by 10 top and bottom
if ( (t%10!=0 && b%10!=0))
{
//(i == j || i == b % 10 || t % 10 == j || t % 10 == b % 10) )

if (i == j) { x = (t % 10) / (b % 10); }
if (i == b%10) { x = (t % 10) / j; }
if (t%10 == j) { x = i / (b % 10); }
if (t%10 == b%10) { x = i / j; }

if (x == f)
{
sum *= f;
Console.WriteLine(t + "/" + b);
}

}
}
}

Console.WriteLine("Answer>>" + 1/sum);
Console.ReadLine();

}

Euler Problem 32

Been on hols… so mini break from this.. but had the chance to do one more…

Here we need to find the sum of all products which use numbers 1-9 ONCE in being formed from 2 multipliers and the product itself…

e.g.  4 x 1738 = 6952    => uses 1,2,3,4,5,6,7,8,9

Note we should only include each product (eg 6952) once in the final sum… so I used a list for this.

Other tips – the product and multipliers can be formed into a string.. whose length must be 9.. anything else would mean a double or missing value.

Also we only need test up to 9876 (we could do 9999 but it’d be pointless as there are repeated values there already!)

_________________________

static void Main(string[] args)
       {

           BigInteger sum = 0;
           List<long> found = new List<long>();

           for (long a = 1; a < 9876; a++)
           {
               for (long b = 1; b < 9876; b++)
               {
                   long c = a * b;
                   if (contains1to9once(a, b, c))
                   {
                       if (!found.Contains(c))
                       {
                           sum += c;
                           found.Add(c);
                       }
                   }
               }
           }
           Console.WriteLine(sum);
           Console.ReadLine();

       }

       static bool contains1to9once(long a, long b, long c)
       {
           string s = a.ToString() + b.ToString() + c.ToString();
       
           //has to be 9 chars long only with one of each
           if(s.Length==9 &&
           s.Split('1').Length==2 &&
           s.Split('2').Length==2 &&
           s.Split('3').Length==2 &&
           s.Split('4').Length==2 &&
           s.Split('5').Length==2 &&
           s.Split('6').Length==2 &&
           s.Split('7').Length==2 &&
           s.Split('8').Length==2 &&
           s.Split('9').Length==2)
           {

               return true;
           }
           return false;

       }

Euler Problem 31

How many ways using UK coins (1,2,5,10,20,50,100,200) can you make 200p?

I just used loops for each coin type.. not very fast but does the trick..

______

static void Main(string[] args)
        {
            int c = 1; //2 dollar coin = one way

            for (int p1 = 0; p1 < 201; p1++)
            {
                for (int p2 = 0; p2 < 201; p2 += 2)
                {
                    for (int p5 = 0; p5 < 201; p5 += 5)
                    {
                        for (int p10 = 0; p10 < 201; p10 += 10)
                        {
                            for (int p20 = 0; p20 < 201; p20 += 20)
                            {
                                for (int p50 = 0; p50 < 201; p50 += 50)
                                {
                                    for (int p100 = 0; p100 < 201; p100 += 100)
                                    {
                                        if (p1 + +p2 + p5 + p10 + p20 + p50 + p100 == 200)
                                        {
                                            c++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            Console.WriteLine(c);

             Console.ReadLine();

        }