La numeración biyectiva es cualquier sistema numérico en el que cada número entero no negativo se puede representar exactamente de una manera utilizando una cadena finita de dígitos . El nombre deriva de esta biyección (correspondencia uno a uno) entre el conjunto de números enteros no negativos y el conjunto de cadenas finitas usando un conjunto finito de símbolos (los "dígitos").
La mayoría de los sistemas numéricos ordinarios, como el sistema decimal común , no son biyectivos porque más de una cadena de dígitos puede representar el mismo entero positivo. En particular, agregar ceros a la izquierda no cambia el valor representado, por lo que "1", "01" y "001" representan el número uno . Aunque solo el primero es habitual, el hecho de que los demás sean posibles significa que el decimal no es biyectivo. Sin embargo, unario , con un solo dígito, es biyectivo.
Una base biyectiva - k numeración es una notación posicional biyectiva . Utiliza una cadena de dígitos del conjunto {1, 2, ..., k } (donde k ≥ 1) para codificar cada entero positivo; la posición de un dígito en la cadena define su valor como un múltiplo de una potencia de k . Smullyan (1961) llama a esta notación k -ádica, pero no debe confundirse con los números p -ádicos : los números biyectivos son un sistema para representar enteros ordinarios mediante cadenas finitas de dígitos distintos de cero, mientras que los números p -ádicos son un sistema de valores matemáticos que contienen los números enteros como un subconjunto y pueden necesitar secuencias infinitas de dígitos en cualquier representación numérica.
Definición
El sistema de numeración biyectiva base- k usa el conjunto de dígitos {1, 2, ..., k } ( k ≥ 1) para representar de forma única cada entero no negativo, como sigue:
- El entero cero está representado por la cadena vacía .
- El número entero representado por la cadena de dígitos no vacía
- a n a n −1 ... a 1 a 0
- es
- una norte k norte + una norte −1 k norte −1 + ... + una 1 k 1 + una 0 k 0 .
- La cadena de dígitos que representa el entero m > 0 es
- a n a n −1 ... a 1 a 0
- dónde
- y
- siendo el menor número entero no menor que x (la función de techo ).
Por el contrario, la notación posicional estándar se puede definir con un algoritmo recursivo similar donde
Extensión a enteros
Para base , la base biyectiva-El sistema de numeración podría extenderse a números enteros negativos de la misma manera que la base estándar.sistema numérico mediante el uso de un número infinito de dígitos, dónde , representado como una secuencia de dígitos infinita a la izquierda . Esto se debe a que la suma de Euler
significa que
y por cada número positivo con representación de dígitos de numeración biyectiva está representado por . Para base, números negativos están representados por con , mientras que para la base , números negativos están representados por . Esto es similar a cómo en las representaciones de dígitos con signo , todos los enteros con representaciones de dígitos están representados como dónde . Esta representación ya no es biyectiva, ya que todo el conjunto de secuencias de dígitos infinitas a la izquierda se utiliza para representar la-ádicos enteros , de los cuales los enteros son solo un subconjunto.
Propiedades de los números k de base biyectiva
Para una base dada k ≥ 1,
- hay exactamente k n base biyectiva- k números de longitud n ≥ 0. [1]
- si k ≥ 2, el número de dígitos en la base biyectiva- k número que representa un número entero no negativo n es, [2] en contraste conpara números de base k ordinarios ; si k = 1 (es decir, unario), entonces el número de dígitos es simplemente n ;
- si k ≥ 2, los números de base biyectiva- k y base ordinaria- k para un entero no negativo n son idénticos si y solo si el número ordinario no contiene el dígito 0 (o, de manera equivalente, el número biyectivo no es ni la cadena vacía ni contiene el dígito k ).
- una lista de números de base k biyectiva , en el orden natural de los enteros representados, está automáticamente en orden shortlex (el más corto primero, lexicográfico dentro de cada longitud). Por lo tanto, usando λ para denotar la cadena vacía , los números de base 1, 2, 3, 8, 10, 12 y 16 son los siguientes (donde las representaciones ordinarias se enumeran para comparar):
base biyectiva 1: | λ | 1 | 11 | 111 | 1111 | 11111 | 111111 | 1111111 | 11111111 | 111111111 | 1111111111 | 11111111111 | 111111111111 | 1111111111111 | 11111111111111 | 111111111111111 | 1111111111111111 | ... | ( sistema de numeración unario ) | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
base biyectiva 2: | λ | 1 | 2 | 11 | 12 | 21 | 22 | 111 | 112 | 121 | 122 | 211 | 212 | 221 | 222 | 1111 | 1112 | ... | |||||||||||
binario: | 0 | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | 10000 | ... | |||||||||||
base biyectiva 3: | λ | 1 | 2 | 3 | 11 | 12 | 13 | 21 | 22 | 23 | 31 | 32 | 33 | 111 | 112 | 113 | 121 | ... | |||||||||||
ternario: | 0 | 1 | 2 | 10 | 11 | 12 | 20 | 21 | 22 | 100 | 101 | 102 | 110 | 111 | 112 | 120 | 121 | ... | |||||||||||
base biyectiva 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 biyectiva 10: | λ | 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 biyectiva 12: | λ | 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 biyectiva 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 | ... |
Ejemplos de
- 34152 (en base biyectiva-5) = 3 × 5 4 + 4 × 5 3 + 1 × 5 2 + 5 × 5 1 + 2 × 1 = 2427 (en decimal).
- 119A (en base 10 biyectiva, con "A" representando el valor de diez dígitos) = 1 × 10 3 + 1 × 10 2 + 9 × 10 1 + 10 × 1 = 1200 (en decimal).
- Una lista alfabética típica con más de 26 elementos es biyectiva, usando el orden de A, B, C ... X, Y, Z, AA, AB, AC ... ZX, ZY, ZZ, AAA, AAB, AAC. ..
El sistema bijective base-10
El sistema biyectivo de base 10 es un sistema numérico posicional de base diez que no usa un dígito para representar el cero . En su lugar, tiene un dígito para representar diez, como una .
Al igual que con el decimal convencional , cada posición de dígito representa una potencia de diez, por lo que, por ejemplo, 123 es "cien, más dos decenas, más tres unidades". Todos los enteros positivos que se representan únicamente con dígitos distintos de cero en decimal convencional (como 123) tienen la misma representación en decimal sin cero. Aquellos que usan un cero deben reescribirse, por ejemplo, 10 se convierte en A, 20 convencional se convierte en 1A, 100 convencional se convierte en 9A, 101 convencional se convierte en A1, 302 convencional se convierte en 2A2, 1000 convencional se convierte en 99A, 1110 convencional se convierte en AAA, 2010 convencional se convierte en 19AA , y así.
La suma y la multiplicación en decimal sin cero son esencialmente lo mismo que con el decimal convencional, excepto que los acarreos ocurren cuando una posición excede diez, en lugar de cuando excede nueve. Entonces, para calcular 643 + 759, hay doce unidades (escribe 2 a la derecha y lleva 1 a las decenas), diez decenas (escribe A sin necesidad de llevar a las centenas), trece centenas (escribe 3 y lleva 1 a la miles) y mil (escriba 1), para obtener el resultado 13A2 en lugar del 1402 convencional.
El sistema bijective base-26
En el sistema biyectivo base-26, se pueden usar las letras del alfabeto latino "A" a "Z" para representar los valores de 26 dígitos del uno al veintiséis . (A = 1, B = 2, C = 3, ..., Z = 26)
Con esta elección de notación, la secuencia numérica (comenzando desde 1) comienza A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB , ANTES DE CRISTO, ...
Cada posición de dígito representa una potencia de veintiséis, así que, por ejemplo, el número ABC representa el valor 1 × 26 2 + 2 × 26 1 + 3 × 26 0 = 731 en base 10.
Muchas hojas de cálculo, incluido Microsoft Excel, utilizan este sistema para asignar etiquetas a las columnas de una hoja de cálculo, comenzando por A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA , etc. Por ejemplo, en Excel 2013, puede haber hasta 16384 columnas, etiquetadas de A a XFD. [3] Se utiliza una variante de este sistema para nombrar estrellas variables . [4] Se puede aplicar a cualquier problema en el que se desee una nomenclatura sistemática mediante letras, utilizando las cadenas más cortas posibles.
Notas históricas
El hecho de que cada entero no negativo tenga una representación única en base biyectiva- k ( k ≥ 1) es un " teorema popular " que ha sido redescubierto muchas veces. Los primeros ejemplos son Foster (1947) para el caso k = 10, y Smullyan (1961) y Böhm (1964) para todo k ≥ 1. Smullyan usa este sistema para proporcionar una numeración de Gödel de las cadenas de símbolos en un sistema lógico; Böhm usa estas representaciones para realizar cálculos en el lenguaje de programación P ′ ′ . Knuth (1969) menciona el caso especial de k = 10, y Salomaa (1973) discute los casos k ≥ 2. Forslund (1995) parece ser otro redescubrimiento, y plantea la hipótesis de que si los sistemas de numeración antiguos usaran una base biyectiva- k , podrían no ser reconocidos como tales en los documentos arqueológicos, debido al desconocimiento general de este sistema.
Notas
- ^ Forslund (1995) .
- ^ "¿Cuántos dígitos hay en el numeral biyectivo base-k para n?" . Stackexchange . Consultado el 22 de septiembre de 2018 .
- ^ Harvey, Greg (2013), Excel 2013 para tontos , John Wiley & Sons, ISBN 9781118550007.
- ^ Hellier, Coel (2001), "Apéndice D: Nomenclatura de estrellas variables", Estrellas variables cataclísmicas: cómo y por qué varían , Libros de praxis en astronomía y espacio, Springer, p. 197, ISBN 9781852332112.
Referencias
- Böhm, C. (julio de 1964), "Sobre una familia de máquinas de Turing y el lenguaje de programación relacionado", ICC Bulletin , 3 : 191.
- Forslund, Robert R. (1995), "Una alternativa lógica al sistema numérico posicional existente", Southwest Journal of Pure and Applied Mathematics , 1 : 27-29, MR 1386376 , S2CID 19010664.
- Foster, JE (1947), "Un sistema numérico sin un símbolo cero", Revista de matemáticas , 21 (1): 39–41, doi : 10.2307 / 3029479 , JSTOR 3029479.
- Knuth, DE (1969), El arte de la programación informática, vol. 2: Algoritmos seminuméricos (1ª ed.), Addison-Wesley, Solución al ejercicio 4.1-24, p. 195. (Analiza la base 10 de la biyección).
- Salomaa, A. (1973), Formal Languages , Academic Press, Nota 9.1, págs. 90-91. (Analiza la base biyectiva- k para todo k ≥ 2.)
- Smullyan, R. (1961), "9. Ordenamiento lexicográfico; representación n -ádica de números enteros" , Teoría de sistemas formales , Annals of Mathematics Studies, 47 , Princeton University Press, págs. 34-36.