Numbers whose reverse equals 9 times the original

Problem

Given a positive integer \(n\), let \(f(n)\) represent the number of n-digit numbers whose reverse equals 9 times the original, with no leading zeros allowed. Find \(f(n)\).

Solution 1:

We observe the following:

1. The smallest such number is \(1089\), which is also the only 4-digit number with the property, i.e. \(f(1) = f(2) = f(3) = 0, f(4)=1\).

2. Numbers obtained by concatenating \(10\), an arbitrary number of 9s, then \(89\), (e.g. \(1089\), \(10989\), \(109989\), \(1099\ldots9989\)) always have the desired property.

3. More such numbers can be constructed by concatenating strings in 2) in a symmetric manner, e.g. \(10989\#1089\#10989\).

4. Zeros can be inserted during concatenation while keep the property, e.g. \(1089\#00\#10989\#00\#1089\).

Because of zeros, we define \(g(n)\) to be the number of n-digit numbers whose reverse equals 9 times the original, WITH LEADING ZEROES ALLOWED. Then we have \(g(0) = g(1) = g(2) = g(3) = 1\) and \(g(4)=2\) (\(0000\) and \(1089\)). If we allow leading zeroes, then any such string with length \(n\) either has a leading zero or not, and if there is a leading zero, then there must be a corresponding trailing zero, hence we have the following relation: \[ g(n) = g(n-2) + f(n) \] where \(g(n-2)\) is the number of strings with leading zero and \(f(n)\) is the number of string without leading zero.

We also noticed that by symmetry, when \(n \ge 4\), \(g(n)\) can be recursivedly defined as below: \[\begin{eqnarray*} g(n) = g(n-2) + g(n-8) + g(n-10) + \ldots + g(2) + g(0) + 1 & & \textrm{ (n is even)}\ \\ g(n) = g(n-2) + g(n-8) + g(n-10) + \ldots + g(3) + g(1) + 1 & & \textrm{ (n is odd)}\ \\ \end{eqnarray*}\] Here \(g(n-2)\) counts strings with leading zero, \(g(n-8)\) counts strings starting and ending with \(1089\), \(g(n-10)\) counts strings starting and ending with \(10989\) and so on. The last 1 represents the whole string as one piece in the format of \(1099\ldots9989\).

By mathematical induction, we have \[ g(0) = g(1) = g(2) = g(3), g(4) = g(5) \implies g(2k) = g(2k+1)\] and also \[ g(n) = g(n-2) + g(n-4). \] Therefore \[ g(n) = F_{\lfloor \frac{n}{2} \rfloor + 1} \] where \(F_n\) is the Fibonacci sequence defined as \(F_0 = F_1 = 1\) and \(F_n = F_{n-1} + F_{n-2}\).

Finally using the relation \[ g(n) = g(n-2) + f(n), \] we conclude that \(\boxed{f(n) = F_{\lfloor \frac{n}{2} \rfloor + 1} - F_{\lfloor \frac{n}{2} \rfloor} = F_{\lfloor \frac{n}{2} \rfloor - 1}}\) for \(n\ge 4\).

Remark: Using the construction 2 below, we can also show that \(f(n) = g(n-4)\) for \(n \ge 4\), which can be used to derive the Fibonacci relation for \(f\) and \(g\) respectively.

Code

We can write a program using dynamic programming to verify the correctness of the solution above. Below is an example of such a Python program (courtesy of ChatGPT).

```{python}
def compute_g_and_f(n):
    # Base cases for g(n)
    g = [0] * (n + 1)
    g[0] = g[1] = 1  # g(0) = g(1) = 1

    # Compute g(n) using dynamic programming
    for i in range(2, n + 1):
        if i - 2 >= 0:
            g[i] += g[i - 2]
        k = 4
        while i - 2 * k >= 0:
            g[i] += g[i - 2 * k]
            k += 1
        if i >= 4:
            g[i] += 1

    # Base cases for f(n)
    f = [0] * (n + 1)

    # Compute f(n) using g(n)
    # or using f(n) = g(n) - g(n-2)
    for i in range(4, n + 1):
        f[i] = 1
        k = 4
        while i - 2 * k >= 0:
            f[i] += g[i - 2 * k]
            k += 1

    return g, f


# Example Usage
n = 20
g, f = compute_g_and_f(n)
print("g[0:21] = ", *g)
print("f[0:21] = ", *f)
```

g[0:21] =  1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 55 55 89
f[0:21] =  0 0 0 0 1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34

Solution 2:

This blog article (in Chinese) presents yet another elegant solution to this same problem.

Construction 1:

Instead of using mathematical induction in Solution 1, one can also show that \(f(2k) = f(2k+1)\) and \(f(2n+4) = f(2n+2) + f(2n)\) by construction.

To show that \(f(2k) = f(2k+1)\), we can construct a one-to-one mapping from strings of length \(2k\) to strings of length \(2k+1\). The mapping is defined as below by extending the two digits in the middle of length \(2k\) to the three digits in the middle of length \(2k+1\).

“00” -> “000” (e.g. 1089001089 -> 10890001089)

“08” -> “098” (e.g. 1089 -> 10989)

“91” -> “901” (e.g. 10891089 -> 108901089)

“99” -> “999” (e.g. 109989 -> 1099989)

To show that \(f(2n+4) = f(2n+2) + f(2n)\), we construct strings of length \(2n+4\) from strings of length \(2n+2\) and strings of length \(2n\) using the following rules:

First if the input string is in the form \(1099\ldots9989\), regardless of the length \(2n-2 or 2n\), we will generate an output string of length \(2n+4\) in the form \(1099\ldots9989\). Note that here we have a 2-to-1 mapping.

If the input string is of length \(2n+2\) and is not in the form \(1099\ldots9989\), then we construct an output string of length \(2n+4\) based on the two digits in the middle of length \(2n+2\):

“99” -> “9999” (e.g. 10999989 -> 1099999989)

“00” -> “0000” (e.g. 1089001089 -> 108900001089)

“08” -> “0998” (e.g. 108910891089 -> 10891099891089)

“91” -> “9001” (e.g. 10891089 -> 1089001089)

Note that the middle two digits are either 99 or 00 in this case.

If the input string is of length \(2n\) and is not in the form \(1099\ldots9989\), then we construct an output string of length \(2n+4\) based on the two digits in the middle of length \(2n\):

“99” -> “989109” (e.g. 10999989 -> 109989109989)

“00” -> “010890” (e.g. 1089001089 -> 10890108901089)

“08” -> “089108” (e.g. 108910891089 -> 1089108910891089)

“91” -> “910891” (e.g. 10891089 -> 108910891089)

Note that the middle two digits are either 91 or 08 in this case.

Finally we do a special handling for the unique input string of length \(2n+2\) and in the form \(1099\ldots9989\#1099\ldots9989\), there is a corresponding unique output string of length \(2n+4\) and in the form \(1099\ldots9989\#1099\ldots9989\). Note that this unique string CANNOT be generated from any string of length \(2n\) using the rules above (because no additional 1 is added).

This additional 1-to-2 mapping compensates the 2-to-1 mapping of \(1099\ldots9989\), Therefore we have \[f(2n+4) = f(2n+2) + f(2n).\]

Construction 2:

Turns out that there are very simple and elegant rules for constructing such strings. The underlying Fibonacci relation \(f(n) = f(n-2) + f(n-4)\) is also straightforward from this construction. (Pointed out by 申强老师)

Check the code below (courtesy of Gemini) and you will recognize the rules by yourself :-)

```{python}
def generate_strings(n):
  """
  Generates strings of length n based on the given rules.

  Args:
    n: The desired length of the strings.

  Returns:
    A set of strings of length n.
  """

  if n == 4:
      return {"1089"}
  elif n == 5:
      return {"10989"}
  elif n == 6:
      return {"109989"}
  elif n == 7:
      return {"1099989"}
  else:
      # Rule from n-4 to n
      strings_n4 = generate_strings(n-4)
      strings_n4_derived = {f"10{''.join(str(9 - int(d)) for d in s)}89" for s in strings_n4}

      # Rule from n-2 to n
      strings_n2 = generate_strings(n-2)
      strings_n2_derived = {s[:2] + '9' + s[2:-2] + '9' + s[-2:] for s in strings_n2}

      return strings_n4_derived.union(strings_n2_derived)

# Test with n from 8 to 15
for n in range(8, 16):
    print(f"{n}: {generate_strings(n)}")
```

8: {'10999989', '10891089'}
9: {'108901089', '109999989'}
10: {'1098910989', '1099999989', '1089001089'}
11: {'10890001089', '10999999989', '10989010989'}
12: {'109989109989', '109999999989', '109890010989', '108910891089', '108900001089'}
13: {'1099999999989', '1089000001089', '1099890109989', '1098900010989', '1089109891089'}
14: {'10989108910989', '10989000010989', '10999999999989', '10998900109989', '10999891099989', '10890000001089', '10891099891089', '10890108901089'}
15: {'109999999999989', '109890000010989', '108910999891089', '108901098901089', '109998901099989', '109891098910989', '108900000001089', '109989000109989'}