Uma nova relação de recorrência geradora de números primos e 1’s demonstrada por Eric Rowland

Eric Rowland demonstrou que a seguinte relação de recorrência só gera 1’s e números primos 

a(n)-a(n-1)=\text{mdc }(n,a(n-1))

(com a condição inicial a(1)=7) no artigo recentemente publicado no Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8  intitulado  A Natural Prime-Generating Recurrence cujo resumo transcrevo:

« For the sequence defined by a(n) = a(n-1) + gcd(n,a(n-1)) with a(1) = 7 we prove that a(n)-a(n-1) takes on only 1’s and primes, making this recurrence a rare naturally occurring generator of primes. Toward a generalization of this result to an arbitrary initial condition, we also study the limiting behavior of a(n)/n and a transience property of the evolution. »

\bigskip

[“gcd” significa “greatest common divisor“]

\bigskip

Anteriormente tive oportunidade de ler alguns artigos de Rowland sobre a função zeta de Riemann publicados há uns anos na Internet. 

\bigskip

Actualização de 2-8-2008: Eric Rowland indica neste post A simple recurrence that produces complex behavior — and primes! de A New Kind of Science Blog a origem deste seu trabalho. Entretanto criou esta demonstração que explora a recorrência. Inicialmente tomei conhecimento deste artigo de Eric Rowland, no JIS, neste post de Jeffrey Shallit no blogue Recursivity , através desta entrada do blogue Logic Nest.

\bigskip

Seja r(n)=a(n)-a(n-1). O seguinte código permite obter, no software PARI (free software com licença GNU General Public License), os termos diferentes de um, para 2<n<101, da sucessão r(n).

r(5)=5,r(6)=3,r(11)=11,r(12)=3,r(23)=23, r(24)=3,r(47)=47,r(48)=3,r(50)=5,r(51)=3.

Todos os outros são iguais a um.

N=2;
X=7;
while(N<101,
  Y= X+gcd(N,X);
  if (Y-X>1,
    print(N ” : ” Y-X)
  );
  X=Y;
  N=N+1
)

 

About these ads

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Computação, Matemática, Notícia, Recorrência, Software, Sucessões, Teoria dos Números com as etiquetas , , , , . ligação permanente.

Deixar uma resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

WordPress.com Logo

Está a comentar usando a sua conta WordPress.com Log Out / Modificar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Log Out / Modificar )

Facebook photo

Está a comentar usando a sua conta Facebook Log Out / Modificar )

Google+ photo

Está a comentar usando a sua conta Google+ Log Out / Modificar )

Connecting to %s