How to represent a decimal number into a binary expression of a different radix/base

Question

Dear Math community,

A good way to ask my question is to simply illustrate this with an example.

Let's have a binary representation of the first 16 numbers {0-15}
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

Now, converting a decimal number $ (X)_{10} $ to a binary expression $ (X)_{2} $ such as demonstrated above is fairly easy as every number can be representated in such a way:

$$ (0000)_2 = 0, (0001)_2 = 1, ..., (1110)_2 = 14, (1111)_2 = 15 $$

Let's use the same binary representation, but now with a different base:

$$ (0000)_3 = 0, (0001)_3 = 1, ..., (1110)_3 = 39, (1111)_3 = 40 $$ $$ (0000)_4 = 0, (0001)_4 = 1, ..., (1110)_4 = 84, (1111)_4 = 85 $$ $$ (0000)_8 = 0, (0001)_8 = 1, ..., (1110)_8 = 584, (1111)_8 = 585 $$ $$ (0000)_9 = 0, (0001)_9 = 1, ..., (1110)_9 = 819, (1111)_9 = 820 $$

Not every number can be represented in such a way, but what would be the most efficient way to find out:

• Can a decimal number $(X)$ be expressed in the form of $(0,1)$ using a certain radix/base $(B)$ where $X \neq B$ and $B \neq 2$ ?
• If so, are there multiple bases? Is there a way to find all of them?

So, given an arbitrary number what is its binary representation using a base other than 2?
Example: $ 39339_{10} = (1011)_{34} $

I've asked a similar question ca. 5 years ago, but the answers didn't fit every situation and aren't quite fitting for this case as well. (How to find the highest [natural] radix base of a given number with a natural output)

So any input on this would be highly appreciated.

Thank you.

Edit:

To be clear, the point of this is not to just simply convert a decimal into a binary representation, but to find out, through some mathematical property of distinct proof the potential bases that could be used given an arbitrary integer for some binary representation of it.

Any (huge) brute-force approach deviates from the core of the question as that you could simply imagine how inefficient it would be to apply this using big integers. The underlying essence of this is to explore and apply some intrinsic method/mathematical way of doing so.

Polynomials seem to be a promising route though.

Answer 1

Not yet an answer, but a comment/an idea how to begin

---

Hmm, if $x$ is your number, then the representation in base $b$ using only digits $(0,1)$ means you can write $$ x = b^{j_1} { b^{k_1}-1 \over b-1 } + b^{j_1} { b^{k_1}-1 \over b-1 } + ... b^{j_n} { b^{k_n}-1 \over b-1 } \tag 1 $$ Here the $k_1,k_2,...,k_n$ give lenghtes of consecutive $1$ in your radix-system, while the differences between the $j_1,j_2,...,j_n$ the lengthes of consecutive $0$ .

And then "normalizing": $$ x \cdot (b-1) = b^{j_1} ( b^{k_1}-1 ) + b^{j_2} ( b^{k_2}-1) + ... b^{j_n} ( b^{k_n}-1 ) \tag 2 $$ and put in a (so-to-say) "iterated factoring": $$ x \cdot (b-1) = (...(( ( b^{k_1}-1 )b^{j'_1} + ( b^{k_1}-1))b^{j'_2} + ... +( b^{k_n}-1 )) b^{j'_n} \tag 3 $$ where $j'_{n-1}=j_{n-1}-j_n$ and so on.

From this you try to develop $x(b-1)$ backwards with modular arithmetic:

• can you divide it by some $b^{j'_n}$, then do it, to get $x_1$
• after that is it of the form $x_2 \cdot b^{j'_{n-1}} + (b^{k_n}-1)$?
• ...
  and repeat as long as possible/meaningful.

---

Disclaimer: This is at the moment just handwaving, so not meant as complete answer.

Answer 2

The problem is to determine the integers $n\ge0$ that can be represented in the form

$$n=\sum\limits_{i=0}^{\max\left(\log_m(n),0\right)}b_i\ m^i\tag{1}$$

where $b_i\in\{0,1\}$ and $m$ is the base.

---

There are two questions to be addressed:

1. Can an integer $n\ge 0$ be expressed in the form of formula (1) above where $b_i\in\{0,1\}$ and $m$ is the base, and where $n\neq m$ and $m\neq 2$?
2. If so, are there multiple bases? Is there a way to find all of them?

---

Question (1) is simpler and answered further below with the algorithms baseRepresentationQ(n,m) and findBaseRepresentation(n,m) which loop over powers of $m$, and the algorithm getKthBaseRepresentation(k,m) which loops over the bits of $k$. All three of these algorithms are of trivial complexity and capable of handling fairly large integer values of $n$.

---

Question (2) is a bit more complicated. A necessary but not sufficient condition for $n>1$ to be expressible in base $m$ per formula (1) above is either $m|n$ or $m|(n-1)$. Therefore all base $m$ representations of $n$ can be found by factoring both $n$ and $n-1$ and then trying all divisors of both $n$ and $n-1$ as the base $m$.

There are more efficient factoring methods than brute force (see Integer factorization), but factoring large integers is far from trivial. The RSA cryptosystem is based on the difficulty of factoring large integers.

---

In OP's question above, the OP excluded the base $m=2$ since all integer values of $n$ can be represented in the form of formula (1) above for $m=2$, and also excluded the trivial case $m=n$ ($n=10_{\ n}$), but there are also the trivial cases $n=0$ ($0=0_m$), $n=1$ ($1=1_m$), and $m=n-1$ ($n=11_{\ n-1}$).

---

The remainder of this answer defines algorithms that address and resolve question (1) above.

---

Here's an algorithm that returns True if an integer $n\ge0$ can be represented in the form of formula (1) above where $b_i\in\{0,1\}$ and $m$ is the base. The algorithm below is written in the Wolfram/Mathematica language with some comments of the form (* comment *) to help clarify the algorithm and syntax.

---

baseRepresentationQ[n_,m_]:=Block[

{basePower=m^Floor[Max[Log[m,n],0]],y=n}, (* initialize local variables *)

While[basePower>=1,

If[y>=basePower,y=y-basePower]; (* If y>=basePower Then y=y-basePower *)

basePower=basePower/m];

If[y==0,True,False]]

---

Here's a slightly more complicated algorithm that returns the $b_i\in\{0,1\}$ values associated with formula (1) above if an integer $n\ge0$ can be represented in the form of formula (1) where $m$ is the base.

---

findBaseRepresentation[n_,m_]:=Block[

{basePower=m^Floor[Max[Log[m,n],0]],y=n,outList={}}, (* initialize local variables *)

While[basePower>=1,

If[y>=basePower,y=y-basePower;b=1,b=0]; (* If y>=basePower Then {y=y-basePower;b=1} Else b=0 *)

outList=AppendTo[outList,b]; (* add bit to outList *)

basePower=basePower/m];

If[y==0,outList,{"Remainder",y}]]

---

Here's a table of output values for the base $m=2$ where every integer $n\ge 0$ has a representation.

---

$\begin{array}{ccc} n & \text{findBaseRepresentation[n,2]} & \text{baseRepresentationQ[n,2]} \\ 0 & \{0\} & \text{True} \\ 1 & \{1\} & \text{True} \\ 2 & \{1,0\} & \text{True} \\ 3 & \{1,1\} & \text{True} \\ 4 & \{1,0,0\} & \text{True} \\ 5 & \{1,0,1\} & \text{True} \\ 6 & \{1,1,0\} & \text{True} \\ 7 & \{1,1,1\} & \text{True} \\ 8 & \{1,0,0,0\} & \text{True} \\ 9 & \{1,0,0,1\} & \text{True} \\ 10 & \{1,0,1,0\} & \text{True} \\ 11 & \{1,0,1,1\} & \text{True} \\ 12 & \{1,1,0,0\} & \text{True} \\ 13 & \{1,1,0,1\} & \text{True} \\ 14 & \{1,1,1,0\} & \text{True} \\ 15 & \{1,1,1,1\} & \text{True} \\ 16 & \{1,0,0,0,0\} & \text{True} \\ 17 & \{1,0,0,0,1\} & \text{True} \\ 18 & \{1,0,0,1,0\} & \text{True} \\ 19 & \{1,0,0,1,1\} & \text{True} \\ 20 & \{1,0,1,0,0\} & \text{True} \\ 21 & \{1,0,1,0,1\} & \text{True} \\ 22 & \{1,0,1,1,0\} & \text{True} \\ 23 & \{1,0,1,1,1\} & \text{True} \\ 24 & \{1,1,0,0,0\} & \text{True} \\ 25 & \{1,1,0,0,1\} & \text{True} \\ 26 & \{1,1,0,1,0\} & \text{True} \\ 27 & \{1,1,0,1,1\} & \text{True} \\ 28 & \{1,1,1,0,0\} & \text{True} \\ 29 & \{1,1,1,0,1\} & \text{True} \\ 30 & \{1,1,1,1,0\} & \text{True} \\ 31 & \{1,1,1,1,1\} & \text{True} \\ 32 & \{1,0,0,0,0,0\} & \text{True} \\ \end{array}$

---

Here's a table of output values for the base $m=3$ where only a subset of integers $n\ge 0$ have a representation. Note the integers $n\ge 0$ that have a representation cover all possible bit patterns 0, 1, 10, 11, 100, 101 etc.

---

$\begin{array}{ccc} n & \text{findBaseRepresentation[n,3]} & \text{baseRepresentationQ[n,3]} \\ 0 & \{0\} & \text{True} \\ 1 & \{1\} & \text{True} \\ 2 & \{\text{Remainder},1\} & \text{False} \\ 3 & \{1,0\} & \text{True} \\ 4 & \{1,1\} & \text{True} \\ 5 & \{\text{Remainder},1\} & \text{False} \\ 6 & \{\text{Remainder},2\} & \text{False} \\ 7 & \{\text{Remainder},3\} & \text{False} \\ 8 & \{\text{Remainder},4\} & \text{False} \\ 9 & \{1,0,0\} & \text{True} \\ 10 & \{1,0,1\} & \text{True} \\ 11 & \{\text{Remainder},1\} & \text{False} \\ 12 & \{1,1,0\} & \text{True} \\ 13 & \{1,1,1\} & \text{True} \\ 14 & \{\text{Remainder},1\} & \text{False} \\ 15 & \{\text{Remainder},2\} & \text{False} \\ 16 & \{\text{Remainder},3\} & \text{False} \\ 17 & \{\text{Remainder},4\} & \text{False} \\ 18 & \{\text{Remainder},5\} & \text{False} \\ 19 & \{\text{Remainder},6\} & \text{False} \\ 20 & \{\text{Remainder},7\} & \text{False} \\ 21 & \{\text{Remainder},8\} & \text{False} \\ 22 & \{\text{Remainder},9\} & \text{False} \\ 23 & \{\text{Remainder},10\} & \text{False} \\ 24 & \{\text{Remainder},11\} & \text{False} \\ 25 & \{\text{Remainder},12\} & \text{False} \\ 26 & \{\text{Remainder},13\} & \text{False} \\ 27 & \{1,0,0,0\} & \text{True} \\ 28 & \{1,0,0,1\} & \text{True} \\ 29 & \{\text{Remainder},1\} & \text{False} \\ 30 & \{1,0,1,0\} & \text{True} \\ 31 & \{1,0,1,1\} & \text{True} \\ 32 & \{\text{Remainder},1\} & \text{False} \\ 33 & \{\text{Remainder},2\} & \text{False} \\ 34 & \{\text{Remainder},3\} & \text{False} \\ 35 & \{\text{Remainder},4\} & \text{False} \\ 36 & \{1,1,0,0\} & \text{True} \\ 37 & \{1,1,0,1\} & \text{True} \\ 38 & \{\text{Remainder},1\} & \text{False} \\ 39 & \{1,1,1,0\} & \text{True} \\ 40 & \{1,1,1,1\} & \text{True} \\ 41 & \{\text{Remainder},1\} & \text{False} \\ 42 & \{\text{Remainder},2\} & \text{False} \\ 43 & \{\text{Remainder},3\} & \text{False} \\ 44 & \{\text{Remainder},4\} & \text{False} \\ 45 & \{\text{Remainder},5\} & \text{False} \\ 46 & \{\text{Remainder},6\} & \text{False} \\ 47 & \{\text{Remainder},7\} & \text{False} \\ 48 & \{\text{Remainder},8\} & \text{False} \\ 49 & \{\text{Remainder},9\} & \text{False} \\ 50 & \{\text{Remainder},10\} & \text{False} \\ 51 & \{\text{Remainder},11\} & \text{False} \\ 52 & \{\text{Remainder},12\} & \text{False} \\ 53 & \{\text{Remainder},13\} & \text{False} \\ 54 & \{\text{Remainder},14\} & \text{False} \\ 55 & \{\text{Remainder},15\} & \text{False} \\ 56 & \{\text{Remainder},16\} & \text{False} \\ 57 & \{\text{Remainder},17\} & \text{False} \\ 58 & \{\text{Remainder},18\} & \text{False} \\ 59 & \{\text{Remainder},19\} & \text{False} \\ 60 & \{\text{Remainder},20\} & \text{False} \\ 61 & \{\text{Remainder},21\} & \text{False} \\ 62 & \{\text{Remainder},22\} & \text{False} \\ 63 & \{\text{Remainder},23\} & \text{False} \\ 64 & \{\text{Remainder},24\} & \text{False} \\ 65 & \{\text{Remainder},25\} & \text{False} \\ 66 & \{\text{Remainder},26\} & \text{False} \\ 67 & \{\text{Remainder},27\} & \text{False} \\ 68 & \{\text{Remainder},28\} & \text{False} \\ 69 & \{\text{Remainder},29\} & \text{False} \\ 70 & \{\text{Remainder},30\} & \text{False} \\ 71 & \{\text{Remainder},31\} & \text{False} \\ 72 & \{\text{Remainder},32\} & \text{False} \\ 73 & \{\text{Remainder},33\} & \text{False} \\ 74 & \{\text{Remainder},34\} & \text{False} \\ 75 & \{\text{Remainder},35\} & \text{False} \\ 76 & \{\text{Remainder},36\} & \text{False} \\ 77 & \{\text{Remainder},37\} & \text{False} \\ 78 & \{\text{Remainder},38\} & \text{False} \\ 79 & \{\text{Remainder},39\} & \text{False} \\ 80 & \{\text{Remainder},40\} & \text{False} \\ 81 & \{1,0,0,0,0\} & \text{True} \\ \end{array}$

---

Another way to look at it is here's a table of integers $n\ge 0$ that have a representation for the base $m=3$ consistent with formula (1) above where $b_i\in\{0,1\}$.

---

$\begin{array}{ccc} n & \text{findBaseRepresentation[n,3]} & \text{baseRepresentationQ[n,3]} \\ 0 & \{0\} & \text{True} \\ 1 & \{1\} & \text{True} \\ 3 & \{1,0\} & \text{True} \\ 4 & \{1,1\} & \text{True} \\ 9 & \{1,0,0\} & \text{True} \\ 10 & \{1,0,1\} & \text{True} \\ 12 & \{1,1,0\} & \text{True} \\ 13 & \{1,1,1\} & \text{True} \\ 27 & \{1,0,0,0\} & \text{True} \\ 28 & \{1,0,0,1\} & \text{True} \\ 30 & \{1,0,1,0\} & \text{True} \\ 31 & \{1,0,1,1\} & \text{True} \\ 36 & \{1,1,0,0\} & \text{True} \\ 37 & \{1,1,0,1\} & \text{True} \\ 39 & \{1,1,1,0\} & \text{True} \\ 40 & \{1,1,1,1\} & \text{True} \\ 81 & \{1,0,0,0,0\} & \text{True} \\ \end{array}$

---

Here's a python version of the algorithm baseRepresentationQ(n,m) along with some test code for the base $m=3$.

---

import math

def baseRepresentationQ(n,m):

# declare and define local variables

y="local"

basePower="local"

y=n

if n>1:
    
    basePower=m**math.floor(math.log(n,m))
    
else:
    
    basePower=1
    
# loop through the powers of the base m

while basePower>=1:
    
    if y>=basePower:
    
        y=y-basePower
        
    basePower=basePower/m
    
return y==0

for x in range(82):

if baseRepresentationQ(x,3):
    
    print(x)

---

Here's the output of the python code version of the algorithm baseRepresentationQ(n,m) above which is consistent with the last table above generated by the Mathematica version of the algorithm.

---

0 1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 81

---

Here's a python version of the algorithm getBaseRepresentation(n,m) along with some test code for the base $m=3$.

---

import math

def getBaseRepresentation(n,m):

# declare and define local variables

y="local"

basePower="local"

b="local"

bitList="local"

retVal="local"

y=n

if n>1:
    
    basePower=m**math.floor(math.log(n,m))
    
else:
    
    basePower=1
    
bitList=[]

# loop through the powers of the base m

while basePower>=1:
    
    if y>=basePower:
        
        y=y-basePower
        
        b=1
        
    else:
        
        b=0
                
    basePower=basePower/m
    
    bitList.append(b)
    
if y==0:
    
    retVal=bitList
    
else:
    
    retVal=y
    
return retVal

for x in range(82):

print(x,getBaseRepresentation(x,3))

---

Here's a python version of an algorithm getKthBaseRepresentation(k,m) along with some test code for the base $m=3$. This algorithm returns the $k^{th}$ integer $n$ (and the bits of it's binary representation to the base $m$ where counting starts at $k=0$) which can be represented in the form of formula (1) above where $b\in\{0,1\}$.

---

import math

def getKthBaseRepresentation(k,m):

# declare and define local variables

y="local"

n="local"

basePower="local"

b="local"

bitList="local"

retVal="local"

y=k

n=0

basePower=1
    
bitList=[]

retVal=[]

if y==0:

    bitList.append(0)
    
# loop through the bits of y

while y>=1:
    
    if y&1==1:
        
        n=n+basePower
        
        b=1
        
    else:
        
        b=0
    
    basePower=basePower*m
    
    bitList.insert(0, b)
    
    if y!=0:
        
        y=y>>1
        
    else:
        
        y=-1
            
retVal.append(n)

retVal.append(bitList)

return retVal

for k in range(17):

print(k,getKthBaseRepresentation(k,3))

---

Here's the output of the python code version of the algorithm getKthBaseRepresentation(k,m) and test code above for the base $m=3$ which is consistent with the last table above generated by the Mathematica version of the getBaseRepresentation(n,m) algorithm.

---

k [n, [bitList]]
0 [0, [0]]
1 [1, 1]
2 [3, [1, 0]]
3 [4, [1, 1]]
4 [9, [1, 0, 0]]
5 [10, [1, 0, 1]]
6 [12, [1, 1, 0]]
7 [13, [1, 1, 1]]
8 [27, [1, 0, 0, 0]]
9 [28, [1, 0, 0, 1]]
10 [30, [1, 0, 1, 0]]
11 [31, [1, 0, 1, 1]]
12 [36, [1, 1, 0, 0]]
13 [37, [1, 1, 0, 1]]
14 [39, [1, 1, 1, 0]]
15 [40, [1, 1, 1, 1]]
16 [81, [1, 0, 0, 0, 0]]

Answer 3

First note that every positive integer $X$ has at least three bases $B$ in which all of its digits are $0$'s or $1$'s. You already exclude the two bases $B=X$ and $B=2$, where we have $(X)_B=10$. The third base is $B=X-1$, for which we have $(X)_B=11$.

If the final digit of $(X)_B$ is a $0$ then $B$ is a divisor of $X$, and so $\tfrac{X}{B}$ is again an integer, and all digits of $(\tfrac XB)_B$ are again $0$'s and $1$'s. Similarly, if the final digit of $(X)_B$ is a $1$ then $B$ is a divisor of $X-1$, and so $\tfrac{X-1}{B}$ is again an integer, and all digits of $(\tfrac{X-1}B)_B$ are again $0$'s and $1$'s. In both cases, we obtain $(\tfrac XB)_B$ and $(\tfrac{X-1}B)_B$ by 'chopping off' the last digit of $(X)_B$.

This suggests a method to determine every base $B$ for which $(X)_B$ consists of all $0$'s and $1$'s:

1. Set $X_0:=X$ or $X_0:=X-1$. Factor $X_0$ and let $\mathcal{B}$ denote the set of (positive) divisors of $X_0$.
2. For each base $B\in\mathcal{B}$: Start with $i=0$. Then:
3. Repeatedly divide $X_i$ by $B$ as often as possible, to find $Y_i$ and $m_i$ such that $X_i=B^{m_i}Y_i$ where $B$ does not divide $Y_i$. Set $X_{i+1}:=Y_i-1$. If $X_{i+1}=0$ we are done; $X_0$ has such a representation in base $B$. Else if $m_i=0$ we are done; $X_0$ has no such representation in base $B$. Else, repeat this step.

Of course factoring $X$ and $X-1$ may be nontrivial. But given two lists of positive divisors $D$ and $D'$ of $X$ and $X-1$, respectively, one can quickly determine all such bases $B$. The following snippet of Python code should do the trick:

def check_base(X_0, B):
    while X_0 > 0:
        if X_0 % B == 0: 
            X_0 = X_0 // B
        elif X_0 % B == 1:
            X_0 = X_0 - 1
        else:
            return 0
    return 1


X = # Your favorite number.
D = positive_divisors(X)
for B in D:
    X_0 = X
    if check_base(X_0, B):
        print(X_0, " looks binary in base ", B)

Do be sure not to include $1\in D$ as in this case the code will not terminate. You could of course add another condition in check_base to catch this.