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.

  • $\begingroup$ This is just the multiplication table problem. There are $o(n^2)$ such numbers. $\endgroup$
    – Lucia
    Dec 17, 2019 at 18:14
  • $\begingroup$ 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. $\endgroup$ Dec 17, 2019 at 18:19
  • $\begingroup$ @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. $\endgroup$ Dec 17, 2019 at 18:22
  • $\begingroup$ @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. $\endgroup$ Dec 17, 2019 at 18:27

1 Answer 1


This is a placeholder for an answer that expands on Lucia's comment. GRP 2020.04.11.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.