MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Back to 1980, P.Erd\H{o}s and C. Pomerance asked in their paper "Matching the natural numbers up to n with distinct multiples in another interval" (see page 160 of the journal scan

"Related to these questions, we ask if there is a large constant $c$ so that in any interval of length $cn$ there are $\pi(n)-\pi(n/2)$ distinct multiples of the primes in $(n/2, n]$ (there need not be a matching). "

I am wondering if there is any progress on this question. Also, can we say anything if we require only some prime multiples to be present (e. g. we want to guarantee that there are distinct multiples of at least $O(n/\log n)$ primes from $(n/2, n]$)?

share|cite|improve this question
I am not aware of any direct progress on the question. Indirectly, I am looking at a kind of complement, which is the distribution of integers coprime to a given integer. My gut tells me that c does not exist for all n, but if k is the number of distinct prime factors of n, then there is a constant c so that intervals of length cf(k)n will have the distinct multiples requested. Here f(k) should be slow growing and subquadratic, say like k(log k)^2. Gerhard "Gut Has Been Wrong Before" Paseman, 2013.01.22 – Gerhard Paseman Jan 22 '13 at 22:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.