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

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
Esta entrada foi publicada em Computação, Demonstração, Matemática, Teoria dos Números com as etiquetas , , , . ligação permanente.

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

  1. 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!

    • 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.

  2. 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)

    • 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.

  3. 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.

    • 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.

  4. 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

    • 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

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

Logótipo da WordPress.com

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

Imagem do Twitter

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

Facebook photo

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

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s