Алгоритм и обоснование (для вещественного основания $b$ с $|b|>1$). Выделю два естественных случая: $b>1$ (включая нецелые) и $b<-1$.
Общее: будем представлять целое $N$ в виде
$$N=\sum _{k\le m}{a}_k{b}^k,a_k\in D:=\{0,1,\dots ,\lceil |b|\rceil -1\},$$ где $m$ — максимально возможная целая степень (см. ниже). Полученное разложение может быть либо конечным (остаток обнулится), либо бесконечным (обычно при иррациональном $b$).
1) Случай $b>1$.
Алгоритм.
- Если $N=0$ — выдаём цифру $0$.
- Возьмём
$$m=\max \{k\in \mathbb{Z}:b^k\le N\}.$$ - Для $k=m,m-1,\dots$ выполняем:
$$a_k=\lfloor \frac{N}{b^k}\rfloor ,N\leftarrow N-a_k{b}^k.$$ Если после шага $N=0$, останавливаемся; иначе продолжаем на следующий $k-1$.
Обоснование.
- По выбору $m$ имеем $1\le \frac{N}{b^m}<b$, поэтому
$$a_m=\lfloor \frac{N}{b^m}\rfloor \in \{1,\dots ,\lceil b\rceil -1\}\subset D.$$ - После вычитания остаётся остаток
$$r=N-a_k{b}^k<b^k,$$ поэтому следующий используемый показатель не превосходит $k-1$ (степень уменьшается хотя бы на единицу). По конструкции в любой момент сумма выписанных членов равна начальной величине $N$ и в случае остановки даёт точное конечное представление; если остановки не происходит, последовательность цифр задаёт стандартную бета‑(greedy) экспансию:
$$N=\sum _{k\le m}{a}_k{b}^k.$$
2) Случай $b<-1$.
Алгоритм (аналогично, с учётом знака степеней).
- Если $N=0$ — выдаём $0$.
- Положим
$$m=\max \{k\in \mathbb{Z}:|b{|}^k\le |N|\}.$$ - Для $k=m,m-1,\dots$ выбираем целую цифру $a_k\in D$ по правилу
$$a_k=\{\begin{array}{ll}\lfloor \frac{N}{b^k}\rfloor ,& \text{если}{b}^k>0,\\ \lceil \frac{N}{b^k}\rceil ,& \text{если}{b}^k<0,\end{array}$$ и обновляем $N\leftarrow N-a_k{b}^k$. Останавливаемся при $N=0$ либо продолжаем дальше.
Короткое обоснование правильности выбора.
- Для $b^k>0$ аналогично случаю $b>1$ имеем $1\le \frac{N}{b^k}<|b|$, потому $\lfloor N/b^k\rfloor \in D$.
- Для $b^k<0$ дробь $x=\frac{N}{b^k}$ лежит в интервале $(-|b|,-1]$. Тогда $\lceil x\rceil$ даёт целое в интервале $\{0,1,\dots ,\lceil |b|\rceil -1\}=D$. В обоих случаях выбранная цифра обеспечивает остаток
$$r=N-a_k{b}^k\text{с}|r|<|b{|}^k,$$ причём следующий индекс не превосходит $k-1$. По индукции сумма выписанных членов равна исходному $N$; алгоритм даёт корректную позиционную запись (конечную при обнулении остатка, иначе бесконечную).
Замечания.
- Выбор алфавита $D=\{0,\dots ,\lceil |b|\rceil -1\}$ стандартен и гарантирует неотрицательные цифры; можно использовать и другие системно допустимые множества цифр при соответствующей корректировке правил.
- Для некратных или иррациональных $b$ запись целого числа может быть бесконечной (это нормально — это бета‑экспансия). Для некоторых классов оснований (например, целые $b$ или некоторые алгебраические числа типа Пизо) представления конечны или периодичны.