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

Publicado em 5 de Março de 2009 por Américo Tavares

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]

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer

Ver todos os artigos de Américo Tavares →

Esta entrada foi publicada em Computação, Demonstração, Matemática, Teoria dos Números com as etiquetas Computação, Demonstração, Matemática, Prova. ligação permanente.

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

Vishal Lama diz:

6 de Março de 2009 às 22:08

Hi Américo,

From what I can understand, I think there is an error in the first equation of the above post. The right hand side of the equation, it seems, should have $f_{k-1}! \times (k-1)!$ and not $f_{k-1}! \times f_{k-1}!$ . Is there a way to translate your posts into English? And, also is there a way to learn Portuguese (for absolute beginners, of course!) using free online tools/lessons? :-) Thanks!

Responder
- Américo Tavares diz:
  
  6 de Março de 2009 às 23:44
  
  Hi Vishal,
  
  I have now corrected the error. Thanks!
  
  The most relevant part of this post is the proposition (proposição). Here I repeat (with adaptations) item 7 of this recent post of mine “Propriedades aritméticas ilustradas por 123456. Será um número interessante?” , where you can find a copy of my original statement and a proof by Jacques Glorieux, both in English.
  
  This representation of a positive integer can be found on page 192 of the Donald Knuth’s book mentioned above.
  
  The coefficients $f_k$ can be put in a sequence: entry A108731 of OEIS.
  
  These inequalities above $0\leq f_k\leq k\leq !\leq n<(k+1)!$ were also proved by Jacques Glorieux.
  
  Concerning Portuguese lessons I will inform myself and let you know.
  
  Thanks for your visit.
  
  Américo
  
  PS. I write above that if someone can establish stronger relations concerning $n,k,f_k$ it will be interesting , because the behavior of the sequence would be better understood.
Vishal Lama diz:

7 de Março de 2009 às 04:03

Américo, thank you indeed for your response! The result you showed above is kinda similar to the one contained in Zeckendorf’s theorem, which says that “every positive integer can be represented in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.” (Wikipedia)

Responder
- Américo Tavares diz:
  
  7 de Março de 2009 às 11:34
  
  Vishal, In item 3 of the same post I expanded 123456 as a sum of Fibonacci numbers as follows
  
  123456=121393+1597+377+55+21+13
  
  These are not consecutive and in this case are the greatest possible ones.
  
  I suspected that this representation was unique for every n but I was not aware of Zeckendorf’s theorem.
  
  Thanks for your information.
António Ferrão diz:

7 de Março de 2009 às 22:52

Conjecture: It’s also possible to define a symmetrical form of the factorial number system, similar to the binary symmetrical system, in which every next number representation differs from the original in just one position.

Conjectura: é igualmente possível definir uma representação factorial simétrica, com semelhanças à representação binária simétrica, na qual a passagem de um número para o seguinte difere apenas em uma posição.

Responder
- Américo Tavares diz:
  
  9 de Março de 2009 às 00:44
  
  Caro António,
  
  Pelo que diz parece-me que a representação binária simétrica que refere é o mesmo que o código Gray [Gray code] (Wikipédia/Wikipedia).
  
  (Neste código os números decimais $0,1,2,3,4,5,6,7,\dots$ são representados por $000,001,011,010,110,111,101,100,\dots$
  em vez da representação binária usual
  $000,001,010,011,100,101,110,111,\dots$ ).
  
  O que pretende seria então representar os números $n-1,n$ e $n+1$ de tal maneira que, em vez de (na notação do post) ter
  $n-1=(e_k,e_{k-1},\dots,e_2,e_1)_{k!}$ , $n=(f_k,f_{k-1},\dots,f_2,f_1)_{k!}$ e
  $n+1=(g_k,g_{k-1},\dots,g_2,g_1)_{k!}$ , tivesse $n-1=(e_i^{'},e_{i-1}^{'},\dots,e_2^{'},e_1^{'})_{i!}$ , $n=(f_i^{'},f_{i-1}^{'},\dots,f_2^{'},f_1^{'})_{i!}$
  e $n+1=(g_i^{'},g_{i-1}^{'},\dots,g_2^{'},g_1^{'})_{i!}$ , e de tal maneira que $(f_i^{'},f_{i-1}^{'},\dots,f_2^{'},f_1^{'})$ fosse igual, excepto numa coordenada, a $(e_i^{'},e_{i-1}^{'},\dots,e_2^{'},e_1^{'})$ e $(g_i^{'},g_{i-1}^{'},\dots,g_2^{'},g_1^{'})$ , sendo ainda necessário determinar $i$ (eventualmente diferente de $k$ ).
  
  Mesmo que a minha interpretação esteja correcta, esta conjectura é difícil de abordar por mim.
  
  PS. Para facilidade (ou necessidade) de comparação das coordenadas devo considerar um valor máximo de $k$ , que represento por $K$ . Neste caso passo a ter $K$ coordenadas e a representar os números $n-1,n$ e $n+1$ por forma a que, em vez de (na notação do post) se ter
  
  $n-1=(e_K,e_{K-1},\dots,e_2,e_1)_{K!}$ , $n=(f_K,f_{K-1},\dots,f_2,f_1)_{K!}$ e
  $n+1=(g_K,g_{K-1},\dots,g_2,g_1)_{K!}$ ,
  
  se tivesse
  
  $n-1=(e_K^{'},e_{K-1}^{'},\dots,e_2^{'},e_1^{'})_{K!}$ , $n=(f_K^{'},f_{K-1}^{'},\dots,f_2^{'},f_1^{'})_{K!}$
  e $n+1=(g_K^{'},g_{K-1}^{'},\dots,g_2^{'},g_1^{'})_{K!}$ , e de tal maneira que $(f_K^{'},f_{K-1}^{'},\dots,f_2^{'},f_1^{'})$ fosse igual, excepto numa coordenada, a $(e_K^{'},e_{K-1}^{'},\dots,e_2^{'},e_1^{'})$ e $(g_K^{'},g_{K-1}^{'},\dots,g_2^{'},g_1^{'})$ .
  Algumas destas primeiras coordenadas (as da esquerda) são nulas, excepto para valores altos de $n$ .
  A limitação que impuz a $k$ traduz-se numa limitação de $n$ a um máximo, a que chamo $N$ .
António Ferrão diz:

9 de Março de 2009 às 12:50

Caro Américo
A demonstração de Jacques Glorieux serve.
Consideremos um conjunto de K elementos, a respeito dos quais seja possível estabelecer uma relação de ordem total. Na prática, isso exclui a repetição de elementos, ou seja, exclui os arranjos que não sejam permutações.
A tese é a de que o número de ordem de tal permutação de K elementos entre todas as restantes permutações que é possível formar com os mesmos elementos está inscrito nas própria permutação. O número de inversões de cada elemento com os que se lhe seguem, ponderado pelo factorial da posição respectiva, permite obter tal número de ordem. É assim possível ordenar lexicalmente todas as permutações de tais elementos, desde a directa, com zero inversões, até à última, com K!-1 permutações, ou seja, a permutação inversa, que exibe inversões em todos os pares de posições.
O algoritmo é ilustrado aqui:
http://ferrao.org/2008/02/ordem-lexicogrfica.html
Chegamos assim ao seguinte:
O elemento na posição K permite (K-1) inversões com os elementos que se lhe seguem. Independentemente disso, com os restantes (K-1) elementos, que ocupam as posições que vão desde 1 até (K-1), podemos obter (K-1) inversões com os (K-2) elementos que ocupam as posições que se seguem. Até chegarmos à última posição, que permite zero inversões ponderadas pelo factorial de 1.
O sistema factorial simétrico passa por, alternadamente, considerar os k “algarismos” de base igual ao factorial da posição (k!), ora em ordem crescente, ora em ordem decrescente. Quando as K! permutações são reordenadas desta maneira, entre cada permutação e a seguinte verifica-se uma única troca de elementos.
Um abraço

Responder
- Américo Tavares diz:
  
  10 de Março de 2009 às 22:45
  
  Caro António,
  Vejo que a representação de 658 segundo o enunciado da proposição,
  658=5×5!+2×4!+1×3!+2×2!,
  corresponde ao método elegante que utilizou para chegar ao resultado do seu problema Número de ordem lexicográfica:
  «Determinar o número de arranjos que se podem
  formar com as seis letras da palavra
  xigubo
  que a antecedem na ordem lexicográfica, mas sem
  recorrer à lista exaustiva.»
  http://ferrao.org/labels/permuta=C3=A7=C3=B5es.html
  
  Eis uma bela ligação entre a aritmética e a análise combinatória!
  Parece-me igualmente bela a demonstração da proposição.
  Um abraço

Deixe uma Resposta Cancelar resposta

Insira aqui o seu comentário...

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

Email (obrigatório) (O endereço nunca será tornado público)

Nome (obrigatório)

Site da Web

Está a comentar usando a sua conta WordPress.com ( Terminar Sessão / Alterar )

Está a comentar usando a sua conta Twitter ( Terminar Sessão / Alterar )

Está a comentar usando a sua conta Facebook ( Terminar Sessão / Alterar )

Cancelar

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

	Arthur Antônio. em Perímetro da astróide
	Arthur Antônio. em Perímetro da astróide
	Tarso Coelho em A Matemática é uma Ciência? ::…
	António Ferrão em Redes Neuronais Artificiais
	maria eclair em Exercício de aplicação dos teo…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…

	Arthur Antônio. em Perímetro da astróide
	Arthur Antônio. em Perímetro da astróide
	Tarso Coelho em A Matemática é uma Ciência? ::…
	António Ferrão em Redes Neuronais Artificiais
	maria eclair em Exercício de aplicação dos teo…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…
	Carlos Alberto Guima… em Resolução da equação do 3.º gr…