[seqfan] Re: Two make a palindrome

[Rob Arthan]

Neil,

Thanks. You said it twice and I got it the second time. 
In case anyone else is being as slow as me,
let me give a bit more detail about the general case.

Palindromes are not very interesting in base 1, so fix a base b >= 2,
and define the (base b) "type" t(n) of an integer n to be the set of digits that
appear an odd number of times in the base b representation of n. Then n
can  be rearranged into a palindrome iff it has at least two non-zero digits
and t(n) has at most 1 element. Integers m and n > 0 therefore "react" if the
symmetric difference of t(m) and t(n) has at most one element. The types
form the 2^b vertices of a finite graph with an edge between any pair of types
that react.

Adding or removing a single element to a type produces a new type that
reacts with the original (the symmetric difference comprises the element
that was added or removed). It follows that the graph of types is connected,
because you can get from any type to any other by adding and removing
elements one at a time.

Now let's label each vertex in the graph with the smallest number of the
corresponding type and then calculate A228407 updating the labels
to show the smallest number of the corresponding type that has not
yet been generated. When you generate a(n), the label associated with
t(a(n)) will increase (to the smallest x > a(n) that has type t(a(n))).
The formation rule for a(n), says that a(n) is the smallest label
associated with a type t that reacts with t(a(n-1)). But this means that the set
of vertices that are visited infinitely many times must be the whole graph.
(If it were a proper subgraph, then eventually all the labels on that subgraph
would exceed every label outside the subgraph, and as the graph is connected
the formation rules would then force you outside the subgraph.) Thus a(n) will
visit each type infinitely often and hence enumerate the natural numbers.

Regards,

Rob.