Euler Problem 70

So I could have kept calculating the totient function directly and left it to run for years. Instead, I googled totient and discovered an interesting little mathematical quirk that would enable me to significantly reduce my testing set.
If a number is a product of two prime numbers …

  • n = p1 * p2

then the totient of that number is …

  • phi (n) = (p1-1) * (p2-1)

The square root of 10E7 is about 3100 plus change. So I calculated all the prime numbers 30% above and below that number. Then tested each of those numbers whereby the products were < 10E7. Smallest n/phi(n) wins. Routine runs in about 5 minutes. By the way, I wrote this routine to leverage (and re-learn Pythonian OOP).

from math import sqrt
class Algorithms:
    def permutate(self, sequence):
        if not sequence:
            return [sequence]
            set = []
            for k in range(len(sequence)):
                part = sequence[:k] + sequence[k+1:]
                for m in self.permutate(part):
                    set.append(sequence[k:k+1] + m)
            return set 
    def primeGen (self, lowerLimit, upperLimit):
        isPrime = [False, True]
        i = 2
        while i < upperLimit:
            i += 1
        p = 2
        while p * p < upperLimit:
            if isPrime[p] == True:
                m = p * p
                while m < upperLimit:
                    if m % p == 0:
                        isPrime[m] = False
                    m += p
            p += 1
        P = []
        count = 0
        for p in isPrime:
            if p and count >= lowerLimit :
            count += 1
        return P
class Problem70:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        primes = self.Euler.primeGen(.7 * sqrt(self.limit), 1.3 * sqrt(self.limit))
        print "Primes:"+str(primes)+"\n"
        i = 0
        minNDivPhi = 10
        minN = 0
        for p1 in primes:
          print "Testing:"+str(p1)
          i += 1
          for p2 in primes[i:]:
            n = p1 * p2
            if n > self.limit:
            phi = (p1-1) * (p2-1)
            nDivPhi = n / float(phi)
            if nDivPhi < minNDivPhi:
                if str(int(n)) in self.Euler.permutate (str(int(phi))):
                    minNDivPhi = nDivPhi
                    minN = n
                    print "n:"+str(n)+" phi:"+str(phi)+" nDivPhi:"+str(nDivPhi)
        return "Value of n where nDivPhi is minimized:"+str(minN)
if __name__ == '__main__':
    P = Problem70(10000000)
    print P.Solution()

Leave a Reply

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

You are commenting using your 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 )

Connecting to %s