6  Os números de Erdős-Woods

Neste projeto vamos investigar uma classe interessante de números naturais.

6.1 Os números

Vamos chamar um intervalo de números naturais \(\{a,a+1,\ldots,a+k\}\) intervalo de Erdős-Woods, se todo número \(m\in\{a,a+1,\ldots,a+k\}\) tem algum fator comum ou com \(a\) ou com \(a+k\). Por exemplo, o intervalo \[ \{5,6,7,8,9\} \] não é de Erdős-Woods, pois \(7\) é coprimo com \(5\) e também com \(9\). Um número natural \(k\in\mathbb N\) é dito número de Erdős-Woods (veja também na OEIS), se existe um intervalo de Erdős-Woods na forma \(\{a,\ldots,a+k\}\). Por exemplo, \(2\) não é número de Erdős-Woods, pois no intervalo \(\{a,a+1,a+2\}\), o número \(a+1\) é coprimo com \(a\) e também com \(a+2\).

6.2 Exploração interativa

Vamos verificar por exemplo que \(\{10,11,12,13,14,15\}\) não é de Erdős-Woods.

gap> a := 10; k := 5;
10
5
gap> Filtered( [a..a+k], x-> GcdInt( a, x ) = 1 and GcdInt( a+k,x) = 1 );
[ 11, 13 ]

Ou seja, os números \(11\) e \(13\) são coprimos com o início e com o final do intervalo. Logo este intervalo não é de Erdős-Woods.

6.3 Tarefa

  1. Escreva uma função is_ew_interval( a, k ) que verifica se o intervalo \(\{a,a+1,\ldots,a+k\}\) é de Erdős-Woods. A função deve devolver true ou false dependendo se o intervalo é de Erdős-Woods. A sua função deve funcionar na seguinte forma.
gap> is_ew_interval( 10,5 );
false
gap> is_ew_interval( 13,4 );
false
  1. Use a função escrita no item anterior para verificar que os números \(16\) e \(22\) são de Erdős-Woods. Ache os intervalos que testemunham que estes números são de fato de Erdős-Woods.
  2. Consegue achar mais números de Erdős-Woods?

Para verificar um intervalo, pode usar Filtered como no exemplo anterior ou o laço for (Seção 5.2) e a função GcdInt (manual) dentro do laço. A expressão break (Seção 5.8) também pode ser útil caso queira usar laços.

Este projeto foi inspirado pelo seguinte vídeo.