# Counting multiples in short intervals

Has anyone seen a problem like this in the literature? There are likely more generalized versions in sieve theory, which I am willing to tackle, but I would prefer a more elementary approach if available. The problem below will ask only about multiples of integers from $$[n,2n)$$, but I will have to face $$[n,kn)$$ at some point.

Are there really about $$n^2(\log 2)$$ many integers in $$[2n,n^2]$$ which are divisible by some integer in $$[n,2n)$$?

At some point, a good formula will involve the floor function, but I don't want to type it out today, so will use expressions like $$n^2/(n+j) - 1$$ to approximate the number of multiples of $$n + j$$ (for integer $$j$$ in $$[0,n)$$) in the integer interval $$S=[2n,n^2]$$. To the first order, I can overcount to get $$n(n-2)T$$, where $$T$$ is the sum of reciprocals of integers in $$[n,2n)$$ ( and so get $$T$$ near $$\log 2$$ ), but now I need to worry about numbers which are multiples of both $$n+i$$ and $$n+j$$, and possibly also of $$n+h$$.

So the first question is how large is the second order term $$n(n-2)U$$, which $$U$$ is a sum of terms like $$\gcd (n+i,n+j)/((n+i)(n+j))$$? Is $$U$$ smaller than $$1/n$$?

And the second question is how much smaller are the rest of the terms which involve sums of terms like $$\gcd(n+i,n+j,n+h)/((n+i)(n+j)(n+h))$$? Surely there are fewer than $$n$$ of these multiples?

This is sort of like the Erdos multiplication table problem, but I am really interested in multiples in $$[2n,n^2)$$ coming from $$[n,kn)$$.

Gerhard "Solutions Are Preferred Over References" Paseman, 2019.12.17.

• This is just the multiplication table problem. There are $o(n^2)$ such numbers. Dec 17 '19 at 18:14
• Of course U is likely bigger than 1/n, but is it like a constant times 1/n? (Maybe counting multiples of (n+i)(n+i+p)/p gives a lower bound like log log n/n to U?) Gerhard "Could Live With LogLog Error" Paseman, 2019.12.17. Dec 17 '19 at 18:19
• @Lucia, except I am looking at entries outside the multiplication table for n by n. Or is there a reduction you see that I am not seeing? Is it a piece of a 2n by 2n table? Gerhard "Would Really Like A Reduction" Paseman, 2019.12.17. Dec 17 '19 at 18:22
• @Lucia, Thanks to you, I just found a reference to work of Kevin Ford on this. I may update this with the reference. Gerhard "Is Getting Ready To Read" Paseman, 2019.12.17. Dec 17 '19 at 18:27