Expansão de números naturais na base $b$

Expansão de naturais na base $b$

Números naturais são escritos normalmente como sequências de algarismos na base decimal. Por exemplo, a sequência $1056$ significa o número
\[
1\cdot 1000+0\cdot 100+5\cdot 10+6.
\]
Mais geralmente, a sequência $[a_na_{n-1}\cdots a_1a_0]$ denota o número
\[
\sum_{k=0}^n a_k\cdot 10^k.
\]

É possível fazer a mesma coisa em uma outra base $b$ assumindo que $b\geq 2$.

Assuma que $a$ e $b$ são números naturais e $b\geq 2$. Então $a$ pode ser escrito unicamente na forma
\[
a=[a_na_{n-1}\cdots a_0]_b=\sum_{k=0}^n a_kb^k
\]
onde $n\geq 0$ e $a_k\in\{0,\ldots,b-1\}$ para todo $k$.

Os números $a_k$ são chamados de algarismos de $a$ na base $b$.

Existência. Usaremos indução por $a$. Se $a\in\{0,\ldots,b-1\}$ então $a$ pode ser escrito como $[a]_b$. Assuma agora que $a\geq b$ e os números menores que $a$ podem ser escritos na base $b$. Usando o Teorema de Divisão de Euclides, escreva $a=qb+a_0$ onde $0\leq a_0\leq b-1$. Como $b\geq 2$, temos que $q<a$, e a hipótese de indução é válida para $q$. Portanto
existem $a_n,\ldots,a_1\in\{0,\ldots,b-1\}$ tais que
\[
q=[a_na_{n-1}\cdots a_1]_b=\sum_{k=1}^n a_kb^{k-1}
\]
e
\[
a=bq+a_0=b\left(\sum_{k=1}^n a_kb^{k-1}\right)+a_0=\sum_{k=0}^n a_kb^{k}=[a_na_{n-1}\cdots a_1a_0]_b
\]
Então a expressão desejada para $a$ existe.

Unicidade. Provaremos esta parte também por indução em $a$. Se $a\in\{0,\ldots,b-1\}$, então $a=[a]_b$ é a única expansão de $a$ na base $b$. Assuma que $a\geq b$ e assuma também que todo número menor que $a$ possui única expansão na base $b$. Suponha que $a$ possui duas expansões
\[
a=[a_n\cdots a_1a_0]_b=\sum_{k=0}^n a_kb^k
\]
e
\[
a=[c_m\cdots c_1c_0]_b=\sum_{k=0}^m c_kb^k.
\]
Como acima, escreva $a=qb+r$ onde $0\leq r\leq b-1$ e note que os números $q$ e $r$ são únicos. Pelas duas expressões para o número $a$ obtemos que
\[
a=\sum_{k=0}^n a_kb^k=b\cdot\left(\sum_{k=1}^n a_kb^{k-1}\right)+a_0
\]
e
\[
a=\sum_{k=0}^m c_kb^k=b\cdot\left(\sum_{k=1}^m c_kb^{k-1}\right)+c_0.
\]
Pela unicidade do resto no Teorema de Euclides, obtemos que $r=a_0=c_0$; ou seja, os últimos algarismos são determinados unicamento.

Agora,
\[
q=(a-r)/b=\sum_{k=1}^n a_kb^{k-1}=\sum_{k=1}^m c_kb^{k-1};
\]
ou seja
\[
q=[a_n\cdots a_1]_b=[c_m\cdots c_1]_b.
\]
A hipótese de indução aplica-se para o número $q$, e assim as as sequências
$[a_n\cdots a_1]_b$ e $[c_m\cdots c_1]_b$ são iguais. Portanto as duas expansões para o número $a$ são iguais como foi afirmado.

Seguindo a demonstração do teorema anterior, obtemos um algoritmo para determinar a sequência dos dígitos de um número natural em uma base $b$. Tome o número $a=168$ e seja $b=5$.

Passo 1:
\[
168=33\cdot 5+3,
\]
portanto o último algarismo de $168$ é $3$ e os demais algarismos são os algarismos de $33$.

Passo 2:
\[
33 = 6\cdot 5+3.
\]
Logo o penúltimo algarismo é $3$ e os demais algarismos são os algarismos de $6$.

Passo 3:
\[
6=1\cdot 5+1;
\]
ou seja, o seguinte algarismo é $1$ e os demais algarismos são os algarismos de $1$.

Passo 4:
\[
1=0\cdot 5+1
\]
que diz que $1=[1]_5$.

Juntando as peças, obtemos que $168=[1133]_5$.

Computação com Python

Escrevemos uma função em Python que vai realizar a computação dos algarismos para um dado natural $a$ e base $b$.

A primeira função é uma função recursiva. A ideia é a seguinte:

  1. Se $a\leq b-1$, então $a$ tem único algarismo e assim $a=[a]_b$;
  2. Caso contrário, escreva $a=qp+a_0$ onde $a_0\in\{0,\ldots,b-1\}$. O último algarismo de $a$ será $a_0$ e os demais algarismos serão os algarismos de $q$ que poderemos determinar, pois $q<a$.

def NumeroEmBaseRecursivo( a, b ):
    
    # calcular quociente e resto de a por b
    q, r = my_divmod( a, b )
    
    if q == 0:
        # se q é zero, temos único dígito
        digitos = [r]
    else:
        # caso contrário calculamos os dígitos de q
        digitos = NumeroEmBaseRecursivo( q, b )
        # adicionamos o último dígito
        digitos.append( r )
    
    return digitos

A função acima é muito elegante, mas na prática função recursiva deve ser evitada quando pode ser substituída por uma função não recursiva. A seguinte função faz a mesma computação evitando recursão.


def NumeroEmBase( a, b ):
    
    # inicializamos a lista de dígitos
    digitos = []
    
    while a != 0:
        # o dígito seguinte será o último dígito de a
        q, r = my_divmod( a, b )
        digitos.insert( 0, r )
        a = q
    
    return digitos