3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ For all integers n greater than 1, distinguishing between density 1 and density 1/n is RE-hard: ​ For Turing machines M, the 0th entry is n and for all positive integers t, the t-th entry given by [if M runs for more than t steps then double the previous entry, else 1 plus the previous entry]. ​ ​ ​ ​ $\endgroup$
    – user6973
    Jul 29, 2016 at 15:31
  • $\begingroup$ @RickyDemer: What if I can add in superlinear bounds, say the t-th entry is between $t^2/10$ and $10t^2$? $\endgroup$
    – Charles
    Jul 29, 2016 at 16:34
  • $\begingroup$ I'll think on that. ​ ​ $\endgroup$
    – user6973
    Jul 29, 2016 at 16:59
  • $\begingroup$ @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. $\endgroup$
    – Charles
    Jul 29, 2016 at 17:13

1 Answer 1

2
$\begingroup$

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 < 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.

$\endgroup$
3
  • $\begingroup$ Indeed, finding ways to handle the hairy inclusion-exclusion of that method was my motivation in posting this question! $\endgroup$
    – Charles
    Jul 29, 2016 at 18:07
  • $\begingroup$ Have you tried what I'd call branch-and-bound even though the bounding is very different from what that usually means? d​W (namely, discarding when you have a good-enough bound on the error caused by doing so) ​ Have you tried using the method of moments to bound the probability that the number of divisibilities is zero? ​ (Chebyshev's inequality is the simplest example of that.) ​ ​ ​ ​ $\endgroup$
    – user6973
    Jul 29, 2016 at 19:07
  • $\begingroup$ I haven't, and that sounds interesting. It might just work. $\endgroup$
    – Charles
    Jul 29, 2016 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.