Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 http://www.math.dartmouth.edu/~carlp/PDF/matching.pdf):

"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|improve this question
1  
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

 
discard

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

Browse other questions tagged or ask your own question.