Double Trouble Numbers
A few years ago I came across a programming problem concerning numbers that were referred to as Double Trouble (DT) numbers, and I will borrow the term here. I looked into them with a friend, Colm Bhandal, because we found them interesting. I will share some of their properties in this post.
First, what is a DT number? A DT number with respect to some base $b$ is a positive integer $n$ such that when the digits (in base $b$) are right rotated one position, the resulting number is $2n$ i.e. double the original number. Some of the questions we will answer are: are there an infinite number of DT numbers for a given base and what form do they take? We will first prove a result that will help answer these questions, namely we will show that for every base $b \geq 2$, there exists a DT number with least significant digit $d$ for all $d \in \{1, \ldots, b - 1\}$. The proof proceeds as follows.
Let $d_{k - 1}b^{k - 1} + d_{k - 2}b^{k - 2} + \cdots + d_0$ be a $k$-digit DT number. Then by definition of a DT number, we have
$$d_0b^{k - 1} + d_{k - 1}b^{k - 2} + \cdots + d_1 = 2 \cdot (d_{k - 1}b^{k - 1} + d_{k - 2}b^{k - 2} + \cdots + d_0)$$
This implies that $d_1 = 2d_0$ and $d_2 = 2d_1 + c$ where $c \in \{0, 1\}$ is the carry of $2 \cdot d_0$ i.e. $c = \lfloor 2d_0 / b \rfloor$. More generally, we have $d_{i + 1} = 2d_i + c_i$ and $c_{i + 1} = \lfloor 2d_i / b \rfloor$ with $c_0 = 0$ and $d_0$ being the least significant digit.
We will view the pair $(d_i, c_i)$ as a state. The state transition function $\delta : \mathbb{Z}_b \times \{0, 1\} \to \mathbb{Z}_b \times \{0, 1\}$ is defined as above; that is
$$\delta : (d_i, c_i) \mapsto (2d_i + c_i, \lfloor 2d_i / b \rfloor)$$
The starting state for a DT number corresponding to its least significant digit is $(d_0, 0)$ where $d_0 \in \mathbb{Z}_b$ is the least significant digit. A DT number is generated when the state returns to $(d_0, 0)$ and the digits of the DT number are the $d_i$ components of the intermediate states in addition to the starting state. The state will always return to the starting state i.e. it will not get stuck in cycles that exclude the starting state. To see this, observe that every state has a unique predecessor state, and therefore, necessarily, the state must return to the starting state. Hence, starting with any least significant digit, we can generate a finite length DT number in any given base. This proves the result.
The maximum length of what we call an elementary DT number is $2(b - 1)$ digits since there are a toral of $2b$ possible states and the states $(0, 0)$ and $(b - 1, 1)$ cannot be encountered because a DT number is positive and the latter state transitions to itself. By elementary, we mean that the DT number is the minimum length DT number with a chosen least significant digit. The minimum length of a DT number is 2 digits. Now given a DT number with $k$ digits, concatenating the number (joining its sequence of digits) with itself yields another (non-elementary) DT number with $2k$ digits. Indeed repeating the process yields DT numbers whose length are arbitrary multiples of $k$. And this tells us, there are an infinite number of DT numbers for any chosen base $b \geq 2$.
An algorithm in Python to find the minimum (by value) DT number for a chosen base is shown below.
def transition(b, state):
"""State transition function with base b."""
d, c = state
return ((2 * d + c) % b, (2 * d) // b)
def find_min_dt(b):
""" Return a list of the digits of the minumum (by value) DT number for base b ordered from least significant to most significant. """
min_digits = None
min_len = 2 * b
for lsd in range(1, b):
digits = [lsd]
init_state = (lsd, 0)
state = transition(b, init_state)
while state != init_state:
d, c = state
digits.append(d)
state = transition(b, state)
if len(digits) < min_len:
min_digits = digits
min_len = len(digits)
return min_digits