<p>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).</p>

<p>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).</p>

<p>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).</p>

<p>Is this problem known? Is there a good way to approximate this number?</p>

<p><i></i>* The <em>density</em> 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.</p>

<hr>

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

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

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

<p>This expands the size we can approach with the naive lcm algorithm, but it doesn't fundamentally alter it.</p>

CC BY-SA 3.0
2016-07-29T16:34:02.263Z
@RickyDemer: What if I can add in superlinear bounds, say the t-th entry is between $t^2/10$ and $10t^2$?
Charles
CC BY-SA 3.0
2016-07-29T17:13:59.647Z
@RickyDemer: For what it's worth I'm trying to actually calculate these densities, and it's perfectly fine for the algorithm to give unhelpful answers ("the density is between 0.01 and 1") to perverse cases.
Charles
<ds.algorithms><reference-request><approximation-algorithms><na.numerical-analysis><promise-problems>
Density of multiples
Charles
# Density of multiples

(Asked by: username_0 on 2016-07-29)

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

1. Remove all $n\_j$ which are multiples of $n\_i$, including $n\_i$ itself.
2. Compute the new density $D\_\text{new}$.
3. 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.

**Tags:** ds.algorithms, reference-request, approximation-algorithms, na.numerical-analysis, promise-problems

> **Comments:**
> **username_0**: @RickyDemer: What if I can add in superlinear bounds, say the t-th entry is between $t^2/10$ and $10t^2$?  
> **username_0**: @RickyDemer: For what it's worth I'm trying to actually calculate these densities, and it's perfectly fine for the algorithm to give unhelpful answers ("the density is between 0.01 and 1") to perverse cases.  

---

## 0 answers

