Editing 3295 - Perm Euler

== Cerinţa ==
Indicatorul lui Euler, '''φ(n)''' – câteodată numit funcția phi, e folosit pentru a determina câte numere pozitive mai mici decât '''n''' care sunt relativ prime cu '''n''' există. De exemplu, cum '''1''', '''2''','''4''', '''5''', '''7''' și '''8''' sunt toate mai mici decât '''9''' și sunt relativ prime la '''9''', '''φ(9)=6'''. Numărul '''1''' e considerat a fi relativ prim cu toate numerele naturale, deci '''φ(1)=1'''. În mod interesant, '''φ(87109)=79180''', și se poate observa că '''87109''' e o permutare a lui '''79180'''.

Se consideră un șir de cel mult '''10000''' de numere naturale distincte mai mici decât '''10.000.000'''. Să se scrie un program care găsește valoarea lui '''n''', pentru care '''φ(n)''' e o permutare a lui n și fracția '''n/φ(n)''' are valoare minimă. Dacă sunt mai multe valori cu aceeași proprietate atunci se scrie prima valoare din șir. Dacă nu sunt valori cu proprietatea menționată se va scrie valoarea '''0'''.
== Date de intrare ==
Fișierul de intrare '''permeuler.in''' conține pe prima linie cel mult '''10000''' de numere naturale distincte mai mici decât '''10.000.000''', separate prin spații.
== Date de ieşire ==
Fișierul de ieșire '''permeuler.out''' va conține pe prima linie primul număr '''x''' pentru care '''φ(x)''' e o permutare a lui '''x''' și fracția '''x/φ(x)''' are valoare minimă.
== Restricții și precizări ==
* în fișier sunt cel mult 10000 de numere
* numerele de pe prima linie a fișierului de intrare vor fi mai mici decât 10.000.000
== Exemplu ==
; permeuler.in
: 1000 345 21 34567 5678 63 345678 1234
; permeuler.out
: Datele introduse corespund restricțiilor impuse.
: 21
== Explicație == 
În fișierul de intrare sunt '''2''' numere care îndeplinesc proprietatea cerută de problemă: '''21''' care are '''φ(21)=12''' și raportul '''21/φ(21)=1.75''' și '''63''' care are  '''φ(63)=36'''  și raportul  '''63/φ(63)=1.75'''. În fișierul de ieșire va fi scrisă valoarea '''21'''.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def validare_date_numere(n):
    flag = False
    if 0 <= int(n) <= 1000:
        flag = True
    return flag

def phi(n):
    result = n
    i = 2
    
    while i*i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
        i += 1
        
    if n > 1:
        result -= result // n
        
    return result

def is_permutation(a, b):
    dict_a = {c: str(a).count(str(c)) for c in range(10)}
    dict_b = {c: str(b).count(str(c)) for c in range(10)}
    return dict_a == dict_b

if __name__ == '__main__':
    if validare_date_numere(n):
        print("\nDatele de intrare corespund restricțiilor impuse.\n")
    with open('permeuler.in', 'r') as f:
        nums = list(map(int, f.readline().split()))
        
    min_ratio = float('inf')
    result = 0
    
    for n in nums:
        phin = phi(n)
        ratio = n / phin
        
        if is_permutation(n, phin) and ratio < min_ratio:
            min_ratio = ratio
            result = n
            
    with open('permeuler.out', 'w') as f:
        f.write(str(result))
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")




</syntaxhighlight>