project euler problem 70 https projecteuler netproblem70 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 96 the number 1 is considered to be relatively prime to every positive number so 11 interestingly 8710979180 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 nn produces a minimum this is essentially brute force calculate all totients up to 107 and find the minimum ratio of nn that way to minimize the ratio we want to minimize n and maximize n as much as possible so we can store the minimum fraction s numerator and denominator and calculate new fractions with each totient to compare against to avoid dividing by zero i opt to use cross multiplication references finding totients https en wikipedia orgwikieuler stotientfunctioneuler sproductformula calculates a list of totients from 0 to maxone exclusive using the definition of euler s product formula gettotients5 0 1 1 2 2 gettotients10 0 1 1 2 2 4 2 6 4 6 return true if num1 and num2 have the same frequency of every digit false otherwise hassamedigits123456789 987654321 true hassamedigits123 23 false hassamedigits1234566 123456 false finds the value of n from 1 to max such that nn produces a minimum solution100 21 solution10000 4435 calculates a list of totients from 0 to max_one exclusive using the definition of euler s product formula get_totients 5 0 1 1 2 2 get_totients 10 0 1 1 2 2 4 2 6 4 6 array of indexes to select return true if num1 and num2 have the same frequency of every digit false otherwise has_same_digits 123456789 987654321 true has_same_digits 123 23 false has_same_digits 1234566 123456 false finds the value of n from 1 to max such that n φ n produces a minimum solution 100 21 solution 10000 4435 i φ i
from __future__ import annotations

import numpy as np


def get_totients(max_one: int) -> list[int]:
    
    totients = np.arange(max_one)

    for i in range(2, max_one):
        if totients[i] == i:
            x = np.arange(i, max_one, i)  
            totients[x] -= totients[x] // i

    return totients.tolist()


def has_same_digits(num1: int, num2: int) -> bool:
    
    return sorted(str(num1)) == sorted(str(num2))


def solution(max_n: int = 10000000) -> int:
    

    min_numerator = 1  
    min_denominator = 0  
    totients = get_totients(max_n + 1)

    for i in range(2, max_n + 1):
        t = totients[i]

        if i * min_denominator < min_numerator * t and has_same_digits(i, t):
            min_numerator = i
            min_denominator = t

    return min_numerator


if __name__ == "__main__":
    print(f"{solution() = }")