Density of multiples I have an infinite collection of positive integers $n_1,n_2,n_3,\ldots$ and I would like to find the density of the numbers divisible by one or more of these.* If the density does not exist, the algorithm can do anything (it's a promise problem).

If the numbers were pairwise coprime, this would simply be
$$
1-\prod_{i=1}^\infty1-\frac{1}{n_i}
$$
which can be approximated with partial products (and an integral for the omitted terms, if they're sufficiently well-behaved).

In the general case this doesn't work, but you can always take the terms $n_1,\ldots,n_k$, take their least common multiple $L$, and check each number $1,2,\ldots,L$ to see how many are divisible by one of the $k$ chosen numbers. But this becomes unwieldy quickly: with $n_i=i^2$ and $k=10$ the sum is about 6 million (taking maybe a second to compute), but with $k=20$ it's 50 quadrillion (taking hundreds of years).

Is this problem known? Is there a good way to approximate this number?

* The density of a subset $S$ of the positive integers
$$
\lim_{n\to\infty}\frac{|\{1,2,\ldots,n\}\cap S|}{n},
$$
that is, the expected fraction of numbers in the set as you look at larger and larger initial intervals. Sometimes this doesn't exist ("numbers starting with 1") but in this case we're promised that it does.



Here's an example of a simplification we can make to the problem. If one of the $n_i$ is prime, then you can


Remove all $n_j$ which are multiples of $n_i$, including $n_i$ itself.
Compute the new density $D_\text{new}$.
The density is $D = 1 - (1-D_\text{old})(1-1/n_i).$


This can be generalized to composite $n_i$ if all terms are either divisible by $n_i$ or else coprime to $n_i$.

This expands the size we can approach with the naive lcm algorithm, but it doesn't fundamentally alter it.
For computable functions LB from {1,2,3,...} to itself, if

1/(LB(1)) + 1/(LB(2)) + 1/(LB(3)) + 1/(LB(4)) + 1/(LB(5)) + ... ​ computably converges
and
there is a positive integer m such that for all integers i, if ​ m &lt; i ​ then ​ LB(i) ≤ ni

then the density exists and is computable by using m and the convergence to upper-bound the

probability of being divisible by something beyond the cutoff point. ​ (To verify that that argument works despite density not being countably additive, do that for each {1,2,...,n} separately.)

I only have a vague suggestion for possibly speeding up the finite part:

Perhaps in most cases you can find a good-enough bound on the

sizes of most of the high-order inclusion-exclusion intersections.