4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I will illustrate the only approach I know of by considering whether $39339_{(10)}$ has a satisfactory expression in base $(34)$. Compute the digits left to right, and manually check if any of the digits are $> 1$. Here, since $(34)^4 > 39339 \geq (34)^3$, you know that the base $(34)$ representation will have exactly $4$ digits. ...see next comment $\endgroup$ Commented Aug 5, 2021 at 11:15
  • $\begingroup$ Denote these digits as $d_3, d_2, d_1, d_0$, reading left to right. Let $S_3 = 39339.$ Then $\displaystyle d_3 = \left\lfloor \frac{S_3}{(34)^3}\right\rfloor.$ Then, iteratively, for $k \in \{2,1,0\}$, you have that $S_k = S_{k+1} - d_{(k+1)}(34)^{(k+1)}.$ Then, $\displaystyle d_k = \left\lfloor \frac{S_k}{(34)^k}\right\rfloor.$ So, going through the algorithm, you simply stop if any of $d_3, d_2, d_1, d_0$ are $> 1$. $\endgroup$ Commented Aug 5, 2021 at 11:15
  • 2
    $\begingroup$ As far as finding all of the bases for a specific positive integer $(n)$ to be converted, you know that in general, the base will have to be $\leq (n)$ and that both base $(n)$ and base $(n-1)$ will work. The only shortcut that I know of is that (for example) if base $b$ gives a satisfactory representation, and if (also) there exists a $k \in \Bbb{Z_{\geq 2}}$ such that $b = c^k$, then there will also be a satisfactory representation in base $c$. $\endgroup$ Commented Aug 5, 2021 at 11:23
  • $\begingroup$ @user2661923 First of all, thanks for commenting. But just to be clear, the base 34 was just an example and thus using the number 34 for a calculation would not suffice. It was about finding the base where the number X could be represented by in binary expression and thus not 'knowing' of any arbitrary base to begin with, perhaps a way to find an estimate? Like your 3th comment 'if base b gives a satifactory representation', how to find that specific base? $\endgroup$ Commented Aug 5, 2021 at 11:36
  • $\begingroup$ I was using base = $(34)$ to illustrate the general procedure for determining if any specific base $b$ will result in a satisfactory expression. Thus, given the number $n$, and the base $b$, first find $k$ such that $b^{k+1} > n \geq b^k$. Then, construe the left to right digit expression to be $d_k, \cdots, d_0$. Then, let $S_k$ represent $n$, and follow the outlined procedure, stopping if any of $d_k, \cdots, d_0$ are seen to be $> 1$. So, in general, the only way that I know of, for checking a specific base $b$ is to manually compute the corresponding digits $d_k, \cdots, d_0$. $\endgroup$ Commented Aug 5, 2021 at 11:42

3 Answers 3

Reset to default
1
$\begingroup$

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]]

$\endgroup$
6
  • $\begingroup$ Hi, thanks for answering. I don't have Wolfram Mathematica installed or used it before, but looking at the 'code' you've posted it seems that you're looping through potential outcomes. If you've read my related question I've already done something similar to test the theory out but as stated it is not what I'm asking for. Take for example a 100 digit long number, looping through it isn't efficient. Or am I mistaken in your approach? If so, would you mind posting this in python or anything alike? But the point is for finding it through more mathematical approach rather than programmatic.thx $\endgroup$ Commented Aug 11, 2021 at 10:30
  • $\begingroup$ @Eli I defined three functions above including getBaseRepresentation(n,m), baseRepresentationQ(n,m), and getKthBaseRepresentation(k,m) where the first two functions loop through the powers of $m$ and the third function loops through the bits of $k$. I gave Mathematica and python implementations of the first two functions and a python implementation of the third function. I don't think any of these implementations can be improved upon significantly. $\endgroup$ Commented Aug 12, 2021 at 2:24
  • $\begingroup$ @Eli The third function getKthBaseRepresentation(k,m) illustrates it's not necessary to loop through every possible outcome as the the $k^{th}$ value of $n$ that can be represented in the form of formula (1) for base $m$ can be directly computed from the binary representation of $k$. Therefore I believe my answer resolves your question. $\endgroup$ Commented Aug 12, 2021 at 2:24
  • $\begingroup$ I think you're missing the crucial part of my question of finding the base not passing it through as an argument with getKthBaseReperesention. As my question states given X what are the potential bases that could be used to still represent it in a form of (0,1). Any brute force approach will not do. (as the question states "what would be the most effecient way to find out") . 82 is a small number, its use is for big numbers as well as not trying to iterate over every base. $\endgroup$ Commented Aug 13, 2021 at 0:15
  • $\begingroup$ @Eli I answered the first part of your question "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$ ?" with the algorithms getBaseRepresentation(n,m) and baseRepresentationQ(n,m). $\endgroup$ Commented Aug 13, 2021 at 2:03
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.