Project Euler 70: Investigate values of n for which φ(n) is a permutation of n.

Project Euler 70: Investigate values of n for which φ(n) is a permutation of n.

Written by on 12 November 2011

Topics: Project Euler

For this problem I have taken a bit of a lazy approach with the coding and not emptied the search space, but just searched where we are most likely to find a solution. However, there are several tricks we can use when we try to find a solution. However, before babbling on, here is the problem we want to solve

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.

Looks familiar? Well, the phi function is the same function as we looked at previously.

Analysis

We are looking for a number n where  φ(n) is a permutation. However, more importantly we are trying to minimize the ratio n/φ(n). So lets start there since the function looks like

 

In order to minimize this we need to maximize the denominator.  As we can see every time we add a distinct prime factor the denominator gets smaller. So we are looking for a number with as few and as large distinct prime factors as possible.

The obvious best choice would be to find a prime number close to 10.000.000. However, that is not possible since a prime must end in 1,3,7,9 and φ(n) = n-1 would only change the last digit. So they cannot be permutations of each other.

The next best thing is two distinct prime factors where each is close to .  So if we just search number which are products of primes between 2000 and 5000 then there should be a good chance that we hit the one we are looking for.

Since we are looking for a number which is a product of two distinct primes we can ease the calculation of phi a tad, since we have

We can multiply phi with and with and get

Since we get

We can multiply and into the fractions and get

A method which is easier to deal with than the original formula.

Coding the solution

We have already made a permutation check for one of the earlier problems, so I wont cover that, but you can see the code in the source code. For an explanation of this part of the code check out Problem 49.

The code for finding the permutation with the smallest ratio is

long best = 1;
long phiBest = 1;
double bestRatio = double.PositiveInfinity;

int limit = 10000000;
int lowerbound = 2000;
int upperbound = 5000;
long[] primes = ESieve(lowerbound, upperbound);

for (int i = 0; i < primes.Length; i++) {
    for (int j = i+1; j < primes.Length; j++) {
        long n = primes[i] * primes[j];
        if (n > limit) break;

        long phi = (primes[i] - 1) * (primes[j] - 1);
        double ratio = ((double) n) / phi;

        if (isPerm(n, phi) && bestRatio > ratio) {
            best = n;
            phiBest = phi;
            bestRatio = ratio;
        }
    }
}

This yields

The permutation with the smallest ratio is 8319823
This gives us the fraction 1,00070905112481
Solution took 8 ms

which is indeed the answer to the problem.

Wrapping up

I haven’t been able to find guarantees that this is indeed the best answer. However I can ensure that it is better than the best possible answer with three distinct primes. Since the best solution would be a solution with three primes as close to the cube root to 10.000.000 as possible.

This would give us a ratio of 1.0140843 which is larger than the ratio we have just found.

It is also possible to show that it is not possible to find a number which has a prime factorization consisting of where  φ(n) is a permutation of n. However, I wont go into details with that.

As usual you can find the source code for the problem here. Comments, questions or other solutions are as always very welcome.

 

11 Comments For This Post I'd Love to Hear Yours!

  1. Marc says:

    You can simplify the reduction even further when knowing that:
    if p1 and p2 are coprime, then you have:
    phi(p1*p2) = phi(P1)*phi(P2)
    then use the rule phi(p) = p-1 when p is prime
    phi(p1*p2) = (p1 – 1)(p2 – 1)

  2. Kristian says:

    Hi Marc

    Thanks for that comment. I don’t mean to be rude or anything but isn’t this exactly what I have done? If not, would you care to elaborate some more so I understand the difference.

    /Kristian

  3. Marc says:

    Oh, sorry, yes, it is.
    I just meant to say that instead of expanding n*factor(1-1/p), you can just state the coprime multiplicative rule.
    I was mentioning it mostly so that anyone reading this would also be aware of the coprime rule as it has helped me quite a bit in the Euler’s totient problems.

    And I forgot to mention, thank you for your project Euler analyses, they’re both very elegant and well written.

  4. Kristian says:

    Right, that makes a lot of sense. I didn’t know of the coprime rule before writing this, so I probably make some steps which are considered trivial.

    And not least thanks for the compliment.

  5. bancaldo says:

    For me this is the best explanation found on the web.
    I use it for my python solution.
    Thank you.

  6. Martin Pahlplatz says:

    I found solution p1:3167, p2:3539, n:11208013, phi:11201308, ratio:1.0005985908074306
    What ‘s wrong with that?

    By the way: love your site!

  7. Martin Pahlplatz says:

    Sorry, n<100000000 forgotten 🙁

  8. anu says:

    p1=3989,p2=2477,n=9880753,phi=9874288,
    ratio=1.000654731.
    what’s problem with that solution?

  9. Seth says:

    How did you get it down to 8ms? I’ve made a roughly equal version and I’ve gotten it down to about 80ms. What does your seive and permuation check methods look like?

  10. Kristian says:

    Both functions are included in the source code which is linked in the bottom of the post. And I have probably developed those and explained them in earlier posts, but I don’t remember where exactly.

Trackbacks For This Post

  1. Project euler #70 « bancaldo™

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.