Problemas Teoremas

Setembro 19, 2010

Livro The P=NP Question and Gödels Lost Letter de Richard J. Lipton

Filed under: Computação,Livros,Matemática,Notícia — Américo Tavares @ 3:37 pm
Tags:

Este é o novo livro The P=NP Question and Gödels Lost Letter do Professor de Computer Science (Georgia Tech) Richard J. Lipton  derivado do seu blogue com quase o mesmo nome. Do Prefácio:

 ” This book is a collection of some of the most popular posts from my blog — Gödel Lost Letter and P=NP — the blog, especially when I started, was to explore various aspects of computational complexity around the famous P=NP question. As I published posts I branched out  and covered additional material, sometimes a timely event, sometimes a fun idea, sometimes a new result, and sometimes an old result. I have always tried to make the posts readable by a wide audience, and I believe I have succeeded in doing this. “  

Tomei conhecimento da sua existência, na sua última entrada, My Book On P=NP Is Now Available.

Março 22, 2010

Solução do Desafio sobre sequências (sucessões): descobrir o termo geral :: Solution to the Challenge: Find the general term of a sequence

Filed under: Computação,Enigmas,Matemática,Matemática-Básico,Matemática-Secundário,Math,PARI,Programação,Sucessões — Américo Tavares @ 10:37 am
Tags: , , , , , , ,

Enunciado do Desafio/Challenge Statement

Qual é o próximo termo da sucessão seguinte? / Which is the next term of the following sequence?

\dfrac{1}{4},\dfrac{1}{8},\dfrac{1}{8},\dfrac{3}{16},\dfrac{3}{8},\dots

E o termo de ordem 20? / And its 20^{\text{th }}  term?

Adenda/Addendum

Nota: os termos são fracções reduzidas.

Remark: every term of the sequence is a  fraction in its lowest terms.

    Solução/Solution

O termo geral da sucessão é/The sequence general term is:

   \dfrac{(n-1)!}{2^{n+1}}

mas expresso como fracção reduzida  [gcd (greatest common divisor) é o m.d.c. ou mdc  (máximo divisor comum)]/but written as a  fraction in its lowest terms 

  \dfrac{((n-1)!)/\gcd ((n-1)!,2^{n+1})}{2^{n+1}/\gcd ((n-1)!,2^{n+1})}\qquad (*)

 

 

Em PARI/GP obtém-se com/With this line of code in PARI/GP


        for(n=1,20,print(n ” : ” ((n-1)!/(2^(n+1)))))

isto / we get

    1 : 1/4
    2 : 1/8
    3 : 1/8
    4 : 3/16
    5 : 3/8
    6 : 15/16
    7 : 45/16
    8 : 315/32
    9 : 315/8
    10 : 2835/16
    11 : 14175/16
    12 : 155925/32
    13 : 467775/16
    14 : 6081075/32
    15 : 42567525/32
    16 : 638512875/64
    17 : 638512875/8
    18 : 10854718875/16
    19 : 97692469875/16
    20 : 1856156927625/32
   
   

Assim o sexto é/Hence the 6th term is

\dfrac{15}{16}

 e o vigésimo/and the 20th,

\dfrac{1856156927625}{32}.

   
O leitor d3r4z descobriu o 6.º temo aqui / The reader d3r4z found the 6th term here

(\ast ) – 24.03.10 –  acrescentado / added

Março 5, 2009

Dígitos de um número inteiro positivo na base factorial

Filed under: Computação,Demonstração,Matemática,Teoria dos Números — Américo Tavares @ 11:12 pm
Tags: , , ,

Suscitado pela ideia do leitor António Ferrão, acrescentei o ponto 7 ao meu artigo a propósito de 123456. Por considerar que merece ser autonomizado, e para não alongar esse artigo, republico agora esse tema com adaptações de exposição. A parte principal deve-se a Jacques Glorieux.

Trata-se de saber como se pode decompor em factoriais o inteiro positivo n.

Uma possível decomposição é

n=f_k\times k!+f_{k-1}\times (k-1)!+\dots+f_2\times 2!+f_1\times 1!

que é única, se se considerarem os maiores factoriais possíveis; uso a notação

(f_k,f_{k-1},\dots,f_2,f_1)_{k!}

para me referir à sucessão que a cada n faz corresponder os k inteiros obtidos por este método. Esta sucessão está registada na The On-line Encyclopedia of Integer Sequences com a identificação A108731 (autor: Frank Adams-Watters). Começa por

1,1,0,1,1,2,0,\dots,

visto que 1=(1)_{1!}, 2=(1,0)_{2!}, 3=(1,1)_{2!}, 4=(2,0)_{2!},\dots.

O desenvolvimento de n na forma indicada — que aparece no livro de Donald Knuth, The Art of Computer Programming, Vol II, p. 192, como me chamou a atenção António Ferrão — é, como disse, único.
\bigskip
Apresento a seguir uma tradução da demonstração de Jacques Glorieux da seguinte
\bigskip

Proposição. Seja n be um inteiro positivo. A decomposição

n=f_{k}\times k!+f_{k-1}\times (k-1)!+\cdots +f_{2}\times 2!+f_{1}\times 1!\qquad (1)

é única se admitirmos que k!, (k-1)!,\dots têm os maiores valores possíveis, a começar por k! e continuando no sentido decrescente.

Demonstração. Baseia-se no teorema do qual depende o algoritmo da divisão, a saber:

“Dados os inteiros a e b com b>0 existem dois únicos inteiros q e r, com 0\leq r<b tais que a=bq+r“

Admitamos que k é o maior inteiro tal que k!\leq n.

Então se dividirmos n por k! e se designarmos o quociente por f_{k}, temos:

n=f_{k}\times k!+r_{k}, em que r_{k} designa o resto da divisão (0\leq r_{k}<k!)

Distinguimos dois casos:

1. r_{k}=0

Neste caso, n=f_{k}\times k!. O desenvolvimento de n indicado em (1) está certo e é único. Temos f_{k-1}=f_{k-2}=\dots =f_{1}=0

2.r_{k}>0

Neste caso, denotemos por m o menor inteiro tal que

(k-m-1)!\leq r_{k} (m=0,1,...,k-2)

Dividamos r_{k} por (k-m-1)! : temos

r_{k}=f_{k-m-1}\times (k-m-1)!+r_{k-m-1}

(com 0\leq r_{k-m-1}<(k-m-1)!).

Assim n=f_{k}\times k!+f_{k-m-1}\times (k-m-1)!+r_{k-m-1}

que se pode escrever

n=f_{k}\times k!+f_{k-1}\times (k-1)!+\dots

\dots +f_{k-m}\times (k-m)!+f_{k-m-1}\times (k-m-1)!+r_{k-m-1}

com f_{k-1}=\dots =f_{k-m}=0

Podemos prosseguir da mesma maneira até chegarmos a:

r_{2}=f_{1}\times 1!+r_{1} (tem-se r_1=0, uma vez que 0\leq r_{1}<1!).

Provámos desta forma que:

n=f_{k}\times k!+f_{k-1}\times (k-1)!+\cdots +f_{2}\times 2!+f_{1}\times 1!

Esta decomposição de n é única, visto que os coeficientes f_{k} são determinados também de forma única pelo algoritmo da divisão. \qquad\square

No meu artigo “linkado” acima poderá ver também o texto em inglês.

Entre n,k e f_k verificam-se as seguinte relações, uma prova das quais se deve também a Jacques Glorieux:

0\leq f_k\leq k\leq k!\leq n<(k+1)!

Se algum leitor interessado conseguir estabelecer relações mais fortes do que estas, seria certamente útil para definir melhor o comportamento da sucessão.

Adenda de 6-3-2009

Uma interpretação informal poderá ser:

Vejamos o exemplo  123456=3×8!+3×6!+2×5!+4×4! .  123456 pode ter outras decomposições: por exemplo 

   123456=123456×1!

 Mas se nos restringirmos ao máximo factorial menor ou igual a 123456, encontramos  8!=40320 (9!= 362880>123456).

Agora subtraímos 8! de 123456:

    123456-8!= 83136

Prosseguimos de forma semelhante:

    83136-8!= 42816
    42816-8!= 2496
    2496-6!= 1776
    1776-6!= 1056
    1056-6!= 336
    336-5!= 216
    216-5!= 96
    96-4!= 72
    72-4!= 48
    48-4!= 24
    24-4!= 0

 Donde 123456=3×8!+3×6!+2×5!+4×4!.

 O caso geral é uma generalização deste procedimento. 

 É similar a 123456 na base 10

    123456-100000=23456

    23456-10000=13456
    13456-10000=3456
    3456-1000=2456
    2456-1000=1456
    1456-1000=456 

    456-100=356
    356-100=256
    256-100=156
    156-100=56

    56-10=46
    46-10=36
    36-10=26
    26-10=16
    16-10=6

    6-1=5
    5-1=4
    4-1=3
    3-1=2
    2-1=1
    1-1=0

 Donde 123456=1×100000+2×10000+3×1000+4×100+5×10+6×1.

[7-3-2009: corrigi erro na primeira decomposição, em resposta ao 1º. comentário] 
   

Julho 27, 2008

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

Filed under: Computação,Matemática,Notícia,Recorrência,Software,Sucessões,Teoria dos Números — Américo Tavares @ 9:10 am
Tags: , , , ,
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
)

 

Julho 26, 2008

Fórmula de Bailey-Borwein-Plouffe para calcular os dígitos hexadecimais de pi

Filed under: Computação,Divulgação,Matemática — Américo Tavares @ 11:42 am
Tags: , ,

A fórmula usada por David Bailey, Peter Borwein and Simon Plouffe para calcular os dígitos hexadecimais de \pi foi:

\displaystyle\pi =\displaystyle\sum_{k=0}^{\infty}\dfrac{1}{16^k}\left[\dfrac{4}{8k+4}-\dfrac{2}{8k+4}-\dfrac{1}{8k+5}-\dfrac{1}{8k+6}\right] .

Este é o artigo original dos investigadores para calcular os dígitos de \pi .

Por exemplo, os dígitos de ordem 10^6 a 10^{16}+13, a seguir à vírgula, são

 26C65E52CB4593.

Tema: Rubric. Blog em WordPress.com.