|
|
COMMENTS
|
For each n=0,1,2,3..., choose the smallest nonnegative integer a(n) not occurring earlier such that the digits of a(n) and a(n-1) (none for n=0) taken together can form a palindrome when suitably reordered.
It is conjectured that the sequence is a permutation of the nonnegative integers (motivating the choice of offset 0), i.e., that all numbers will eventually occur. (The conjecture is true - see below. - N. J. A. Sloane, Nov 12 2013)
To test this conjecture, consider the indices n where the smallest integers not yet used occur. If the conjecture is true, this is equivalent to a(m)>a(n) for all m>n; if not, then this list ends at the first missing number. These [n,a(n)] are: [0, 0], [2, 1], [6, 2], [10, 3], [17, 4], [34, 5], [45, 6], [65, 7], [81, 8], [118, 9], [119, 29], [122, 39], [145, 44], [152, 45], [197, 46], [230, 47], [271, 48], [362, 49], [533, 57], [740, 58], [754, 68], [816, 69], [855, 89], [856, 98], [857, 198], [1011, 211], [1012, 222], [1110, 224], [1232, 225], [1385, 234], [1406, 236], [1413, 237], [1767, 238], [1921, 239], [2555, 257], [2590, 259], [2597, 269], [4354, 279], [4355, 297], [4361, 379], [4362, 397], [4368, 479], [4369, 497],...
See A228410 for the variant considering only positive integers, and comments about the differences.
Sequence A228412 is an "arithmetic" variant, where instead of the union of the digits, the sum of terms is considered. Sequence A062932 is a further variant where injectivity is replaced by monotonicity.
Theorem. In any base b >= 2, Eric Angelini's "palindrome" sequence (A228407 in base 10, A230891 and A230892 in base 2) contains every number n >= 0 and is therefore a permutation of the numbers n >= 0.
Proof. Fix the base b >= 2. Classify numbers n into 2^b classes according to the parity of the numbers of 0's, 1's, ..., b-1's they contain.
Construct a graph G with these 2^b classes as nodes, with two nodes joined by an edge iff they are at Hamming distance 0 or 1 apart. This is the b-dimensional cube graph with a loop at each node.
Let S = a(0), a(1), ... denote Angelini's palindromic sequence in base b. A set of digits can be arranged to form a palindrome iff there is an even number of copies of every digit or exactly one of the digits occurs an odd number of times.
At step n, write a(n) on the node of G corresponding to its parity class. The previous remark implies that the successive a(i) will trace out an infinite path in the graph.
At least one node must be visited infinitely often.
The rule for constructing the sequence implies that each node adjacent to a node that is visited infinitely often must also be visited infinitely often. Since G is connected, every node is visited infinitely often. Therefore every number must appear in the sequence, for if a number never appeared, the node corresponding to its parity class would only be visited finitely many times. QED.
Thanks to Rob Arthan for comments on the original version of this proof.
(End)
Records: 0, 11, 100, 101, 103, 110, 114, 120, 201, 210, 1000, 1003, 1007, 1008, 1020, 1029, 1030, 1040, 1047, 1048, 1082, 1208, 1280, 1802, 1820, 2018, 2081, 2108, 2180, 2801, 2810, 8012, 8021, 8102, 8120, 8201, 8210, 10002, 10004, 10007, 10020, 10060, 10080, 10081, 10100, 10105, 10113, 10304, ... ;
Last occurrence: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 29, 39, 44, 45, 46, 47, 48, 49, 57, 58, 68, 69, 89, 98, 198, 211, 222, 224, 225, 234, 236, 237, 238, 239, 257, 259, 269, 279, 297, 379, 397, 479, 497, 589, ... ;
Index of last occurrence: 0, 2, 6, 10, 17, 34, 45, 65, 81, 118, 119, 122, 145, 152, 197, 230, 271, 362, 533, 740, 754, 816, 855, 856, 857, 1011, 1012, 1110, 1232, 1385, 1406, 1413, 1767, 1921, 2555, 2590, 2597, 4354, 4355, 4361, 4362, 4368, 4369, ... . (End)
|
