Monthly Archives: February 2010

Euler Problem 160

Posted on by
2

Euler Problem 160

Factorial trailing digits.

Solution:

Za mene jedan od težih koji sam uspio riješiti. Rješenje vrlo sporo oko 30 sati da se izračuna zadnjih 5 cifara. Nije nešto al…

static long last_digits_factorial(long N, int numDigits)
{
long a2 = 0, a5 = 0, a;
long ans = 1;
long lastDigits = (long)Math.Pow(10, numDigits);
for (long i = 1; i <= N; i++)
{
long j = i;
//divide i by 2 and 5
while (j % 2 == 0)
{
j /= 2;
a2++;
}
while (j % 5 == 0)
{
j /= 5;
a5++;
}
ans = (ans * (j % lastDigits)) % lastDigits;
}
a = a2 - a5;
for (long i = 1; i <= a; i++)
ans = (ans * 2) % lastDigits;
return ans;
}
static void Main(string[] args)
{
//Izračunavanje trajalo preko 30 sati.
Console.WriteLine(last_digits_factorial(1000000000000, 5));
Console.WriteLine("Press any key to continue...");
Console.Read();
}
Advertisement

Euler Problems 21-40

Posted on by
Reply

Euler Problem 21:

sum = 0; For[i = 100, i < 10000, i++, sum1 = DivisorSigma[1, i] - i; 
 If[i == (DivisorSigma[1, sum1] - sum1), sum += i];
 ]; sum - 8128 - 496

Euler Problem 22:

Treba paziti na sortiranje po engleskoj varijati je se dobijaju različita rješenja:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Collections;
using System.Globalization;

namespace EulerProblem22
{
    class Program
    {
        static void Main(string[] args)
        {
            long totalSum = 0;
            //English letters
            var letters = new List<char> { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
            string[] strWords = System.IO.File.ReadAllText("names.txt").Split(new char[] { ',', '\"' }, StringSplitOptions.RemoveEmptyEntries);

            //Lokalizirao sortiranje
            // Array.Sort<string>(strWords);
            //Sortiranje po English
            Array.Sort(strWords, new ENStringComparer());

            int pos = 1;
            foreach (var word in strWords)
            {
                totalSum += getNameValue(word) * pos;
                pos++;
            }
            Console.WriteLine(totalSum);
            Console.Read();
        }
        private static long getNameValue(string name)
        {
            long total = 0;

            for (int loop = 0; loop < name.Length; loop++)
                total +=((long)name[loop]) - 64;

            return total;
        }
        //Posebna klasa za sortiranje po English lokalizaciji
        private class ENStringComparer : IComparer<string>
        {
            private static CultureInfo usCulture = new CultureInfo("en-US");
            public int Compare(string str1, string str2)
            {
                return usCulture.CompareInfo.Compare(str1, str2);
            }
        }

    }
}

Euler Problem 23:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem23
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> lst = new List<int>();
            for (int i = 12; i < 28123; i++)
            {
                if (IsAbudant(i))
                    lst.Add(i);
            }
            int count = lst.Count;
            List<int> sumAbudList = new List<int>();
            for (int i = 0; i < count; i++)
            {
                for (int j = i; j < count; j++)
                {
                    int res = lst[i] + lst[j];
                    if (res <= 28123)
                        sumAbudList.Add(res);
                }
            }
            var sum = ParallelEnumerable.Range(1, 28123).Sum(x =>
            {
                if (sumAbudList.Contains(x) == false)
                    return x;
                else
                    return 0;
            }
            );

            Console.WriteLine(sum);

            Console.Read();
        }
        static bool IsAbudant(int n)
        {
            List<int> lst = new List<int>();

            for (int i = 1; i < n; i++)
            {
                if (n % i == 0)
                    lst.Add(i);
            }
            return lst.Sum() > n;

        }
    }
}

Euler Problem 24:

digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
permutations = Permutations[digits];
permutations[[1000000]]

Euler Problem 25:

static IEnumerable<BigInteger> FibonacciNiz()
{
    //Prva dva člana, odnosno prethodna dva člana
    BigInteger a = 1;
    BigInteger b = 1;
    //i-ti clan
    BigInteger c = 0;
    yield return a;
    yield return b;

    while (true)
    {
        yield return c = a + b;
        //nakon proracuna i-tog člana
        // prethodna dva člana postaju
        a = b;
        b = c;
    }
}
//Glavna funkcija
var termNumber = FibonacciNiz().TakeWhile(x => x.ToString().Length < 1000).Count();

Euler Problem 26:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace EulerProblem26
{
    class Program
    {
        static void Main(string[] args)
        {
            int max = 0;
            int maxd = 0;
            for (int d = 2; d < 1000; ++d)
            {
                var reminders = new HashSet<int>();
                int x = 1;
                int len = 0;
                while (x < d)
                    x *= 10;

                while (x != 0)
                {
                    if (reminders.Contains(x))
                        break;

                    reminders.Add(x);

                    while (x < d)
                    {
                        x *= 10;
                        len++;
                    }
                    x = x % d;
                }
                if (x != 0)
                {
                    if (len > max)
                    {
                        maxd = d;
                        max = len;
                    }
                }
            }
            Console.WriteLine(maxd);
            Console.Read();
        }
    }
}

Euler Problem 27:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace EulerProblem27
{
    class Prime
    {
        public int a;
        public int b;
        public int n;
    }
    class Program
    {
        static void Main(string[] args)
        {
            List<Prime> lst = new List<Prime>();
            Parallel.For(-1000, 1001, (i) =>
            {
                if (!IsPrime(Math.Abs(i)))
                    return;

                for (int j = -1000; j <= 1000; j++)
                {
                    if (!IsPrime(Math.Abs(j)))
                        continue;
                    int n = 0;
                    Prime pr = new Prime();

                    while (true)
                    {
                        if (IsPrime(Math.Abs(n * n + i * n + j)))
                        {
                            pr.a = i;
                            pr.b = j;
                            pr.n = n;
                            n++;
                        }
                        else
                        {

                            if (pr.n > 0)
                            {
                                lock (lst)
                                {
                                    lst.Add(pr);
                                }
                            }
                            break;
                        }
                    }
                }
            });
            var ss = lst.OrderByDescending(p => p.n).ToList();
            Console.WriteLine(ss[0].a * ss[0].b);
            Console.Read();
        }

        static long PrimeFormula(int n, int a, int b)
        {
            return n * n + a * n + b;

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

Euler Problem 28:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace EulerProblem28
{
class Program
{
    static void Main(string[] args)
    {
        int[][] A;
        int m = 1001;

        A = SpiralAlgorithm(m);
        long sum=0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if(i==j)
                    sum+=A[i][j];
                if (i + j == 1000)
                    sum += A[i][j];

            }
           
        }
        Console.WriteLine(sum-1);
        Console.WriteLine("");
        Console.WriteLine("Press any key to continue...");
        Console.ReadLine();
    }
//Spiral algorithm
static int [][] SpiralAlgorithm(int m)
{
    int i, j;
    int elNumber = 0;
    int mode = 0;
    int[][]  A = new int[m][];

    for (i = 0; i < m; i++)
    {
        A[i] = new int[m];
        for (j = 0; j < m; j++)
            A[i][j] = 0;
    }
    i = 0;
    j = 0;
    mode = 1;
    elNumber = (m * m);
    while (elNumber > 0)
    {
        //Na lijevo
        if (mode % 4 == 1)
        {
            int k;
            for (k = m - 1; k >= 0; k--)
            {
                if (A[i][k] > 0)
                    continue;

                A[i][k] = elNumber;
                elNumber--;
            }
            mode++;
        }
        //Prema dolje
        else if (mode % 4 == 2)
        {
            for (int k = 0; k < m; k++)
            {
                if (A[k][j] > 0)
                    continue;

                A[k][j] = elNumber;
                elNumber--;
            }
            mode++;
        }
        //Donji prema desno
        else if (mode % 4 == 3)
        {
            int l = m - 1 - i;

            for (int k = 0; k < m; k++)
            {
                if (A[l][k] > 0)
                    continue;

                A[l][k] = elNumber;
                elNumber--;
            }
            mode++;

        }
        //dolje gore
        else if (mode % 4 == 0)
        {
            int l = m - 1 - j;
            for (int k = m - 1; k >= 0; k--)
            {
                if (A[k][l] > 0)
                    continue;

                A[k][l] = elNumber;
                elNumber--;
            }
            mode++;
            j++;
            i++;
        }
    }
    return A;
}
}
}

Euler Problem 29:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem29
{
    class Program
    {
        static void Main(string[] args)
        {

            var count = (from p1 in Enumerable.Range(2, 99)
                         from p2 in Enumerable.Range(2, 99)
                         select Math.Pow(p1, p2)).Distinct().Count(); ;
            Console.WriteLine(count);
            Console.Read();
        }
    }
}

Euler Problem 30:

sum = 0; For[i = 2, i <= 999999, i++, 
 If[Sum[n^5, {n, IntegerDigits[i]}] == i, sum += i]]; sum

Euler Problem 31:

Length[FrobeniusSolve[{1, 2, 5, 10, 20, 50, 100, 200}, 200]]

Euler Problem 32:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//codeproject.com/KB/recipes/Combinatorics.aspx
using Facet.Combinatorics; 
namespace EulerProblem32
{
    class Program 
    {
        static void Main(string[] args)
        {

            List<int> products= new List<int>();
            Permutations<int> permutations= new 
                Permutations<int>(new List<int>(){1, 2, 3, 4, 5, 6, 7, 8, 9});
            foreach(IList<int> p in permutations)
            {
                int product1 = p[8];
                int product2 = p[7] * 10 + product1;
                int product3 = p[6] * 100 + product2;
                int product4 = p[5] * 1000 + product3;
                int a1 = p[0];
                int a2 = a1 * 10 + p[1];
                int a3 = a2 * 10 + p[2];
                int a4 = a3 * 10 + p[3];
                int b1 = p[4];
                int b2 = p[3] * 10 + b1;
         
                if (a3 * b2 == product4)
                    products.Add(product4);
         
                if (a4 * b1 == product4)
                    products.Add(product4);
            }

            Console.WriteLine(products.Distinct().Sum());
            Console.WriteLine("Press any key to contrinue...");
            Console.Read();
           
        }
    }
}

Euler Problem 33:

n = 1; d = 1; For[i = 1, i < 10, i++,
 max = i*100/(10 + 9*i);
 nom1 = 9 i^2; den1 = 9 i;
 For[j = i + 1, j <= i*100/(10 + 9*i), j++,
  nom1 += 9 i; den1--; If[Mod[nom1, den1] == 0, n *= i; d *= j;]
  ]
 ]; d/n

Euler Problem 34:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Probem34
{
    /*
     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.
     */
    class Program
    {
        static long Factorial(long n)
        {
            long retVal=1;
            for(int i=1; i<=n; i++)
                retVal*=i;
            return retVal;
        }
        static bool IsPrime(int n)
        {
            bool retVal=true;
            int sqrt=(int)Math.Sqrt(n);
            for(int i=2;i<sqrt; i++)
            {
                if(n%i==0)
                {
                    retVal=false;
                    break;
                }
            }
            return retVal;
        }
        static void Main(string[] args)
         {
              // Problem 34
                long sum = 0;
                for (int i = 3;i<1000000 ; i++)
                {
                    string digits = i.ToString();
                    long fact=0;
                    for (int j = 0; j < digits.Length; j++)
                    {
                        int digit=int.Parse(digits[j].ToString());
                        fact += Factorial(digit);
                    }
                    if (i == fact)
                        sum += fact;

                }
                Console.WriteLine(sum);
		Console.Read();
         }
    }
}

Euler Problem 35:

namespace EulerProblem35
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> primes = new List<int>();
            for (int i = 2; i < 1000000; i++)
                if (IsPrime(i))
                    primes.Add(i);
            long count=0;
            for (int i = 0; i < primes.Count; i++)
                if (IsCircPrime(primes[i]))
                    count++;
            Console.WriteLine(count);
            Console.Read();


        }
        static bool IsCircPrime(long n)
        {
            string s = n.ToString();

            for (int i = 1; i <= s.Length; i++)
            {
                s = s.Substring(1, s.Length - 1) + s.Substring(0, 1);

                if (!IsPrime(long.Parse(s)))
                 return false; 
            }

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

Euler Problem 36:

namespace EulerProblem36
{
    class Program
    {
        static void Main(string[] args)
        {
            int sum = 0;
            for (int i = 1; i < 1000000; i++)
            {
                string bin = Convert.ToString(i, 2);
                string dec = Convert.ToString(i);
                string revBin = ReverseString(bin);
                string revDec = ReverseString(dec);

                if (bin == revBin && dec == revDec)
                    sum += i;
            }
            Console.WriteLine(sum);
            Console.Read();
        }
        public static string ReverseString(string s)
        {
            string s2 = "";
            for (int i = s.Length - 1; i >= 0; i--)
                s2 += s[i];
            return s2;
        }
    }
}

Euler Problem 37:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem37
{
    class Program
    {
        static void Main(string[] args)
        {

            List<int> lst = new List<int>();
            int count = 0;
            for (int i = 10; count < 11; i++)
            {
                bool wantedNumber = true;
                if (IsPrime(i))
                {
                    string str = i.ToString();

                    for (int j = 0; j < str.Length - 1; j++)
                    {
                        string temp = str.Substring(j + 1, str.Length - j - 1);
                        if (temp[0].ToString() == "0")
                        {
                            wantedNumber = false;
                            break;
                        }
                        int n1 = int.Parse(temp);

                        if (n1 == 0 || n1 == 1)
                        {
                            wantedNumber = false;
                            break;
                        }
                        if (IsPrime(n1))
                        {
                            string temp1 = str.Substring(0, str.Length - j - 1);
                            if (temp1[0].ToString() == "0")
                            {
                                wantedNumber = false;
                                break;
                            }

                            int n2 = int.Parse(temp1);
                            if (n2 == 0 || n2 == 1)
                            {
                                wantedNumber = false;
                                break;
                            }
                            if (!IsPrime(n2))
                            {
                                wantedNumber = false;
                                break;
                            }

                        }
                        else
                        {
                            wantedNumber = false;
                            break;
                        }
                    }
                }
                else
                    wantedNumber = false;

                if (wantedNumber)
                {
                    lst.Add(i);
                    count++;
                }
            }

            Console.WriteLine(lst.Sum());

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

Euler Problem 38:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem38
{
    class Program
    {
        static void Main(string[] args)
        {
            int res = 0;
            for (int i = 9999; i > 1000; i--)
            {
                int numb1 = i * 1;
                int numb2 = i * 2;

                string str = numb1.ToString() + numb2.ToString();
                if (str.Contains("0"))
                    continue;
                if (str.Distinct().Count() == 9)
                {
                    res = i;
                    Console.WriteLine(i.ToString()+numb2.ToString());
                    break;
                }
            }
            Console.Read();
        }
    }
}

Euler Problem 39:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem39
{
    class Program
    {
        class pitagor
        {
            public int a;
            public int b;
            public int c;
            public int Perimeter;
        }
        static void Main(string[] args)
        {
            List<pitagor> lst = new List<pitagor>();
            for (int i = 1; i < 999; i++)
            {
                for (int j = i + 1; j < 999; j++)
                {

                    double cc = Math.Sqrt(i * i + j * j);
                    int c = (int)Math.Sqrt(i * i + j * j);
                    if (c == cc)
                    {
                        pitagor p = new pitagor();
                        p.a = i;
                        p.b = j;
                        p.c = c;
                        if (i + j + c > 1000)
                            continue;
                        p.Perimeter = i + j + c;
                        lst.Add(p);

                    }

                }
            }
            var pp = (from p in lst
                      group p by p.Perimeter into g
                      select new { Broj = g.Count(), per = g.Select(x => x.Perimeter) })
                      .OrderByDescending(x => x.Broj).FirstOrDefault().per.FirstOrDefault();
            Console.WriteLine(pp);
            Console.Read();
        }
    }
}

Euler Problem 40:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem40
{
    class Program
    {
        static void Main(string[] args)
        {
            string number = "";
            for (int i = 1; ; i++)
            {
                number += i.ToString();
                if (number.Length > 1000000)
                    break;
            }
            int d1 = int.Parse(number[0].ToString());
            int d10 = int.Parse(number[9].ToString());
            int d100 = int.Parse(number[99].ToString());
            int d1000 = int.Parse(number[999].ToString());
            int d10000 = int.Parse(number[9999].ToString());
            int d100000 = int.Parse(number[99999].ToString());
            int d1000000 = int.Parse(number[999999].ToString());

            Console.WriteLine(d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000);
            Console.Read();
        }
    }
}

Euler Problem 65

Posted on by
5

Euler Problem 65: Find the sum of digits in the numerator of the 100thconvergent of the continued fraction for e.

Sa  mathmematica došao do sljedećeg:

an = ContinuedFraction[E, 101][[100]];
For[i = 99, i &gt; 0, i--,
an = ContinuedFraction[E, 101][[i]] + 1/an
]; Total[IntegerDigits[Numerator[an]]]

Ili:

Total[IntegerDigits[
Numerator[FromContinuedFraction[ContinuedFraction[E, 100]]]]]