bancaldo™

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.

Analisi:

Le fonti utili per la soluzione del problema:
wikipedia (Totient Function)

Dal link sono ricavabili le due formule fondamentali relative ai numeri primi:

n = p1 * p2
phi(n) = (p1 – 1) * (p2 – 1)

In sostanza:
Dobbiamo trovare il numero ‘n’ per il quale la funzione phi(n) riusulta essere una permutazione di ‘n’ stesso ed il rapporto tra n e phi(n) deve essere il più piccolo possibile.
Perchè un rapporto sia minimale, i denominatore deve essere il più grande possibile.
Verrebbe da pensare che prendendo il numero primo prossimo a 10^7 si abbia il risultato cercato.
Questo è errato in quando da un’altra analisi della funzione phi, è risaputo che se n è primo, quindi finisce per 1,3,7,9 allora:

phi(n) = n-1

ciò comporterebbe una variazione dell’ultima cifra del numero, quindi non si avrebbe come risultato una permutazione.
Se cercassimo invece due numeri primi che all’incirca fossero dell’ordine di grandezza della radice quadrata di 10^7, restringeremmo enormemente il campo di ricerca ed avremmo buone possibilità di ottenere il risultato.

√10^7 = ~3162

Useremo un campo di ricerca da 1000 a 5000 per stare tranquilli.

Python:

import time

st = time.time()

def is_prime(num):
    if num <= 1: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    else:
        d = 3
        r = int(num**0.5)
        while d <= r:
            if num % d == 0: return False
            d += 2
        return True


primes = [p for p in xrange(999, 5001, 2) if is_prime(p)]

minrate = 2
nmin = 1
tmax = 1

for p1 in primes:
    for p2 in primes:
        n = p1 * p2
        totien = (p1 - 1)*(p2 - 1)
        rate = float(n) / totien
        if n > 10**7: break
        if sorted(str(totien)) == sorted(str(p1*p2)) and rate < minrate:
            minrate = rate
            nmin = n
            tmax = totien
            
print nmin
print 'elapsed time: %ssec' %(time.time() - st)