# Sistemas de numeración
Un sistema de numeración es un conjunto de reglas y símbolos que permiten construir números (al menos los números naturales y el $0$).

Los sistemas de numeración se pueden clasificar en dos tipos:
- Sistemas de numeración posicionales (por ejemplo el decimal, binario, hexadecimal, mesopótamico, etc).
- Sistemas de numeración no posicionales (por ejemplo el romano).

En estas notas de clase sólo veremos los sistemas de numeración posicionales.

## Sistemas de numeración posicionales
Un sistema de númeración posicional base $b$, es aquel que utiliza los símbolos ${0, 1, 2, \dots, b-1}$, también llamados dígitos. Un número $n$ ($n \in \mathbb{N} \cup \{0\}$) se representa con una secuencia de dígitos $a_{k-1}a_{k-2}a_{k-3}\dots a_0$, tal que:

$$
n=a_{k-1}b^{k-1}+a_{k-2}b^{k-2}+a_{k-3}b^{k-3}+\dots+a_1b+a_0
$$

y $a_{k-1} \neq 0$ si $n \neq 0$.

Para distinguir las bases distintas de $10$, se suele colocar la base como subindice al final de la representación base $b$ de ese número: $a_{k-1}a_{k-2}a_{k-3}\dots a_0~_b$. Si no tiene subíndice indicando la base y no se especifica la base del número por otro medio, se asume que es base $10$.

Para facilitar la representación, las bases mayores a $10$ y menores a $37$ utilizan letras mayúsculas para representar los símbolos mayores o igual a $10$ en orden alfabético: $A, B, C, \dots, Z$. Para bases mayores a $37$, se puede usar la representación decimal de los símbolos y se separan con comas.

:::info
:information_source: **Ejemplo 1**
- Si $n=503$ y $b=10$, entonces $n=503_{10}$ ya que $503=5\cdot 10^2+0\cdot 10^1+3\cdot 10^0$.
- Si $n=23$ y $b=2$, entonces $n=10111_2$, ya que $23=1\cdot 2^4+0\cdot10^3+1\cdot10^2+1\cdot10^1+1\cdot10^0$.
- Si $n=348$ y $b=16$, entonces $n=15C_{16}$, ya que $348=1\cdot 16^2+5\cdot16^1+12\cdot16^0$.
- Si $n=94523$ y $b=200$, entonces $n=(2,72,123)_{200}$, ya que $94523=2\cdot 200^2+72\cdot200^1+23\cdot200^0$.
:::

### Representación única
Para toda base $b$ ($b \geq 2$), existe una representación única en dicha base.

:::spoiler Demostración
Primero veamos que se cumple para todos los números $n$ menores a $b$. En este caso, $n=a_0$.

Ahora supongamos que se cumple para todos los $n < b^k$, y demostremos por inducción que se cumple para $b^k \leq n < b^{k+1}$.

Para $n$ en $[b^k,b^{k+1})$ tenemos que:

$$
\begin{align}
n &= a_0 + a_1b + a_2b^2 + \dots a_kb^k \\
&= a_0 + b(a_1 + a_2b + \dots a_kb^{k-1}) \\
&= a_0 + b \cdot q
\end{align}
$$

Notemos que $n$ es un número de la forma $a_0+bq$, con $0 \leq a_0 < b$. Como consecuencia del algoritmo de la división, $a_0$ está determinado de forma única y es igual a $n \% b$.

De la expresión de arriba tenemos que:
$$
\begin{align}
\frac{n - a_0}{b}=a_1+a_2b+a_3b^2+\dots+a_kb^{k-1}
\end{align}
$$

Y como $\frac{n - a_0}{b}<b^k$, entonces tiene una representación única en base $b$. Por lo tanto, $n \in [b^k,b^{k+1})$ tiene una representación única, donde $a_0$ es su dígito menos significativo, y sus otros dígitos son los mismos que $\frac{n - a_0}{b}$ en el mismo orden.
:::

### Obteniendo la representación base $b$ de un número
Si queremos obtener la representación en base $b$ de un número $n$, podemos utilizar las propiedades vistas en la demostración de la representación única. Primero podemos observar que el dígito menos significato, es decir $a_0$, es igual a $n \% b$. Una vez que tenemos el primer dígito, continuamos con $\frac{n-a_0}{b}=\lfloor\frac{n}{b}\rfloor$. Obtenemos el primer dígito de $\frac{n-a_0}{b}$, y se repite el mismo proceso hasta llegar a $0$.

El código para obtener la representación en vase $b$ es la siguiente:

// Regresa un vector con los dígitos de n en base b
vector<int> n_to_base_b (int n, int b) {
    vector<int> base_b;
    while (n > 0) {
        base_b.push_back(n % b);
        n /= b;
    }
    if (!base_b.size())
        return {0};
    return base_b;
}

En algunos casos es más fácil tener un `string` que contenga la representación en lugar de un vector. Por ejemplo, si queremos obtener la representación binaria en un `string` con carácteres `0` y `1`, lo podemos hacer así:

string n_to_binary (int n) {
    vector<int> base_b = n_to_base_b(n, 2);
    string res;
    
    for (int i = (int)base_b.size() - 1; i >= 0; i--)
        res.push_back('0' + base_b[i]);
    return res;
}

El código de arriba regresa un string donde el dígito binario más significativo está en la posición $0$. Esto es conveniente si quieremos imprimir la representación en binario para que el dígito más significativo esté del lado izquierdo.

### Obtener $n$ dada su representación en base $b$.
Ahora queremos el inverso de la función anterior. Dada la representación base $b$ de un número, obtener su valor númerico. La implementación es simple:

int base_b_to_n (const vector<int> &base_b, int b) {
    int n = 0, power_of_b = 1;
    for (int d : base_b) {
        n += d * power_of_b;
        power_of_b *= b;
    }
    return n;
}

El código tendría que ser diferente si la representación base $b$ está contenida en un `string`. Queda como un ejercicio implementar ese código.

## Sistema numérico no posicional
Cualquier otro sistema numérico que no entra en la definición de posicional, como por ejemplo el sistema de numeración romano. Estos sistemas no son comunes en problemas de programación competitiva, por lo que no se verán en estas notas.