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 () i to: ako su i – prosti brojevi tada je . 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;
        }