Euler's totient function

phi

class Solution
{
	static void Main(String[] args)
	{
		var n = int.Parse(Console.ReadLine());
        
        var coprimes = CoprimeCount(n);
		var ratio = float.MaxValue;
		var r = 0;
		for (var i = 1; i < n; i++)
		{
			var phi = coprimes[i];
			if (IsPermutaion(i, phi))
			{
				var ratio2 = (float)i / phi;
				Console.WriteLine(string.Format("{0} {1} {2}", i, phi, ratio2));
				if (ratio > ratio2)
				{
					ratio = ratio2;
					r = i;					
				}
			}
		}

		Console.WriteLine(r);
    }
	
	private static int[] CoprimeCount(int n)
	{
		var stack = new Stack<CoprimePair>(n + 1);
		var phi = new int[n + 1];
		
		stack.Push(new CoprimePair(3, 1));
		stack.Push(new CoprimePair(2, 1));
			
		while (stack.Count > 0)
		{
			CoprimePair cp = stack.Pop();
			
			phi[cp.M]++;
			CoprimePair next;
			while (cp.GetNext(out next))
			{
				if (next.M <= n)
				{
					stack.Push(next);
				}
			}
		}
		return phi;
	}
	
	private static bool IsPermutaion(int a, int b)
	{
		var arr = new int[10];
		while(a != 0)
		{
			int rem;
			a = Math.DivRem(a, 10, out rem);
			arr[rem]++;
		}
		
		while(b != 0)
		{
			int rem;
			b = Math.DivRem(b, 10, out rem);
			arr[rem]--;
		}
		
		for (var i = 0; i < arr.Length; i++)
		{
			if (arr[i] != 0)
			{
				return false;
			}
		}
		
		return true;
	}
}

public struct CoprimePair
{	
	public int M;
	public int N;
	private int c;
	
	public CoprimePair(int m, int n)
	{
		M = m;
		N = n;
		c = 0;
	}
	
	public bool GetNext(out CoprimePair cp)
	{
		switch (c)
		{
			case 0:
				c++;
				cp = new CoprimePair(2 * M - N, M);
				return true;
			case 1:
				c++;
				cp = new CoprimePair(2 * M + N, M);
				return true;
			case 2:
				c++;
				cp =  new CoprimePair(M + 2 * N, N);
				return true;
			default:
				cp = default(CoprimePair);
				return false;
		}
	}
	
	override public string ToString()
	{
		return M + " " + N;
	}
}