Euler Problem 70


Euler Problem 70:

Investigate values of n for which φ(n) is a permutation of n.

Solution:

Najoptimalnije rješenje se ogleda u tome da se iskoristi osobina Eulerove Totient funkcije (\varphi) i to: ako su p_{1} i p_{2} – prosti brojevi tada je \varphi(p_{1}\cdot p_{2})=(p_{1}-1)(p_{2}-1). Zbog toga je potrebno generirati proste brojeve manje od recimo 10 000, i provjeriti sve parove koji ne prelaze maximalnu vrijednost zadane zadatkom.

Source code implementacija:

        static void Main(string[] args)
        {
            List<int> primes = new List<int>();
            for (int i = 2; i< 10000; i++)
            {
                if (IsPrime(i))
                    primes.Add(i);
            }
            int soln = 0;
            double minratio = double.MaxValue;
            for (int i = 0; i < primes.Count; i++)
            {
                for (int j = 0; j < primes.Count; j++)
                {
                    int phi;
                    if (primes[i] == primes[j])
                        continue;
                    else
                        phi = (primes[i] - 1) * (primes[j] - 1);
                    int n = primes[i] * primes[j];
                    if (n > 10000000)
                        continue;
                    if (IsPermutation(n, phi))
                    {
                        if ((((double)n )/ ((double)phi) )< minratio)
                        {
                            minratio = (((double)n) / ((double)phi));
                            soln = n;
                        }
                    }
                }
            }
            //
            Console.WriteLine("Solution for PE 70: {0}",soln);
            Console.WriteLine("Press any key to continue...");
            Console.Read();
        }
        static bool IsPrime(long n)
        {
            for(int i=2; i*i<=n;i++)
                if(n%i==0)
                    return false;
               return true;
        }
        static bool IsPermutation(long n, long phi)
        {
            var str1 = phi.ToString();
            var str2 =  n.ToString();

            if (str1.Length != str2.Length)
                return false;

            var phi1 = str1.OrderBy(x => int.Parse(x.ToString())).ToArray();
            var n1 = str2.OrderBy(x => int.Parse(x.ToString())).ToArray();

            for (int i = 0; i < phi1.Length; i++)
                if (phi1[i] != n1[i])
                    return false;

                return true;
        }

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 03/03/2010, in C#, Project Euler and tagged . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s