For a natural number $n$, let $c\_b(n)$ denote the number of digit transitions in the representation of $n$ in base $b$. By a digit transition, we mean a pair of successive, unequal digits: for instance, the decimal number 114633366 has 4 transitions, given by 14, 46, 63 and 36, hence $c\_{10}(114633366) = 4$.


Are there any known results surrounding the quantity $c\_2(n) + c\_3(n)$ (or, more generally, sums over different bases)? More specifically, I am trying to prove or disprove the following claim:


“For any $C > 0$, there exists a natural number $n$ such that, for any natural $k$ with $n \leq k \leq 2n$, $c\_2(k) + c\_3(k) > C$.”


In other words, I want to know whether it is possible to always find a number $n$ such that no number between $n$ and $2n$ has binary and ternary representations that are simultaneously nice (in the sense that they have, between them, fewer than $C$ digit transitions).


As a remark, I believe the numbers with few digit transitions in base $b$ can equivalently be described as the numbers expressible as $\sum e\_ib^i$ where $i \geq 0$, $e\_i \in \{-1, 0, 1\}$, and only few of the $e\_i$ are non-zero.


Edit: As Steven Stadnicki pointed out [below](https://mathoverflow.net/questions/377251/are-there-numbers-whose-binary-and-ternary-representations-simultaneously-have-f#comment956978_377251), this is not true for general $b$. A similar characterisation probably exists in general and is not too difficult, but I don't know if it helps.


As another remark, for a fixed number $k$ of transitions, when varying the number of digits $n$, the number of numbers with $k$ or fewer transitions is polynomial in $n$ (choose the places where the transitions happen, and the digits). The number of numbers, however, is exponential in $n$, so heuristically, one would expect the sets of numbers with few transitions in base 2 and base 3 respectively to have less and less opportunity to intersect as $n$ gets large; however, I am lacking intuition in the area, so I don't know if there is a way to make this rigorous.


My main field is not number theory, so I would be grateful for any advice of where to look for relevant results, no matter how obvious you think it is!


Update: I have checked the minimal value of $c\_2(n) + c\_3(n)$ between successive powers of 2. Between $2^i$ and $2^{i + 1}$, it is below 6 for $i \leq 22$. It then stabilises at 7 until $i = 30$ inclusive (except for $i = 25$ where it drops back to 6). It jumps to 9 for $i = 31$.



Are there numbers whose binary and ternary representations simultaneously have few digit transitions? How frequent are those numbers?
[Edited because I had misread $c\_b(k)$ to be the number of non-zero digits in the base $b$ representation, rather than the number of digit transitions. The argument works for both variants. -T]


The claim is true, and one can in fact argue by purely Archimedean methods (with the only number theoretic input being the irrationality of $\log 2 / \log 3$).


If the claim were false, then there exists $C$ such that for every power of two $n = 2^j$, there exists $2^j \leq k \leq 2^{j+1}$ such that $c\_2(k)+c\_3(k) \leq C$. In particular, for every $j$ there exists a solution to the exponential Diophantine equation


$$ e\_{j,1} (2^{j - a\_{j,1}+1}-1) + \dots + e\_{j,l} (2^{j - a\_{j,l}+1}-1) $$
$$= f\_{j,1} (3^{j^\* - b\_{j,1}+1}-1)/2 + \dots + f\_{j,m} (3^{j\_\* - b\_{j,m}+1}-1)/2 \quad (1)$$


with $j^\* := \lfloor \frac{\log 2}{\log 3} j \rfloor$, $l+m \leq C$,
$$ e\_{j,1},\dots,e\_{j,l}, f\_{j,1},\dots, f\_{j,m} = \{-2,-1,0,1,2\},$$
and
$$ O(1) = a\_{j,1} < \dots < a\_{j,l}$$
and
$$ O(1) = b\_{j,1} < \dots < b\_{j,m}$$
integers. (There are some additional constraints like $a\_{j,l} \leq j, b\_{j,m} \leq j\_\*$ that we shall simply discard. The $O(1)$ constraints are extremely explicit, for instance it would be safe to take $a\_{j,1}, b\_{j,1} \in \{-3,-2,-1,0,1,2,3\}$.)


We will show instead that the set of natural numbers $j$ for which there is a solution to (1) obeying the stated constraints in fact has natural density zero, giving the required contradiction (this is a version of the probabilistic method).


We perform the following induction. For any $l',m' \geq 1$, let $P(l',m')$ denote the claim that for any integers $a\_1,\dots,a\_{l'},b\_1,\dots,b\_{m'}$, the set of $j$ for which there is a solution to (1) obeying the stated constraints together with the additional constraints
$$ l \geq l'; m \geq m'$$
$$ a\_{j,i} = a\_i \hbox{ for } i=1,\dots,l'$$
$$ b\_{j,i} = b\_i \hbox{ for } i=1,\dots,m'$$
has natural density zero. If we can prove $P(1,1)$ then we are done by the union bound (since there are only boundedly many choices for $a\_{j,1}$ and $b\_{j,1}$). On the other hand $P(l',m')$ is vacuously true when $l'+m' > C$. So it will suffice to show that $P(l',m')$ is true whenever $P(l'+1,m'), P(l',m'+1)$ are both true.


Fix $l',m',a\_1,\dots,a\_{l'},b\_1,\dots,b\_{m'}$, and let $K$ be a large number to be chosen later. By the induction hypothesis and the union bound, the set of $j$ for which one can find a solution to (1) with the indicated constraints will have density zero if we impose either the additional constraint
$$ a\_{j,l'+1} \leq K$$
or
$$ b\_{j,m'+1} \leq K$$
(adopting the convention that $a\_{j,i}=\infty$ if $i>l$, and $b\_{j,i}=\infty$ if $i>m$). Thus we may restrict attention to those solutions which instead obey the constraints
$$ a\_{j,l'+1}, a\_{j,m'+1} > K.$$
The equation (1) and the given constraints (and the convergence of the geometric series $\sum\_{n=0}^\infty 2^{-n}, \sum\_{n=0}^\infty 3^{-n}$) then implies (for large $j$) that
$$ (1 + O(2^{-K})) (e\_{j,1} 2^{j - a\_{1}+1} + \dots + e\_{j,l'} 2^{j - a\_{l'}+1})$$
$$= (1 + O(3^{-K})) (f\_{j,1} 3^{j^\* - b\_{1}+1} + \dots + f\_{j,m'} 3^{j\_\* - b\_{m'}+1})/2$$
which on taking logarithms and rearranging implies that
$$ \frac{\log 2}{\log 3} j = j\_\* + \frac{1}{\log 3} \log \frac{(f\_{j,1} 3^{-b\_{1}+1} + \dots + f\_{j,m'} 3^{-b\_{m'}+1})/2}{e\_{j,1} 2^{-a\_{1}+1}+\dots+e\_{j,l'} 2^{-a\_{l'}}} + O( 2^{-K} ),$$
or on taking modulo $1$ to eliminate $j\_\*$
$$ \frac{\log 2}{\log 3} j = \frac{1}{\log 3} \log \frac{(f\_{j,1} 3^{-b\_{1}+1} + \dots + f\_{j,m'} 3^{-b\_{m'}+1})/2}{e\_{j,1} 2^{-a\_{1}+1}+\dots+e\_{j,l'} 2^{-a\_{l'}+1}} + O( 2^{-K} ) \hbox{ mod } 1.$$
Thus $\frac{\log 2}{\log 3} j \hbox{ mod } 1$ is constrained to the union of $O(O(1)^{m+m'})$ intervals of length $2^{-K}$. But $\frac{\log 2}{\log 3}$ is irrational, so $\frac{\log 2}{\log 3} j \hbox{ mod } 1$ is equidistributed. Thus the set of solutions to this system of constraints has natural upper density at most $O(O(1)^{m+m'} 2^{-K})$. Since $K$ can be taken arbitrary large, we obtain zero density for the original problem as required.


If one used some quantitative result on the irrationality of $\log 2 / \log 3$, such as that provided by Baker's theorem, one would presumably be able to get some quantitative control on how $C$ must necessarily grow with $n$, but I haven't tried to compute this exactly.


