Numeração bijetiva - Bijective numeration
Sistemas numéricos |
---|
Sistema de numeração hindu-arábica |
leste Asiático |
americano |
Alfabético |
Antigo |
Sistemas posicionais por base |
Sistemas de numeração posicional não padronizados |
Lista de sistemas numéricos |
A numeração bijetiva é qualquer sistema numeral no qual todo número inteiro não negativo pode ser representado exatamente de uma maneira usando uma seqüência finita de dígitos . O nome deriva dessa bijeção (correspondência um a um) entre o conjunto de inteiros não negativos e o conjunto de strings finitas usando um conjunto finito de símbolos (os "dígitos").
A maioria dos sistemas numéricos comuns, como o sistema decimal comum , não são bijetivos porque mais de uma sequência de dígitos pode representar o mesmo número inteiro positivo. Em particular, adicionar zeros à esquerda não altera o valor representado, portanto, "1", "01" e "001" representam o número um . Mesmo que apenas a primeira seja usual, o fato das demais serem possíveis significa que decimal não é bijetivo. Porém, unário , com apenas um dígito, é bijetivo.
Um bijectiva de base - k numeração é um bijective notação posicional . Ele usa uma sequência de dígitos do conjunto {1, 2, ..., k } (onde k ≥ 1) para codificar cada inteiro positivo; a posição de um dígito na string define seu valor como um múltiplo de uma potência de k . Smullyan (1961) chama essa notação de k -adic, mas não deve ser confundida com os números p -adic : os numerais bijetivos são um sistema para representar inteiros comuns por cadeias finitas de dígitos diferentes de zero, enquanto os números p -adic são um sistema de valores matemáticos que contêm os inteiros como um subconjunto e podem precisar de sequências infinitas de dígitos em qualquer representação numérica.
Definição
O sistema de numeração bijetivo de base k usa o conjunto de dígitos {1, 2, ..., k } ( k ≥ 1) para representar de forma única cada inteiro não negativo, como segue:
- O zero inteiro é representado pela string vazia .
- O número inteiro representado pela sequência de dígitos não vazios
- a n a n −1 ... a 1 a 0
- é
- a n k n + a n −1 k n −1 + ... + a 1 k 1 + a 0 k 0 .
- A sequência de dígitos que representa o inteiro m > 0 é
- a n a n −1 ... a 1 a 0
- Onde
- e
- sendo o menor inteiro não menor que x (a função de teto ).
Em contraste, a notação posicional padrão pode ser definida com um algoritmo recursivo semelhante, onde
Extensão para inteiros
Para base , o sistema de numeração de base bijetivo poderia ser estendido para inteiros negativos da mesma maneira que o sistema de numeração de base padrão , usando um número infinito do dígito , onde , representado como uma sequência infinita à esquerda de dígitos . Isso ocorre porque o somatório de Euler
significa que
e para cada número positivo com numeração bijetiva, a representação do dígito é representada por . Para base , os números negativos são representados por com , enquanto para base , os números negativos são representados por . Isso é semelhante a como nas representações de dígitos com sinais , todos os inteiros com representações de dígitos são representados como onde . Essa representação não é mais bijetiva, pois todo o conjunto de sequências infinitas à esquerda de dígitos é usado para representar os inteiros -adic , dos quais os inteiros são apenas um subconjunto.
Propriedades de numerais de base k bijetivos
Para uma determinada base k ≥ 1,
- há exatamente k n numerais de base- k do bijetivo de comprimento n ≥ 0.
- se k ≥ 2, o número de dígitos no numeral de base k bijetivo que representa um inteiro não negativo n é , em contraste com os numerais de base k comuns ; se k = 1 (isto é, unário), então o número de dígitos é apenas n ;
- Se k ≥ 2, a base-bijective k e base- comuns k numerais para um número inteiro não negativo n são idênticos se e apenas se o numeral normal não contém o dígito 0 (ou, de forma equivalente, o numeral bijective não é nem a cadeia vazia nem contém o dígito k ).
- uma lista de numerais de base- k bijetivos , na ordem natural dos inteiros representados, é automaticamente na ordem shortlex (o mais curto primeiro, lexicográfico dentro de cada comprimento). Assim, usando λ para denotar a string vazia , os numerais de base 1, 2, 3, 8, 10, 12 e 16 são os seguintes (onde as representações comuns são listadas para comparação):
base 1 do bijetivo: | λ | 1 | 11 | 111 | 1111 | 11111 | 111111 | 1111111 | 11111111 | 111111111 | 1111111111 | 11111111111 | 111111111111 | 1111111111111 | 11111111111111 | 111111111111111 | 1111111111111111 | ... | ( sistema numérico unário ) | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
base 2 do bijetivo: | λ | 1 | 2 | 11 | 12 | 21 | 22 | 111 | 112 | 121 | 122 | 211 | 212 | 221 | 222 | 1111 | 1112 | ... | |||||||||||
binário: | 0 | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | 10000 | ... | |||||||||||
base 3 do bijetivo: | λ | 1 | 2 | 3 | 11 | 12 | 13 | 21 | 22 | 23 | 31 | 32 | 33 | 111 | 112 | 113 | 121 | ... | |||||||||||
ternário: | 0 | 1 | 2 | 10 | 11 | 12 | 20 | 21 | 22 | 100 | 101 | 102 | 110 | 111 | 112 | 120 | 121 | ... | |||||||||||
base do bijetivo 8: | λ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | ... | |||||||||||
octal: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 20 | ... | |||||||||||
base 10 do bijetivo: | λ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | 11 | 12 | 13 | 14 | 15 | 16 | ... | |||||||||||
decimal: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ... | |||||||||||
base 12 do bijetivo: | λ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | 11 | 12 | 13 | 14 | ... | |||||||||||
duodecimal: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | 10 | 11 | 12 | 13 | 14 | ... | |||||||||||
base do bijetivo 16: | λ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | G | ... | |||||||||||
hexadecimal: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | 10 | ... |
Exemplos
- 34152 (no bijetivo base-5) = 3 × 5 4 + 4 × 5 3 + 1 × 5 2 + 5 × 5 1 + 2 × 1 = 2427 (em decimal).
- 119A (no bijetivo base-10, com "A" representando o valor do dígito dez) = 1 × 10 3 + 1 × 10 2 + 9 × 10 1 + 10 × 1 = 1200 (em decimal).
- Uma lista alfabética típica com mais de 26 elementos é bijetiva, usando a ordem de A, B, C ... X, Y, Z, AA, AB, AC ... ZX, ZY, ZZ, AAA, AAB, AAC. ..
O sistema bijetivo de base 10
O sistema bijetivo de base 10 é um sistema numeral posicional de base dez que não usa um dígito para representar zero . Em vez disso tem um dígito para representar dez, tais como A .
Tal como acontece com o decimal convencional , cada posição do dígito representa uma potência de dez, então, por exemplo, 123 é "cem, mais duas dezenas, mais três unidades." Todos os inteiros positivos que são representados apenas com dígitos diferentes de zero em decimal convencional (como 123) têm a mesma representação em decimal sem um zero. Aqueles que usam um zero devem ser reescritos, então por exemplo 10 torna-se A, convencional 20 torna-se 1A, convencional 100 torna-se 9A, convencional 101 torna-se A1, convencional 302 torna-se 2A2, convencional 1000 torna-se 99A, convencional 1110 torna-se AAA, convencional 2010 torna-se 19AA , e assim por diante.
A adição e a multiplicação em decimal sem zero são essencialmente as mesmas que com o decimal convencional, exceto que os carregamentos ocorrem quando uma posição excede dez, em vez de quando ultrapassa nove. Então, para calcular 643 + 759, existem doze unidades (escreva 2 à direita e carregue 1 às dezenas), dez dezenas (escreva A sem precisar carregar para as centenas), treze centenas (escreva 3 e carregue 1 para o milhares) e mil (escreva 1), para dar o resultado 13A2 em vez do 1402 convencional.
O sistema bijetivo de base 26
No sistema bijetivo de base 26, pode-se usar as letras do alfabeto latino de "A" a "Z" para representar os valores de 26 dígitos de um a vinte e seis . (A = 1, B = 2, C = 3, ..., Z = 26)
Com esta escolha de notação, a sequência numérica (começando em 1) começa A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB , BC, ...
Cada posição de dígito representa uma potência de vinte e seis, então, por exemplo, o numeral ABC representa o valor 1 × 26 2 + 2 × 26 1 + 3 × 26 0 = 731 na base 10.
Muitas planilhas, incluindo o Microsoft Excel, usam este sistema para atribuir rótulos às colunas de uma planilha, começando A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA , etc. Por exemplo, no Excel 2013, pode haver até 16384 colunas (2 14 em código binário), rotuladas de A a XFD. Uma variante desse sistema é usada para nomear estrelas variáveis . Pode ser aplicado a qualquer problema onde uma nomenclatura sistemática usando letras é desejada, usando as sequências de caracteres mais curtas possíveis.
Notas históricas
O fato de que todo inteiro não negativo tem uma representação única no bijetivo base- k ( k ≥ 1) é um “ teorema popular ” que foi redescoberto muitas vezes. As primeiras instâncias são Foster (1947) para o caso k = 10, e Smullyan (1961) e Böhm (1964) para todo k ≥ 1. Smullyan usa este sistema para fornecer uma numeração de Gödel das cadeias de símbolos em um sistema lógico; Böhm usa essas representações para realizar cálculos na linguagem de programação P ′ ′ . Knuth (1969) menciona o caso especial de k = 10, e Salomaa (1973) discute os casos k ≥ 2. Forslund (1995) parece ser outra redescoberta, e hipotetiza que se os antigos sistemas de numeração usassem o bijetivo de base k , eles poderiam não ser reconhecido como tal em documentos arqueológicos, devido ao desconhecimento geral deste sistema.
Notas
Referências
- Böhm, C. (julho de 1964), "On a family of Turing machines and the related programming language", ICC Bulletin , 3 : 191.
- Forslund, Robert R. (1995), "Uma alternativa lógica ao sistema de número posicional existente", Southwest Journal of Pure and Applied Mathematics , 1 : 27-29, MR 1386376 , S2CID 19010664.
- Foster, JE (1947), "A number system without a zero symbol", Mathematics Magazine , 21 (1): 39-41, doi : 10.2307 / 3029479 , JSTOR 3029479.
- Knuth, DE (1969), The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (1st ed.), Addison-Wesley, Solution to Exercise 4.1-24, p. 195. (Discute a base 10 do bijetivo.)
- Salomaa, A. (1973), Formal Languages , Academic Press, Nota 9.1, pp. 90-91. (Discute a base do bijetivo- k para todo k ≥ 2.)
- Smullyan, R. (1961), "9. Ordenação Lexicográfica; representação n -adica de inteiros" , Teoria dos Sistemas Formais , Annals of Mathematics Studies, 47 , Princeton University Press, pp. 34-36.