Cobertura dos n primeiros primos

Uma questão bastante simples serviu para eu revisar e combinar duas ferramentas matemáticas: o princípio da inclusão-exclusão e as combinações.

A dúvida era: dados n primeiros primos, qual porcentagem dos inteiros é de múltiplos de ao menos um deles.

Se n=1, o único primo a ser considerado é o 2. Obviamente, metade dos inteiros é múltiplo de 2.

Com n=2, temos os primos 2 e 3. É preciso somar 1/2 e 1/3, mas também subtrair 1/6, porque esses 1/6 já foram contabilizados num caso ou noutro. Aí já vemos que precisamos das combinações e logo depois do princípio da inclusão-exclusão: somam-se as porcentagens de cada primo, depois subtraem-se as combinações dois a dois.

Então, preciso de duas funções e uma lista de primos. A função de combinações (choose) está descrita em detalhes noutro artigo.

#!/usr/bin/perl

my @primes=qw(2 3 5 7 11 13 17 19 23 29);

sub choose {
  my $n=shift;
  my $k=shift;
  my $callback=shift;
  my @rest=@_;
  
  if($k>0) {
    for my $m ($k..$n) {
      choose($m-1, $k-1, $callback, $m, @rest); 
      &$callback($m, @rest) if $k==1;
    }
  } 
}

for my $n (1..50) {
  my @g=@primes[0..$n-1];
  my $sum=0;
  my $op=1;
  for my $k (1..$n) {
    choose($n, $k, sub {
      my $product=1;
      map { $product*=$g[$_-1] } @_;
      $sum+=($op*(1/$product));
      print "$sum\r"; 
    });
    $op*=-1;
  }    
  print "$sum\n";
}

Esse código imprime a porcentagem dos inteiros que são múltiplos dos n primeiros primos, até o n=50. Eu reduzi a lista dos primos para encurtar o código, mas é fácil obter a lista dos primeiros 1000 primos.

O cálculo começa a ficar lento com n=15 ou nessa redondeza, conforme o computador.

O gráfico abaixo mostra a evolução. Ela parece convergir para algo perto de 0,9, mas na verdade ela vai muito lentamente em direção ao 1.

Agora, o que me interessa são as frações que esses números representam. Os primeiros são 1/2, 2/3, 11/15, e 27/35.