A. Basic Vocabulary
We assume WLOG that $$$b_1>b_2$$$. The number of digits in the base-$$$b_1$$$ representation of $$$n$$$ is therefore not greater than that in base-$$$b_2$$$. Hence, if a solution exists, $$$(n)_{b_1}$$$ must be a prefix of $$$(n)_{b_2}$$$. Here $$$(x)_b$$$ represents the base-$$$b$$$ representation of the integer $$$x$$$.
Let's start off by observing that any number $$$n$$$ when represented in base $$$b$$$, where $$$2b>n$$$ is of the form $$$[1,n-b]_b$$$. Considering $$$2b_1>n$$$, what must be the constraint on $$$b_2$$$ for $$$(n)_{b_1}$$$ to be a prefix?
Let $$$n-b_1=x$$$, then $$$n=[1,x]_{b_1}$$$. Note that $$$x>0$$$ since $$$b_1<n$$$.
Thus we have,
Thus, $$$(b_2+x)$$$ is the quotient obtained on dividing $$$n$$$ by $$$b_2^k$$$.
Now, we note that $$$1 \leq x \leq b_2-1$$$, since $$$x$$$ is a non-zero digit in base-$$$b_2$$$. Therefore,
If there exists any $$$b_2$$$, $$$k$$$ satisfying the above inequality, then we can derive $$$b_1$$$ as follows:
- $$$q \leftarrow \Big\lfloor\frac{n}{b_2^k}\Big\rfloor$$$
- $$$x \leftarrow q-b_2$$$
- $$$b_1 \leftarrow n-x$$$
We observe that the upper bound of $$$(1)$$$ strictly increases with $$$b_2$$$ for a given $$$k$$$. Therefore, it is optimal to choose the largest value of $$$b_2$$$ such that $$$(b_2+x)b_2^k \leq n$$$, which can be found in $$$\mathcal{O}(\log(\sqrt{n}))$$$ by Binary Search. Since $$$b_2 \geq 2$$$, we must test at most $$$\log_2{(n)}$$$ values of $$$k$$$.
Note that all this while, we are operating under the assumption that $$$2b_1<n$$$. Let's observe the case when $$$k=1$$$. We have,
Now, consider how we find $$$b_2$$$. We choose the largest value that satisfies the lower bound and check whether it satisfies the upper bound. What if the upper bound for a certain $$$b_2$$$ went beyond the lower bound for $$$b_2+1$$$? For visualisation, one could try imagining that for every $$$b_2$$$ there is a certain interval in which $$$n$$$ must lie for the inequality to hold. What happens when these intervals start to overlap? Then we'd be guaranteed a solution for any value of $$$n$$$.
which is true $$$\forall b_2 \geq 4$$$.
Therefore, we conclude that $$$\forall n \geq (4+1)(4)=20$$$, $$$\exists b_1,b_2$$$ such that $$$2b_1>n$$$ and $$$(1)$$$ holds for $$$k=1$$$.
Thus, we finally have our complete solution. For $$$n<20$$$ the trivial brute force algorithm is fast enough. For $$$n>20$$$, we test solely for $$$k=1$$$ as described before and report the answer obtained.
