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.

Telegram bot no OpenWRT

O roteador TP-Link WR842ND, além de ser relativamente barato, possui uma porta USB e permite rodar o OpenWRT. O desempenho dele (266,64 Bogomips) é semelhante ao de um Pentium 133. Ele possui 8MB de Flash e 32MB de RAM. Então, é uma máquina com potencial. Seria uma pena que fosse usada apenas para oferecer wifi.

Adicionei um pendrive de 16GB e um amigo gentilmente instalou e configurou o OpenWRT (Gargoyle, para ser mais preciso). Além de roteador, com muitos gigas livres, ele pode virar um servidor de arquivos e posso deixar um download grande rodando nele durante a noite, por exemplo.

Ele não oferece o X, obviamente, mas tem uma linha de comando completa via o BusyBox. Já que tenho mais memória via o pendrive, instalei o Perl para facilitar as tarefas.

Para gerenciá-lo remotamente, resolvi escrever um bot do Telegram. E para dar mais emoção, decidi usar o que estivesse já instalado. Só abri exceção para o curl, porque não sou tão masoquista. O shell disponível é o ash: limitado, mas pequeno e eficiente.

O Telegram oferece uma interface sobre HTTP com mensagens em JSON. Por sorte, o OpenWRT já oferece uma ferramenta para processar JSON: jsonfilter. Por azar, não tem nenhuma documentação. Só encontrei o modo de usar no código-fonte.

Então, a única peça que faltava era o curl.

opkg install curl

E esse comando instala um executável de apenas 69KB.

Para enviar uma mensagem com o IP do roteador, um script simples basta:

#!/bin/ash

ip=$(ifconfig eth0 | grep inet | grep -v inet6 | awk '{print $2}')

api=https://api.telegram.org/bot<key>
curl -k -s -X POST $api/sendMessage?chat_id=<id>&text=$ip

A opção -k indica que o curl pode ignorar os erros de certificado, o -s suprime as mensagens e o -X precede o POST.

Resolvi colocar cada comando em um arquivo distinto. Para retornar o resultado ao script de controle, duas variáveis são necessárias: telegram_reply para indicar se houve sucesso no processamento e telegram_message com o texto da resposta. Talvez no futuro seja preciso adicionar telegram_type, se eu quiser enviar fotos, por exemplo. O script para tratar o comando /ip fica assim:

#!/bin/ash

ip=$(ifconfig eth0 | grep inet | grep -v inet6 | awk '{print $2}')

telegram_message=$ip
telegram_reply=true

O método getUpdates (que informa os últimos comandos) pode receber um parâmetro para indicar quais comandos já foram respondidos. Para manter registro desse parâmetro, criei um arquivo /tmp/bot_vars.sh. Ele conterá apenas uma linha na forma offset=123.

Então, o script que solicita os comandos e os encaminha para os scripts específicos precisa:

1. Solicitar os comandos;
2. Extrair os ids das solicitações, os ids dos solicitantes, e os comandos propriamente ditos;
3. Para cada comando, separar os parâmetros e invocar o respectivo script;
4. Se o script retornou com sucesso, enviar a mensagem produzida;
5. atualizar o arquivo /tmp/bot_vars.sh com o id do último comando.

#!/bin/ash

key='segredo';
api="https://api.telegram.org/bot$key"
source /tmp/bot_vars.sh
offset=$(($offset+1))
status=0
updates=$(curl -s -k -X GET $api/getUpdates?offset=$offset)
status=$(jsonfilter -s "$updates" -e $.ok)
if [ $status = 'true' ]; then
  update_ids=$(jsonfilter -s "$updates" -e $.result[*].update_id)

  for update_id in $update_ids
  do
    sender=$(jsonfilter -s "$updates" \
                        -e "$.result[@.update_id=$update_id].message.from.id")
    command=$(jsonfilter -s "$updates" \
                         -e "$.result[@.update_id=$update_id].message.text")
    cmd=$(echo $command |  awk '{print $1}')
    parms=$(echo $command | awk '{$1=""; print $0}')

    telegram_reply=false
    case $cmd in
      '/ip') source ip.sh $parms ;;
    esac

    if [ $telegram_reply = 'true' ]; then
      curl -k -s -X POST \
        $api/sendMessage -d chat_id=$sender -d text="$telegram_message"
    fi
    
  done

  if [ -n "$update_ids" ]; then
    echo "offset=$update_id" > /tmp/bot_vars.sh
  fi
fi

Não é o quadro mais lindo do museu, mas, sendo shell, não se poderia esperar muito mais. Agora, tenho que me preocupar com os problemas de segurança que isso deve ter.