### Totient permutation题号：70 难度： 20 中英对照

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 < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

### Code

import java.util.Arrays;

public class p70 {

public static void main(String[] args) {
long start = System.nanoTime();
String result = run();
long end = System.nanoTime();
System.out.println(result);
System.out.println((end - start) / 1000000 + "ms");
}

private static final int LIMIT = pow(10, 7);

public static String run() {
int minNumer = 1;  // Initially infinity
int minDenom = 0;
int[] totients = listTotients(LIMIT - 1);
for (int n = 2; n < totients.length; n++) {
int tot = totients[n];
// 遍历该数是否有相同数字,且迭代寻找最小的符合条件数
if ((long) n * minDenom < (long) minNumer * tot && hasSameDigits(n, tot)) {
minNumer = n;
minDenom = tot;
}
}
if (minDenom == 0)
return Integer.toString(minNumer);
}

//判断x和y是否有相同数字
private static boolean hasSameDigits(int x, int y) {
char[] xdigits = Integer.toString(x).toCharArray();
char[] ydigits = Integer.toString(y).toCharArray();
Arrays.sort(xdigits);
Arrays.sort(ydigits);
return Arrays.equals(xdigits, ydigits);
}

// Returns x to the power of y, throwing an exception if the result overflows an int.
public static int pow(int x, int y) {
if (x < 0)
throw new IllegalArgumentException("Negative base not supported");
if (y < 0)
throw new IllegalArgumentException("Negative exponent");
int z = 1;
for (int i = 0; i < y; i++) {
if (Integer.MAX_VALUE / z < x)
throw new ArithmeticException("Overflow");
z *= x;
}
return z;
}

// Returns an array 'totients' where totients[i] == totient(i), for 0 <= i <= n.
// 返回从1~n,所有的数的互质数个数
public static int[] listTotients(int n) {
if (n < 0)
throw new IllegalArgumentException("Negative array size");
int[] totients = new int[n + 1];
for (int i = 0; i <= n; i++)
totients[i] = i;

for (int i = 2; i <= n; i++) {
if (totients[i] == i) {  // i是质数,因为相等时所有小于它的数都与它互质
for (int j = i; j <= n; j += i) //j是i 的倍数
totients[j] -= totients[j] / i;
}
}
}

}
8319823
562ms