import time
def mobius(n):
    """Berechnet die Möbius-Funktion μ(n)"""
    if n == 1:
        return 1
    prime_factors = 0
    i = 2
    while i * i <= n:
        if n % i == 0:
            n //= i
            prime_factors += 1
            if n % i == 0:
                return 0  # n enthält ein Quadrat eines Primfaktors
        i += 1
    if n > 1:
        prime_factors += 1
    return -1 if prime_factors % 2 else 1

def mertens(n):
    """Berechnet die Mertens-Funktion M(n)"""
    mertens_sum = 0
    for k in range(1, n + 1):
        mertens_sum += mobius(k)
    return mertens_sum

def find_x_for_condition(n,start, limit):
    """Finde das klenste x für ein gegebenes n, für das M(x) > x^(1/n) gilt."""
    for x in range(start, limit):
        if abs(mertens(x)) > x ** (1 / n):
            return x
    return limit


# Beispiel: Suche nach x für n=2
n = 2.3
limit=10000
start=1000
start_time=time.time()
x = find_x_for_condition(n,start, limit)
end_time=time.time()

elapsed_time=end_time-start_time

if isinstance(x, int):
    if x == limit:
        print(f"Kein x im Bereich bis {limit:,} gefunden.".replace(",", "."))
        print(f"Die Berechnung hat {elapsed_time:.6f} Sekunden gedauert.")
    else:
     print(f"Das kleinste x, für das M(x) > x^(1/n) für n={n} gilt, ist x = {x:,}".replace(",", "."))
     print(abs(mertens(x)))
     print(x**(1/n))
     print(f"Die Berechnung hat {elapsed_time:.6f} Sekunden gedauert.")