Project Euler Problem #70

May 5, 2010

Read the details of the problem here

Summary

Investigate values of n for which φ(n) is a permutation of n.

Solution

I’d done Problem 69 sometime ago but that was a fairly obvious non-programming solution. I’d taken a look at this problem and it looked a lot more complicated and without anything concrete to leverage from the previous problem, so I skipped over it. However I was hunting around for a problem that I might have a good stab at to make my century and gave this one some more consideration.

I knew from the previous problem that the ratio of n/φ(n) was maximised when n was the product of many small prime factors (there’s the giveaway for that one!) hence with few relatively prime numbers. It seemed reasonable that it would be a minimum when n was a product of a small number of large, prime factors – so best case would be only two. A little bit of experimentation (using a GCD calculation) showed this to be the case with a good degree of confidence (though it was far from a formal proof). I also found that if n = p1 * p2 then φ(n) = (p1-1) * (p2-1). This would obviously be a big help as long as the assumptions held true as it was very evident that a GCD approach was hopeless.

For a few first multiples of primes and the exemplar:

p1 p2 p1*p2 (n) (p1-1)*(p2-1) Relatively Prime φ(n) n/φ(n)
2 3 6 2 1,5 2 3
3 5 15 8 1,2,4,7,8,11,13,14 8 1.875
5 7 35 24 1,2,3,4,6,8,9,11,12,
13,16,17,18,19,22,23,
24,26,27,29,31,32,33,
34
24 1.45833…
7 11 77 60 1,2,3,…,74,75,76 60 1.28333…
11 7919 87109 79180 loads of them… 79180 1.10013…

Given that the exemplar was of this two-prime form, I suspected that might be on the right track as Euler is quite good on giving clues like this.

So the next step was to determine which primes might be eligible for calculation. As mentioned earlier, I wanted them both to be as large as possible and so it makes sense to concentrate around the square root of the limit given (107). I decided to give it 30% either way from the square root and expand outwards if necessary. The square root of 107 is 3162.28 so that meant creating primes running from 2213-4111 (in which there happens to be only 236 primes). I did this using the normal sieve method before constructing the list from it.

It was then just a case of running through the 27,730 combinations of primes, some of which would exceed the limit and could be quickly discarded, and doing the necessary calculations.

def LIMIT = 10000000
def UPRIME=(int)Math.ceil((Math.sqrt(LIMIT) * 1.3))
def LPRIME=(int)Math.floor((Math.sqrt(LIMIT) * 0.7))

def isPrime = new boolean[UPRIME]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

for (i in 2..<Math.sqrt(UPRIME)) {
  if (!isPrime[i]) continue
  def j = i + i
  while (j < UPRIME) {
    isPrime[j] = false
    j += i
  }
}

def primes = []
for (i in LPRIME..<UPRIME) { if (isPrime[i]) primes << i }

def ( answer, min ) = [ 0, Double.MAX_VALUE ]

for (i in 0..<primes.size()-1) {
  for (j in i+1..<primes.size()) {
    def n = primes[i] * primes[j]
    if (n > LIMIT) break
    def phi = (primes[i]-1) * (primes[j]-1)
    if (n.toString().toList().sort().join()
        == phi.toString().toList().sort().join()) {
      def ratio = n / phi
      if ( ratio < min ) ( answer, min ) = [ n, ratio ]
    }
  }
}

This runs in a quite satisfactory, and quite surprising quick, 0.26 seconds. Though I must admit that I was somewhat lucky with the bounds of the primes. A Java version, using an int array rather than list for the primes, but otherwise the same logic runs in 13 ms – so around 20x faster.

Special Note: This was my 100th correctly answered question, so I’m now in the Hall of Fame albeit as a n00b Novice, being ranked at 115/2292 in England.

Conclusion

Groovy was useful in creating the check for a permutation but I steered mostly clear of listops & syntactic sugar as I was concerned, perhaps needlessly as it turned out, about performance.

Advertisements

One Response to “Project Euler Problem #70”


  1. […] quite straightforwardly, and a little thought showed that this was very similar to Problem #69 and Problem #70. The numerator in the resilience function is going to be the count of terms that are relatively […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: