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!



Divisibility properties of a stream of numbers
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.


