Project Euler #70: Time Efficiency Improvement

Question

The problem was to find which \$n\$ for which \$\varphi(n)\$ is a permutation of \$n\$ and \$n/\varphi(n)\$ is minimum,now as we all know that means (simple conclusions from mathematics):

• \$\varphi(n)\$ should be a permutation of n.
• \$n\$ should have least number of prime factors (2 cannot be one of the prime factor and \$n\$ cannot be prime)
• The prime factors should be as large as possible. Or in other words, the number should be as large as possible.

So the problem reduces to finding all numbers which are multiples of 2 primes (if no such number is found then find one with 3 prime factors and then 4 and so on, but such a situation never occurs)

I move back from 3137 as first factor and 33..331 the other (378 and 239118 th index in primes array). I multiply 'em, add to a list and then sort it and move in descending order to see which are permutations.

Even then it is taking a lot of time. Several minutes at-least.

double ratio = 100;
    List<Integer> l = new ArrayList<Integer>();
    int[] primes = Helper.getPrimes(10000050);
    for (int i = 378; i >= 1; i--) {
        for (int j = 239118; j > i; j--) {
            BigInteger num = BigInteger.valueOf(primes[i]).multiply(BigInteger.valueOf(primes[j]));
            if (num.compareTo(BigInteger.TEN.pow(7)) < 1) {
                int x = num.intValue();
                System.out.println(primes[i] + " * " + primes[j] + " = " + x);
                l.add(x);
            }
        }
    }
    Collections.sort(l);
    for (int i = l.size() - 1; i >= 0; i--) {
        int x = l.get(i);
        int y = EulerTotient(x);
        boolean isPerm = isPermutation(x, y);
        if (isPerm) {
            if (x < y * ratio) {
                ratio = (double) x / (double) y;
                System.out.println(x);
            }
        }
    }
    return 0;

isPermutation:

private static boolean isPermutation(int x, int b) {
    if (String.valueOf(x).length() != String.valueOf(b).length()) {
        return false;
    } else {
        int[] count = new int[10];
        do {
            ++count[x % 10];
            --count[b % 10];
            x /= 10;
            b /= 10;
        } while (x != 0);// also b!=0
        for (int i = 0; i < 10; i++) {
            if (count[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

EulerTotient: (take care to create a primes array)

public static int EulerTotient(int n) {
    int x = n;
    for (int i = 0; primes[i] <= n; i++) {
        if (n % primes[i] == 0) {
            x /= primes[i];
            x *= (primes[i] - 1);
        }
    }
    return x;
}

getPrimes:

isPrime = new boolean[maxValue + 1];
    Arrays.fill(isPrime, true);
    for (int i = 2; i * i <= maxValue; i++) {
        if (isPrime[i]) {
            for (int j = i; j * i <= maxValue; j++) {
                isPrime[i * j] = false;
            }
        }
    }
ArrayList<Integer> primes = new ArrayList<Integer>();
    for (int j = 2; j < lim; j++) {
        if (isPrime(j)) {
            primes.add(j);
        }
    }
    return listToIntArray(primes);

Answer 1

Several minutes? My stupid approach takes 1.3 second. It uses precomputed factoring of numbers below 1e7, which itself takes 0.3 s.

List<Integer> l = new ArrayList<Integer>();
int[] primes = Helper.getPrimes(10000050);
for (int i = 378; i >= 1; i--) {
    for (int j = 239118; j > i; j--) {
        BigInteger num = BigInteger.valueOf(primes[i]).multiply(BigInteger.valueOf(primes[j]));
        if (num.compareTo(BigInteger.TEN.pow(7)) < 1) {
            int x = num.intValue();
            System.out.println(primes[i] + " * " + primes[j] + " = " + x);
            l.add(x);
        }
    }
}

BigInteger??? That's the culprit. The solution is a few millions and confortable fits into an int. Using long would give me a good feeling. Using Guava's LongMath.checkedMultiply would give a guaranty I'm not computing non-sense. And so would my saturated arithmetic.

BigInteger.valueOf(primes[i])

• this should be done before the inner loop,
• or better stored in an array

BigInteger.TEN.pow(7)

• this is a contant and shouldn't be recomputing again and again

num.compareTo(BigInteger.TEN.pow(7)) < 1

So you want that num is at most 1e7 and are scared of it overflowing 9e18? How should this happen? Not at all as i * j <= 239118**2.

Another inefficiency: Whenever num gets too big, you know it'll be even bigger for a bigger prime. So if you were iterating upwards, you could use a break. For iterating downwards, you could use one division to determine the initial j.

int y = EulerTotient(x);

In order to compute the totient, you need the factorization. But you just have thrown the primes away! Use a map or alike.

Possibly you've lost several minutes already in this part and needn't read any further.

---

isPermutation

if (String.valueOf(x).length() != String.valueOf(b).length()) {
    return false;

This takes probably more time than the remaining computation, which is fine. I'd go for

    do {
        ++count[x % 10];
        --count[b % 10];
        x /= 10;
        b /= 10;
        if ((x != 0) != (b != 0)) return false; // different lengths
    } while (x != 0); // also b!=0

And I wouldn't call the arguments x and b as it's confusing (there are interchangeable so should be named similarly).

EulerTotient

Method names should start with a lowercase letter. Not even the best mathematicians deserve any exception.

This part is fine, except for that you need no such computation as you actually know the factorization when you create n. For this computation, you could add

n /= primes[i];

to the if-block and gain some speed due to an earlier loop exit.

getPrimes

No problem here. One can argue that in

        for (int j = i; j * i <= maxValue; j++) {
            isPrime[i * j] = false;
        }

the expression i*j gets computed twice or that you could keep the product in a variable and just add i on each iteration, but that's what JIT excels at. So it's fine as it is.