# 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;
}

Advertisement