Generating numbers by repeated doubling and digit reversal Let $S$ be the smallest set of positive integers satisfying the following conditions:


*$1 \in S$,

*If $n \in S$ then $2n \in S$,

*If $n \in S$ then the digit reversal of $n$ is also in $S$.
We assume that any leading zeros are dropped after digit reversal. For example, the digit reversal of $12300$ is $321.$
Is it true that $S$ contains all positive integers, except those divisible by $3$ or $11$?
EDIT: I have verified the conjecture up to $n = 10\,000$.

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:


*

*Start with $\mathsf{curr=\{\}}$ and $\mathsf{nxt=\{n\}}$.

*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}$.

*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.

*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).
