Generating numbers by repeated doubling and digit reversal

Let $S$ be the smallest set of positive integers satisfying the following conditions:

Solution 1:

This is to show one can arrive at $5$ by several steps. I did this "backward" by continually starting with a goal number and allowing the moves: multiply by $5$, reversal, divide an even number by $2$ To explain the multiply by $5$ step, suppose the goal number was $17.$ Then $17 \cdot 5=85,$ and if we got to $85$ somehow, then $2 \cdot 85=170,$ reversed is $71,$ and reversed again is our goal number $17.$ So this is a kind of attempt at backtracking from some goal number.

For the goal of $5$ I multiplied by $5$ to get $25,$ reversed to get $52,$ then divided by $2$ twice to get $13.$ Thus if $13$ can be obtained, so can $5.$

From here on I'll just present the links, each step being doubling or reversal, without showing the backtracking method above outlined.

From 13 to 5: $13,26,52,25,50,5.$

From 7 to 13: $7,14,28,56,65,130,31,13.$

From 19 to 7: $19,91,182,281,562,265,530,35,70,7$

From 64 to 19: $$64,46,92,184,368,736,1472,2741,5482,2845,5690,965,\\ 1930,391,193,386,772,277,554,455,910,19.$$

Then since powers of $2$ such as $64$ are obtained from $1$ by doubling, we can put the above together and get a (long) derivation of the goal number $5.$

There is a lot of choice to be made while "backtracking" but a subgoal is to backtrack to a reasonably small number, and hope that from there more backtracking will eventually lead to something known to be attainable already (such as a power of 2). As in the above example for obtaining 5, the numbers arrived at in between may become large, and still later small again. Not a sure-fire method, for example a failure to backtrack in one (or several) way(s)doesn't rule a number out.

Solution 2:

Let $A$ be the set of natural numbers not divisible by $3$ or $11$. Working backwards, we want to be able to derive $1$ from any $n\in A$, using a combination of the following two steps:

• $n\rightarrow R(n)\cdot 10^k$, if $n$ is not a multiple of $10$, where $R(n)$ is the reversal of $n$, and $k$ is any non-negative integer;
• $n\rightarrow n/2$, if $n$ is even.

The second step is the inverse of the rule "if $n\in S$ then $2n\in S$" in the original problem, which only produces even numbers. The first step is the inverse of the rule "if $n\in S$ then the digit-reversal of $n$ is in $S$", with its condition that trailing zeroes in $n$ are dropped after the reversal... this rule only produces non-multiples of $10$, and when it is inverted, we can recover any number of trailing zeroes. Note that these steps preserve membership in $A$.

By induction, we can get from any number $n\in A$ to $1$ iff we can get from any number $n \in A \setminus \{1\}$ to some smaller number $m<n$. When $n$ is even, the second step immediately yields a smaller number, so we don't need to check even starting values. That being the case, we'll never start with a multiple of $10$; so any time we encounter a multiple of $10$ in a derivation, it must be directly preceded by a first-rule application, followed by some number of second-rule applications; and we could have produced any number of additional trailing zeroes by increasing $k$ in that first-rule application. So $n\rightarrow 10n$ produces no new reachability relations if $n$ is a multiple of $10$. Since $n\rightarrow 10n$ can also be achieved when $n$ is not a multiple of $10$ (by applying the first rule twice), we can simplify the rules for derivations that start with an even number. In fact,

The original conjecture is equivalent to the claim that any number $n\ge 5$ not divisible by $2$, $3$, or $11$, can be made smaller by some combination of these three steps:

• $n\rightarrow R(n)$, if $n$ is not a multiple of $10$, where $R(n)$ is the reversal of $n$;
• $n\rightarrow 10n$;
• $n\rightarrow n/2$, if $n$ is even.

A simple search algorithm is the following:

1. Start with $\mathsf{curr=\{\}}$ and $\mathsf{nxt=\{n\}}$.
2. Choose the smallest element of $\mathsf{nxt}$ (with probability $\alpha$), or the smallest element of $\mathsf{nxt}$ with the smallest number of zero digits (with probability $1-\alpha$). Remove that element from $\mathsf{nxt}$ and add it to $\mathsf{curr}$.
3. Apply the three possible steps to this element. When a new value (not already in $\mathsf{curr}$ or $\mathsf{nxt}$) is generated, add it to $\mathsf{nxt}$. If the new value is less than $n$, we're done.
4. Return to step 2.

Using this heuristic, I've been able to verify the conjecture for all $n \le 10^8$. Generally choosing the smallest element of $\mathsf{nxt}$ is desirable (so $\alpha=0.9$ works well); but for specific values of $n$ such as $n=10^4+1$ and $n=10^6+1$, the alternate strategy is faster (so $\alpha=0.1$ works for these).

Solution 3:

Some thoughts:

Divisibility by $3$:

E.g. $n$ is divisible by $3$ if and only if its digit sum is divisible by 3, e.g. see here. $$ 3 \mid n \iff 3 \mid ds(n) $$

Now $S$ contains numbers $2^k (k \in \mathbb{N}_0)$ which are not divisible by $3$ (see unique prime factorization). Thus their digit sum is not divisible by $3$. A number generated from reversal of its digit string (and removal of trailing zero digits) still has the same digit sum and thus is not divisible by $3$ either. $$ 3 \not\mid 2^k =: x \iff 3 \not\mid ds(x) = ds(y) \iff 3 \not\mid y \\ y = \text{rev}(x) = \text{integer}(\text{normalize}((x)_{10}^R)) \quad (*) $$ Multiplication by some non-trivial power of $2$ will just increase the exponent of $2$ in the unique prime factorization $n = 2^{e_2} 3^{e_3} 5^{e_5} \cdots$ and not increase the exponent of $3$, so it will not affect divisibility by $3$.

So numbers divisible by $3$ are not members of $S$.

Divisibility by $11$:

Divisibility by $11$ of an integer $n$ seems to relate to the divisibility by $11$ of the alternating digit sum, which is also invariant to the generation via reversal etc, up to a sign, which does not matter for divisibility. A similar argument like for $3$ should apply.

So the claim of no numbers divisible by $3$ and $11$ in $S$ seems valid and, as Robert Israel notes in the comments, the hard part left is to argue why every other positive integer might show up in $S$, or not.

About the conjecture:

My personal guess is that this conjecture is not true. The numbers in the gaps between the $2^k$, e.g. $5$ can only get introduced by that reversal process $(*)$. So it must originate from some digit string $s_5 = 5\,0^m$, possibly for a very large $m$. I somehow doubt that such a string shows up in the digit strings for $2^k$ and friends. (see coffeemath's example)

Generating $S$:

We can use a binary word $$ w \in \{ 0, 1 \}^n \quad (n \in \mathbb{N}) \\ w = d_1 \cdots d_n $$ to encode a generation of an element $s \in S$ by applying the rules $n$ times, each binary digit $d_i$ of $w$ encoding a function $f_i^{(w)}:\mathbb{N}\to\mathbb{N}$: $$ f_i^{(w)}(k) = \begin{cases} 2 k & \text{for } d_i = 0 \\ \text{rev}(k) & \text{for } d_i = 1 \end{cases} \\ $$ those functions are applied one after another, composing a resulting function $f^{(w)}$: $$ f^{(w)} = f_n^{(w)} \circ f_{n-1}^{(w)} \circ \cdots \circ f_2^{(w)} \circ f_1^{(w)} \\ 1 = \sigma(\epsilon) \\ s = \sigma(w) = f^{(w)}(1)uu $$

Examples:

$$ 58 = \sigma(0000001010) \\ 1 \overset{0}{\to} 2 \overset{0}{\to} 4 \overset{0}{\to} 8 \overset{0}{\to} 16 \overset{0}{\to} 32 \overset{0}{\to} 64 \overset{1}{\to} 46 \overset{0}{\to} 92 \overset{1}{\to} 29 \overset{0}{\to} 58 \\ 2 = \sigma(0) \\ 4 = \sigma(00) $$

The binary words of length $n$ can be generated by counting from $0$ to $2^n-1$ and computing the base $2$ representation digit strings of length $n$ (with leading zero digits). Then $$ S = \bigcup_{n=0}^\infty S_n \\ S_0 = \{ \sigma(\epsilon) \} = \{ 1 \} \\ S_n = \{ \sigma(w) \mid w = (i)_2, i \in \{ 0, \ldots, 2^n-1\} \} \quad (n \ge 1) $$ Practical Considerations:

The number of binary words of length $n$ is $2^n$, it grows exponentially with $n$, so sooner or later a computation will need too much time. On the machine I tried a Ruby script, it gets ugly around $n=24$.

Optimization 1:

One optimization is to note that of the various words $w$ which evaluate to a certain value $s$, $$ s = \sigma(w) $$ the one with minimal length and in the order of the word's value interpreted as integer value, that word just features $1$ or $11$ as sub sequence of $1$ digits, but no longer sequence. This is because $$ \text{rev}^2 \ne \text{id} $$ e.g. $\text{rev}^2(1200) = \text{rev}(21) = 12$ and $$ \text{rev}^{1+2k} = \text{rev} \quad (k\in \mathbb{N}) $$ so we can substitute $$ 1(11)^+ \to 1 $$ to shorten the binary words to ones with the same $s$ value, or ignore them, because we must have seen them before, if we go from shorter to longer words.

Optimization 2:

The $\text{rev}^2$ operation acts like a trunction of trailing zero digits (see above example for $1200$): $$ \text{rev}^2(u0^k) = \text{rev}(u^R) = u $$

A Second Encoding:

The above means we can compose the generation of a member $s\in S$ via three basic operations: $$ 0: 0 \leftrightarrow f(k) = 2 k \\ 1: 1 \leftrightarrow f(k) = \text{rev}(k) \\ 2: 11 \leftrightarrow f(x) = \text{rev}^2(k) $$ and use ternary numbers for encoding. This way we skip some generations which add no new member.