12
$\begingroup$

Given an integer $n \geq 4$, find all $n$-digit numbers which are 4 times the reverse of their decimal digits e.g. $8712 = 4 \times 2178$.

For each value of $n$, there is only one solution.

An interesting pattern:

\begin{align} 8712 &= 4 \times 2178 \\ 87912 &= 4 \times 21978 \\ 879912 &= 4 \times 219978 \\ 8799912 &= 4 \times 2199978 \end{align}

I have been able to show that the smaller of the two $n$-digit numbers is $22(10^{n-2}-1)$, so the larger number is $4\times 22(10^{n-2}-1) = 88(10^{n-2}-1)$.

Is there a way to show that for any integer $n \geq 4$ , it is always true that $88(10^{n-2}-1)$ is the reverse of $22(10^{n-2}-1)$? (There are no possible solutions for $n = 2$ or $n = 3$.)

$\endgroup$
7
  • 2
    $\begingroup$ The "assumption" that there is only 1 per n seems like the interesting part of the problem. $\endgroup$
    – DanielV
    Commented Jun 22 at 1:20
  • 8
    $\begingroup$ There are two 8-digit numbers $x$ satisfying $4x=\text{reverse of }x$: $4\times21782178=87128712$ and $4\times21999978=87999912$ $\endgroup$ Commented Jun 22 at 2:32
  • 2
    $\begingroup$ @Lucenaposition And that would seem to imply a large family of concatenated solutions when $n > 8$. For instance, $217802178$ with $9$ digits, and $2178002178$ and $2197821978$ for $10$ digits. $\endgroup$ Commented Jun 22 at 5:08
  • 5
    $\begingroup$ There is a general way to characterize numbers like this: Reorder the sequence of digits as $d_1 d_n d_2 d_{n-2} \dots d_{\lceil (n+1)/2 \rceil}$ (reverse half and interleave) then the condition becomes a regular language and properties can be computed from the DFA. It turns out the count of $n$-digit numbers satisfying the condition is $(\lfloor n / 2 \rfloor - 1)$'th Fibonacci number (for $n \geq 2$). $\endgroup$
    – pcpthm
    Commented Jun 22 at 11:15
  • 4
    $\begingroup$ @pcpthm, I would really like to see that written up as an answer. $\endgroup$
    – Aldoggen
    Commented Jun 22 at 13:08

2 Answers 2

13
$\begingroup$

We can obtain the closed form expressions of those $n$-digit numbers as

$\begin{align} 21 \underbrace{99\ldots9}_{n-4 \ \text{times}} 78 &= 22 \underbrace{00\ldots0}_{n-2 \ \text{times}} - 22 \\ &= 22 \cdot 10^{n-2} - 22 \\ &= 22(10^{n-2}-1) \end{align}$

and similarly, the reverse of that is

$\begin{align} 87 \underbrace{99\ldots9}_{n-4 \ \text{times}} 12 &= 88 \underbrace{00\ldots0}_{n-2 \ \text{times}} - 88 \\ &= 88 \cdot 10^{n-2} - 88 \\ &= 88(10^{n-2}-1) \end{align}$

and since we have that $88(10^{n-2}-1) = 4 \cdot 22(10^{n-2}-1)$, we conclude that the numbers with this form constitute a family of $n$-digit numbers where the reverse is equal to $4$ times the number.

$\endgroup$
3
  • 7
    $\begingroup$ This is the bit the OP said they knew how to do. What they are asking is a proof that they are the only such numbers. $\endgroup$ Commented Jun 22 at 4:39
  • 5
    $\begingroup$ Please take a closer look at the question statements the OP has written. $\endgroup$
    – Euclid
    Commented Jun 22 at 16:18
  • $\begingroup$ There are multiple question statements: 1) "find all $n$-digit numbers which are 4 times the reverse of their decimal digits", 2) "For each value of $n$, there is only one solution.", 3) "Is there a way to show that [...] $88(10^{n-2}-1)$ is the reverse of $22(10^{n-2}-1)$?". Clarifying and specifying that this answer focusses on no. 3 may avoid these comments, and signal that the other question statements are still open to answer. $\endgroup$
    – peterwhy
    Commented Jun 24 at 18:50
3
$\begingroup$

This is not a direct answer to the question, but a general way to see numbers defined by digit reversal and linear equality (it should work for any Presburger arithmetic but I don't have formalization). Extended from my comment.

Let $K > 0$ be an integer constant. Consider the proposition: $(x_1, x_2) \mapsto x_1 = K \times x_2$. Represent each number using fixed-base digits as $x_i = \sum_{j=0}^{l-1} d_{i,j} 10^j$ and encode the proposition as a language $L_1 \subseteq \Sigma^*$ over the alphabet $\Sigma := \{0, \dots, 9\}^2$: $$ L_1 := \{ (d_{1,0}, d_{2,0}) (d_{1,1}, d_{2,1}) \dots (d_{1,l-1}, d_{2,l-1}) \mid x_1 = K \times x_2 \}. $$ Then $L_1$ is a regular language. This is a standard result of Presburger arithmetic. Here is the next-state function of an automaton with $K$ states. The state of the automaton represents the current carry.

# Start from {0}. Final is {0}
def next1(carry: int, d1: int, d2: int) -> Iterator[int]:
    t = d2 * K + carry
    if t % 10 == d1:
        yield t // 10

Because the reverse of every regular language is also regular, we can use the reversed encoding of the numbers: $$ L_2 := L_1^R = \{ (d_{1,l-1}, d_{2,l-1}) (d_{1,l-2}, d_{2,l-2}) \dots (d_{1,0}, d_{2,0}) \mid x_1 = K \times x_2 \}. $$ $L_2$ is then also a regular language. Here is another automaton with $K$ states, where the state is used to guess the carry from the next digit position.

# Start from {0}. Final is {0}
def next2(carry: int, d1: int, d2: int) -> Iterator[int]:
  for next_carry in range(K):
    t = d2 * K + next_carry
    if t % 10 == d1 and t // 10 == carry:
        yield next_carry

Now, consider the proposition $x \mapsto x = K \times x^R$ where $x^R$ represents the digit reversal of $x$. For simplicity, assume the digit length $l$ is even. Let $x_1 := x \bmod 10^{l/2}$ and $x_2 := \lfloor x / 10^{l/2} \rfloor$. Then consider an encoding where the digits of $x_2$ are reversed: $$ L_3 := \{ (d_{1,0}, d_{2,l/2-1}) (d_{1,1}, d_{2,l/2-2}) \dots (d_{1,l/2-1}, d_{2,0}) \mid x = K \times x^R \}. $$ Because we have: $$ x = K \times x^R \iff \exists c, c \cdot 10^{l/2} + x_1 = K \times x_2^R \land x_2 = K \times x_1^R + c, $$ $L_3$ is almost equivalent to $L_1 \cap L_2$. The difference can be addressed by restricting the final states of the automaton:

# Start from {(0, 0)}. Final is { (c, c) | c ∈ {0..K-1} }
def next3(state: tuple[int, int], d1: int, d2: int) -> Iterator[tuple[int, int]]:
    carry1, carry2 = state
    for next_carry1 in next1(carry1, d1, d2):
        for next_carry2 in next2(carry2, d2, d1):
            yield (next_carry1, next_carry2)

Because the automaton constructed here is deterministic (at most one derivation for each string in the language), we can count the words in the language using the transition matrix of the automaton.

For $K = 4$, I found that there are only four reachable states from $(0, 0)$: $\{(0, 0), (0, 3), (3, 0), (3, 3)\}$. Taking the submatrix using only the reachable states, the number of strings of length $n$ in $L_3$ can be computed as:

$$ |L_3 \cap \Sigma^n| = \begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ \end{bmatrix}^n \begin{bmatrix}1 \\ 0 \\ 0 \\ 1\end{bmatrix} = F_{n+1}, $$

where $F_n$ is the $n$th Fibonacci number. This count includes numbers with leading zeros, so the count without leading zeros is $F_{n+1} - F_n = F_{n-1}$.

I will leave the analysis of the odd $l$ case to the reader.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .