Computação « problemas

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]

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
)

	Eduardo Lazarini no Matemática, papel e caneta, e …
	mario dumbo hossi no Descobrir a Moeda Falsa
	Américo Tavares no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	anonimo no Dodecaedro e outros poliedros…
	Elias_Brasil no Probabilidades com cartas
	Pedro Cunha no Caderno
	Andrea no Matemática, papel e caneta, e …
	alessandro no Caderno

Category Archive

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

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

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

Américo Tavares

Bem-vindo(a)!

Últimos Comentários e respostas

Arquivos

Últimos Artigos

Categorias (Temas)

Acompanhamento via RSS de Blogues com Matemática

… em português

A MATEMÁTICA ANDA POR AÍ

Disquisitiones Mathematicae

Geometria

morfismo

… não portugueses

Gaussianos

Gower’s Weblog

The Unapologetic Mathematician

Todd and Vishal’s blog

What’s new

Weblog de Pierre Bernard

Ligações (Links)

Matemática

Matemática/Computação

Matemática/Problemas

Matemática/Publicações, bibliotecas online

Meu blogue auxiliar

Outros: ciências, tecnologia e economia, etc.

N.º de Visualizações (início: Out. 2007)

Acompanhe este blogue via RSS

COMENTÁRIOS