Divisibility properties of a stream of numbers

Question

Let $S$ be a set of $k$ distinct natural numbers, each from the interval $[2,n]$, with least common multiple $\mathop{lcm}$. What fraction $\rho$ of the numbers $2,3,4,\ldots,\mathop{lcm}$ are divisible by a member of $S$?

For example, if $S=(4,6,8,9)$, then $|S|=k=4$, $n=9$, and $\mathop{lcm}=72$. The numbers $2,\ldots,\mathop{lcm}$ that are divisible by a member of $S$ are $$D=(4,6,8,9,12,16,18,20,24,27,28,30,32,36,40,42,44,45,48,52,54,56,60,63,64,66,68,72)\;.$$ There are $|D|=28$ of these numbers, so $\rho=|D|/\mathop{lcm}=28/72=0.39$: 39% of the numbers up to $\mathop{lcm}$ are divisible by a member of $S$.

This question arose in a colleague's work on online algorithms analyzing a stream of numbers represented by $S$. A few more examples before asking specific questions:

• For $S=(2, 4, 8, 16, 32)$, $|D|=16$ and $\rho=0.5$.
• For $S=(b^1, b^2, b^3, \ldots, b^r)$, $|D|=b^{r-1}$ and $\rho=1/b$.
• For $S=(2, 3, 5, 7, 11)$, $\mathop{lcm}=2310$, $|D|=1830$, and $\rho=0.79$.
• For $S=(2, 3, 4, 5, 6, 7, 8, 9, 10, 11)$, $\mathop{lcm}=27720$, $|D|=21960$, and $\rho=0.79$.

Q1. As a function of $n$, the largest number in $S$, what is the maximum value of $\rho$ achievable?

Q2. As a function of $n$ and $k$, what is the expected value of $\rho$ if the $k$ elements of $S$ are chosen randomly from the range $[2,n]$? For example, for $n=10$ and $k=4$, $\rho \approx 0.55$.

Q3. Given $S$, can $D$ be computed in time proportional to $|D|$? Can $|D|$ be computed faster, in $o(|D|)$?

Especially Q1 feels like it should be known. Thanks for pointers or tips!

Answer 1

Let $L$ denote the lcm of your $k$ numbers. If a number $\ell$ below $L$ is divisible by one of the $k$ numbers, then $\ell$ must have some common factor $>1$ with $L$. Therefore the number of elements you want is bounded above by $L-\phi(L)$ (the numbers that are not coprime to $L$).

So if the $k$ numbers are all below $n$, then the lcm of these numbers is some $L$ which divides $\text{lcm}[1,...,n] =L(n)$ say. Thus the maximum proportion that may be attained is $$ 1- \frac{\phi(L)}{L} \le 1 -\frac{\phi(L(n))}{L(n)} = 1- \prod_{p\le n} \Big(1-\frac 1p\Big). $$

This bound may be attained by taking your $k$ numbers to be the primes below $n$.

If the $k$ numbers are $a_1$, $\ldots$, $a_k$ then we can work out $\rho$ by inclusion exclusion. So $\rho$ is the sum of the reciprocals of the $a_i$ - the sum of the reciprocals of lcms taken two at a time + the sum of reciprocals of lcms taken three at a time etc. If $k$ is small compared with $n$ (if $k=o(n/(\log n)^{3/2}$ I think) then we can calculate the expected value of $\rho$ (Question 2). Only the sum of the reciprocals of the $a_j$ should matter, and the expected value of $\rho$ should be about $(k/n) \log n$. When $k$ gets larger things seem more complicated ... .

More comments: It turns out that the problem you proposed of studying the multiples of a set of numbers has been extensively studied. There is a Cambridge Tract (number 118) "Sets of Multiples" by R.R. Hall that deals with this problem. For example one situation that was considered first by Erdos is the case when the set is the numbers from $n/2$ to $n$. Here the density of the sets of multiples goes to zero, with a curious rate related to the ``Multiplication table problem." Anyway Hall's book should contain what's known on the problem.