Múltiplos dos primos

Há anos eu havia escrito um programa para encontrar inteiros candidatos a primos, pulando todos os que eu já sabia serem múltiplos de alguns poucos primos.

Resolvi brincar com o contrário: achar sequências de pulos que levariam a múltiplos dos primeiros primos.

#!/usr/bin/perl
my @primes=qw(
      2      3      5      7     11     13     17     19     23     29 
     31     37     41     43     47     53     59     61     67     71 
     73     79     83     89     97    101    103    107    109    113 
    127    131    137    139    149    151    157    163    167    173 
    179    181    191    193    197    199    211    223    227    229 
    233    239    241    251    257    263    269    271    277    281 
    283    293    307    311    313    317    331    337    347    349 
    353    359    367    373    379    383    389    397    401    409 
    419    421    431    433    439    443    449    457    461    463 
    467    479    487    491    499    503    509    521    523    541 
    547    557    563    569    571    577    587    593    599    601 
    607    613    617    619    631    641    643    647    653    659 
    661    673    677    683    691    701    709    719    727    733 
    739    743    751    757    761    769    773    787    797    809 
    811    821    823    827    829    839    853    857    859    863);

my @steps=(2);
my $product=1;
my @sub=@primes[0..5];
map { $product*=$_ } @sub;
for my $i (2..$product) {
  $found=0;
  for (@sub) {
    if ($i%$_==0) {
      $found=1;
      last;
    }
  }
  if($found) {
    push @steps, $s;
    $s=1;
  } else {
    $s++;
  }
}
print "@steps\n";

A série precisa ir até o produtório dos n primos. Para n=2 (2 e 3), ela vai até 6. Para n=3 (2, 3, e 5), vai até 30, e assim por diante. Os passos são sempre de 1 ou 2, porque um passo maior que 2, pularia um par.

Os primeiros resultados são:

n=1 
2
n=2 
2 1 1 2
n=3 
2 1 1 1 1 2 1 1 2 2 1 1 2 2 1 1 2 1 1 1 1 2
n=4 
2 1 1 1 1 1 1 1 1 2 2 1 1 2 2 1 1 2 1 1 1 1 2 2 1 1 1 1 2 1 1 2 2 1 1 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 2 1 1 
2 2 1 1 1 1 2 1 1 2 1 1 1 1 2 1 1 1 1 1 1 2 1 1 2 2 1 1 2 2 1 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 1 2 1 1 1 1 2 2 
1 1 2 1 1 1 1 2 2 1 1 1 1 2 1 1 1 1 2 1 1 2 2 1 1 2 1 1 1 1 2 2 1 1 1 1 2 1 1 2 2 1 1 2 2 1 1 1 1 1 1 1 1 2

A soma é igual ao produto, obviamente. Ademais, os inversos das médias são as sequência de frações da última investigação sobre primos. Isto é, para n=2, a média é 6/4 e os dois primos são fatores de 2/3 dos números inteiros. Além disso, as duas metades das sequências são espelhadas, o que podemos usar para economizar espaço e processamento.