numeración biyectiva

Sistema numérico en el que cada número entero no negativo se puede representar exactamente de una manera.

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 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 que utilizan 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 número 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 sólo lo 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 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 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 número entero cero está representado por la cadena vacía .
• El número entero representado por la cadena de dígitos no vacía

un _{norte un} norte ₋₁ ... un ₁ un ₀

es

una _norte k ^norte + una _{norte −1} k ^{norte −1} + ... + una ₁ k ¹ + una ₀ k ⁰ .

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

un _{norte un} norte ₋₁ ... 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 número 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 de base biyectiva podría extenderse a números enteros negativos de la misma manera que el sistema de numeración de base estándar mediante el uso de un número infinito del dígito , donde , representado como una secuencia de dígitos infinita a la izquierda . 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}$

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 está representada por . Para base , los números negativos se representan con , mientras que para base , los números negativos se representan con . 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 enteros -ádicos , de los cuales los enteros son sólo 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 los números biyectivos de base k

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

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

  ${\displaystyle \lfloor \log _{k}((n+1)(k-1))\rfloor }$, ^[1] a diferencia de los números 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 número 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 número 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 números biyectivos de base k y ordinarios de base k para un entero no negativo n son idénticos si y sólo si el número ordinario no contiene el dígito 0 (o, de manera equivalente, el número biyectivo no es la cadena vacía ni contiene el dígito k ) .

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

• hay exactamente números biyectivos de base k de longitud ; ^[2] ${\displaystyle k^{\ell }}$ ${\displaystyle \ell \geq 0}$
• una lista de números biyectivos de base k , en el 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, usando λ para denotar la cadena vacía , los números en base 1, 2, 3, 8, 10, 12 y 16 son los siguientes (donde se enumeran las representaciones ordinarias para comparar):

Ejemplos

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

119A (en biyectiva base-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 y utiliza el orden de A, B, C...X, Y, Z, AA, AB, AC...ZX, ZY, ZZ, AAA, AAB, AAC. ..

El sistema biyectivo de base 10

El sistema biyectivo de base 10 es un sistema numérico posicional de base diez que no utiliza un dígito para representar el cero . En cambio , tiene un dígito para representar diez, como A.

Al igual que con el decimal convencional , la posición de cada 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 usan un cero deben reescribirse, así 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 , etcétera.

La suma y la multiplicación en este sistema son esencialmente las mismas 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 dar el resultado 13A2 en lugar del convencional 1402.

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 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 por 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í por ejemplo, el número 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 por 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 virus de macro de Microsoft Word muy extendido, Concept, se llama formalmente WM/Concept.A, su variante 26 WM/Concept.Z, la variante 27 WM/Concept. AA, y siguientes. Una variante de este sistema se utiliza para nombrar estrellas variables . ^[4] Puede aplicarse a cualquier problema en el que se desee una denominación sistemática utilizando letras, utilizando las cadenas más cortas posibles.

Notas historicas

El hecho de que cada número 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 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 utilizaran la base biyectiva k , podrían no ser reconocido como tal en los documentos arqueológicos, debido al desconocimiento general de este sistema.

Notas

1. "¿Cuántos dígitos hay en el número biyectivo de base k para n?". Intercambio de pila . 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. 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 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 biyectiva-10.)
• Salomaa, A. (1973), Lenguajes formales , Academic Press, Nota 9.1, págs. 90–91. (Se 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, vol. 47, Princeton University Press, págs. 34-36.