gpt4_solution.py

import json
import time

# START - CODE GENERATED BY gpt4
def solution():
    def is_permutation(a, b):
        return sorted(str(a)) == sorted(str(b))

    def phi(n, prime_factors):
        result = n
        for p in prime_factors:
            result *= (p - 1)
            result //= p
        return result

    def prime_sieve(limit):
        is_prime = [True] * (limit + 1)
        p = 2
        while p * p <= limit:
            if is_prime[p]:
                for i in range(p * p, limit + 1, p):
                    is_prime[i] = False
            p += 1
        return [p for p in range(2, limit + 1) if is_prime[p]]

    limit = 10**7
    primes = prime_sieve(int(limit**0.5) + 1)
    min_ratio = float('inf')
    result_n = 0

    for i in range(2, limit):
        n = i
        prime_factors = set()
        for p in primes:
            if p * p > n:
                break
            if n % p == 0:
                while n % p == 0:
                    n //= p
                prime_factors.add(p)
        if n > 1:
            prime_factors.add(n)

        phi_n = phi(i, prime_factors)
        if is_permutation(i, phi_n):
            ratio = i / phi_n
            if ratio < min_ratio:
                min_ratio = ratio
                result_n = i

    return result_n
# END - CODE GENERATED BY gpt4

cpu_s, wall_s = time.process_time(), time.time()
result = solution()
cpu_e, wall_e = time.process_time(), time.time()

cpu_time, wall_time = cpu_e - cpu_s, wall_e - wall_s
print(json.dumps({"solution": result, "cpu": cpu_time, "wall": wall_time}))