Numeración biyectiva

Sistema de numeración en el que cada número entero no negativo puede representarse exactamente de una manera

La numeración biyectiva es cualquier sistema de numeración en el que cada número entero no negativo puede representarse de exactamente una manera utilizando una cadena finita de dígitos . El nombre se refiere a la biyección (es decir, correspondencia uno a uno) que existe en este caso entre el conjunto de números enteros no negativos y el conjunto de cadenas finitas utilizando un conjunto finito de símbolos (los "dígitos").

La mayoría de los sistemas de numeración 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, la adición de 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 sistema decimal no es biyectivo. Sin embargo, el sistema de numeración unario , con un solo dígito, es biyectivo.

Una numeración biyectiva en base k 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 numerales biyectivos son un sistema para representar números 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 utiliza el conjunto de dígitos {1, 2, ..., k } ( k ≥ 1) para representar de forma única cada número entero no negativo, de la siguiente manera:

• El entero cero está representado por la cadena vacía .
• El entero representado por la cadena de dígitos no vacía

un _n un _{n −1} ... un ₁ un ₀

es

a _n k ⁿ + a _{n −1} k ^{n −1} + ... + a ₁ k ¹ + a ₀ k ⁰ .

• La cadena de dígitos que representa el entero m > 0 es

un _n un _{n −1} ... un ₁ un ₀

dónde

${\displaystyle {\begin{aligned}a_{0}&=m-q_{0}k,&q_{0}&=f\left({\frac {m}{k}}\right)&\\a_{1}&=q_{0}-q_{1}k,&q_{1}&=f\left({\frac {q_{0}}{k}}\right)&\\a_{2}&=q_{1}-q_{2}k,&q_{2}&=f\left({\frac {q_{1}}{k}}\right)&\\&\,\,\,\vdots &&\,\,\,\vdots \\a_{n}&=q_{n-1}-0k,&q_{n}&=f\left({\frac {q_{n-1}}{k}}\right)=0\end{aligned}}}$

y

${\displaystyle f(x)=\lceil x\rceil -1,}$

${\displaystyle \lceil x\rceil }$siendo el menor entero no menor que x (la función techo ).

Por el contrario, la notación posicional estándar se puede definir con un algoritmo recursivo similar donde

${\displaystyle f(x)=\lfloor x\rfloor ,}$

Extensión a números enteros

Para la base , el sistema de numeración base biyectiva podría extenderse a números enteros negativos de la misma manera que el sistema de numeración base estándar mediante el uso de un número infinito del dígito , donde , representado como una secuencia infinita por la izquierda de dígitos . Esto se debe a que la suma de Euler ${\displaystyle k>1}$ ${\displaystyle k}$ ${\displaystyle b}$ ${\displaystyle d_{k-1}}$ ${\displaystyle f(d_{k-1})=k-1}$ ${\displaystyle \ldots d_{k-1}d_{k-1}d_{k-1}={\overline {d_{k-1}}}}$

${\displaystyle g({\overline {d_{k-1}}})=\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=-{\frac {k-1}{k-1}}=-1}$

lo que significa que

${\displaystyle g({\overline {d_{k-1}}}d_{k})=f(d_{k})\sum _{i=1}^{\infty }f(d_{k-1})k^{i}=1+\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=0}$

y para cada número positivo con numeración biyectiva la representación de dígitos se representa por . Para la base , los números negativos se representan por con , mientras que para la base , los números negativos se representan por . Esto es similar a cómo en las representaciones de dígitos con signo , todos los números enteros con representaciones de dígitos se representan como donde . Esta representación ya no es biyectiva, ya que todo el conjunto de secuencias de dígitos infinitas por la izquierda se utiliza para representar los números enteros -ádicos , de los cuales los números enteros son solo un subconjunto. ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle {\overline {d_{k-1}}}d_{k}d}$ ${\displaystyle k>2}$ ${\displaystyle n<-1}$ ${\displaystyle {\overline {d_{k-1}}}d_{i}d}$ ${\displaystyle i<k-1}$ ${\displaystyle k=2}$ ${\displaystyle n<-1}$ ${\displaystyle {\overline {d_{k}}}d}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle {\overline {d_{0}}}d}$ ${\displaystyle f(d_{0})=0}$ ${\displaystyle k}$

Propiedades de la base biyectivaanumerales

Para una base dada , ${\displaystyle k\geq 2}$

• el número de dígitos en el numeral biyectivo base k que representa un entero no negativo n es

  ${\displaystyle \lfloor \log _{k}((n+1)(k-1))\rfloor }$, ^[1] en contraste con los numerales ordinarios de base k ; si k = 1 (es decir, unario), entonces el número de dígitos es simplemente n ; ${\displaystyle \lceil \log _{k}(n+1)\rceil }$
  

• el entero no negativo más pequeño, representable en un numeral biyectivo de base k de longitud , es ${\displaystyle \ell \geq 0}$

  ${\displaystyle \mathrm {min} (\ell )={\frac {k^{\ell }-1}{k-1}}}$;

• el entero no negativo más grande, representable en un numeral biyectivo de base k de longitud , es ${\displaystyle \ell \geq 0}$

  ${\displaystyle \mathrm {max} (\ell )={\frac {k^{\ell +1}-k}{k-1}}}$, equivalente a , o ; ${\displaystyle \mathrm {max} (\ell )=k\times \mathrm {min} (\ell )}$ ${\displaystyle \mathrm {max} (\ell )=\mathrm {min} (\ell +1)-1}$

• Los numerales biyectivos en base k y ordinarios en base k para un entero no negativo n son idénticos si y solo si el numeral ordinario no contiene el dígito 0 (o, equivalentemente, el numeral biyectivo no es la cadena vacía ni contiene el dígito k ).

Para una base dada , ${\displaystyle k\geq 1}$

• Hay numerales exactamente biyectivos de base k de longitud ; ^[2] ${\displaystyle k^{\ell }}$ ${\displaystyle \ell \geq 0}$
• una lista de numerales biyectivos de base k , en orden natural de los números enteros representados, está automáticamente en orden shortlex (el más corto primero, lexicográfico dentro de cada longitud). Por lo tanto, utilizando λ para denotar la cadena vacía , los numerales de base 1, 2, 3, 8, 10, 12 y 16 son los siguientes (donde se enumeran las representaciones ordinarias para comparación):

Ejemplos

34152 (en base biyectiva 5) = 3×5 ⁴ + 4×5 ³ + 1×5 ² + 5×5 ¹ + 2×1 = 2427 (en decimal).

119A (en base biyectiva 10, donde "A" representa el valor del dígito diez) = 1×10 ³ + 1×10 ² + 9×10 ¹ + 10×1 = 1200 (en decimal).

Una lista alfabética típica con más de 26 elementos es biyectiva, utilizando el orden A, B, C...X, Y, Z, AA, AB, AC...ZX, ZY, ZZ, AAA, AAB, AAC...

El sistema biyectivo de base 10

El sistema de numeración biyectivo de base 10 es un sistema de numeración posicional de base diez que no utiliza un dígito para representar el cero , sino un dígito para representar el diez, como A.

Al igual que con el sistema 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 números enteros positivos que se representan únicamente con dígitos distintos de cero en el sistema decimal convencional (como 123) tienen la misma representación en el sistema biyectivo de base 10. Aquellos que utilizan un cero deben reescribirse, por lo que, por ejemplo, 10 se convierte en A, el 20 convencional se convierte en 1A, el 100 convencional se convierte en 9A, el 101 convencional se convierte en A1, el 302 convencional se convierte en 2A2, el 1000 convencional se convierte en 99A, el 1110 convencional se convierte en AAA, el 2010 convencional se convierte en 19AA, y así sucesivamente.

En este sistema, la suma y la multiplicación son básicamente las mismas que en el sistema decimal convencional, excepto que los acarreos se producen cuando una posición excede a diez, en lugar de cuando excede a nueve. Por lo tanto, 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 los millares) y un millar (escribe 1), para obtener el resultado 13A2 en lugar del 1402 convencional.

El sistema biyectivo de base 26

En el sistema biyectivo de base 26 se pueden utilizar las letras del alfabeto latino "A" a "Z" para representar los 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 (que comienza desde 1) comienza A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ...

Cada posición de dígito representa una potencia de veintiséis, así que, por ejemplo, el numeral WI representa el valor 23 × 26 ¹ + 9 × 26 ⁰ = 607 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 con A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA, etc. Por ejemplo, en Excel 2013, puede haber hasta 16384 columnas (2 ¹⁴ en código binario), etiquetadas de A a XFD. ^{[3] Las variantes} de malware también se nombran utilizando este sistema: por ejemplo, el primer macrovirus de Microsoft Word generalizado, Concept, se denomina formalmente WM/Concept.A, su 26.ª variante WM/Concept.Z, la 27.ª variante WM/Concept.AA, et seq. Una variante de este sistema se utiliza para nombrar estrellas variables . ^[4] Se puede aplicar a cualquier problema en el que se desee una denominación sistemática utilizando letras, al tiempo que se utilizan 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. Ejemplos tempranos son Foster (1947) para el caso k = 10, y Smullyan (1961) y Böhm (1964) para todos los k ≥ 1. Smullyan utiliza este sistema para proporcionar una numeración de Gödel de las cadenas de símbolos en un sistema lógico; Böhm utiliza 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) analiza los casos k ≥ 2. Forslund (1995) parece ser otro redescubrimiento, y plantea la hipótesis de que si los sistemas de numeración antiguos utilizaban la base biyectiva k , podrían no ser reconocidos como tales en los documentos arqueológicos, debido a la falta de familiaridad general con este sistema.

Notas

1. "¿Cuántos dígitos tiene el numeral biyectivo en base k para n?". Stackexchange . Consultado el 22 de septiembre de 2018 .
2. Forslund (1995).
3. Harvey, Greg (2013), Excel 2013 para principiantes , John Wiley & Sons, ISBN 9781118550007.
4. Hellier, Coel (2001), "Apéndice D: Nomenclatura de estrellas variables", Estrellas variables cataclísmicas: cómo y por qué varían, Praxis Books in Astronomy and Space, Springer, pág. 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", Boletín ICC , 3 : 191.
• Forslund, Robert R. (1995), "Una alternativa lógica al sistema de numeración posicional existente", Southwest Journal of Pure and Applied Mathematics , 1 : 27–29, MR  1386376, S2CID  19010664.
• Foster, JE (1947), "Un sistema numérico sin símbolo cero", Mathematics Magazine , 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 del ejercicio 4.1-24, pág. 195. (Discute la base biyectiva 10.)
• Salomaa, A. (1973), Lenguas formales , Academic Press, Nota 9.1, págs. 90–91. (Discute la base biyectiva k para todo k ≥ 2.)
• Smullyan, R. (1961), "9. Ordenamiento lexicográfico; representación n-ádica de números enteros", Theory of Formal Systems , Annals of Mathematics Studies, vol. 47, Princeton University Press, págs. 34–36.