PROJECT EULER #70

Link to Project Euler problem 70

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < src="http://projecteuler.net/index.php?section=problems&id=70" style="display: none;" alt="^(">⁷, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

Have to admit that I tried to brute-force this one and fell asleep on the couch. On awakening the answer lay there but the program would have happily run for some days (?) before completing. Armed with advice from the forum I learned that there are many ways to skin a totient...

Euler (from projecteuler.net) wrote:

Given n=p1e1p2e2...p1e1, φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pk).

Now for n/φ(n) to be minimised, φ(n) must be as close to n as possible; that is, we want to maximise φ(n).

When evaluating φ(n), we note that each time we multiply by (1-1/pi), it gets smaller, so we need to minimise the number of distinct prime factors in n.

If n were prime, it would end in 1,3,7, or 9, and subtracting 1 only changes the last digit (to 0,2,6, or 8), so it could not be a permutation.

Hence n=p1*p2 and we only need to search through a list of known prime pairs.

In addition, φ(p1*p2)=p1*p2*(1-1/p1)(1-1/p2)=(p1-1)(p2-1), so we can compute φ(n) more efficiently.

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
  private static List<int> primes = GenerateRangeOfPrimes(1000,5000);

  static void Main()
  {
      //Problem 70
      DateTime start = DateTime.Now;
      decimal min = 100;
      int number = 1;

      for (int j = primes.Count - 1; j >= 0; j--)
          for (int k = j - 1; k >= 1; k--)
          {
              int i = primes[j]*primes[k];
              if (i < 10000000)
              {
                  int totient = (primes[j] - 1)*(primes[k] - 1);
                  if (IsPermutation(i, totient))
                      if ((decimal) i/totient < min)
                      {
                          min = (decimal) i/totient;
                          number = i;
                          Console.WriteLine(number + ": " + min + " p1: " + primes[k] + " p2: " + primes[j]);
                      }
              }
          }
      TimeSpan time = DateTime.Now - start;
      Console.WriteLine("This took {0}", time);
      Console.ReadKey();
  }

  private static bool IsPermutation(int m,int n)
  {
      char[] c = m.ToString().ToCharArray();
      char[] d = n.ToString().ToCharArray();
      Array.Sort(c);
      Array.Sort(d);
      string s = new string(c);
      string t = new string(d);
      if (s == t) return true;
      return false;
  }

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

  private static List<int> GenerateRangeOfPrimes(int m,int n)
  {
      var p = new List<int> { 2, 3 };
      for (int i = 5; i <= n; i += 2)
          if (IsPrime(i))
              p.Add(i);
      while (p[0] < m)
          p.Remove(p[0]);
      return p;
  }
}
}