当前位置:首页 » Project Euler » 详细页

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.

Solution

这题主要是考察 **[欧拉函数](https://en.wikipedia.org/wiki/Euler%27s_totient_function)**的性质,即 $ \phi (n)$是 $ \leq n$ 且与$n$ 互质的整数的数目。 我们用代码中的经典算法来遍历求解 $1\sim n$ 的满足欧拉函数条件的互质整数的个数。 然后对范围内的数遍历,先判断是否是 *Same Digit Number* ,然后比较比值,始终记录最小的比值$ n/φ(n)$,迭代结束后,输出最小比值满足条件数即可。

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)
            throw new RuntimeException("Not found");
        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;
            }
        }
        return totients;
    }


}
8319823
562ms