'reverse and add!'

[Frederick Magata]

Hello everyone,

this is my first contribution to the mailing list. So I hope you may find it
interesting.

In the context of the popular 'reverse and add!'-algorithm consider the
following sequence:
Let a(n) be the minimal number so that the 'reverse and add!'-algorithm in
base n does not terminate in a palindrome (in base n). If there is no such
number regarding base n, then a(n):=-1.

As proved by K. Brockhaus [1] a(2)=22. Presumably a(10)=196, as investigated
by Walker [2] and Irvin [3].
For further values, please see below. Can anyone confirm them?

I conjecture: a(n) is always positive, a(n)~n^2 and there are infinitely
many n, so that a(n)=n^2-n-1 (E.g. a(19)=19^2-19-1).
Furthermore, I bet there is always a set of sequences, which are transformed
under the 'reverse and add!'-process into each other. Just like the ones in
the proof by Brockhaus.

Best wishes and a happy new year

Frederick Magata
-

Below are the sequence details in the expected OEIS format:
%I A000001
%S A000001 22, 103, 290, 708, 1079, 2656, 1021, 593, 196, 1011, 237, 2701,
361, 447, 413, 3297, 519, 341, 379, 711, 461, 505, 551, 1022, 649, 701, 755,
811, 869, 929, 991, 1055, 1799, 1922, 1259, 1331, 1405, 1481, 1559, 1639,
1595, 1762, 1891, 1934, 2069, 2161, 2255, 2351, 2299, 2549, 4157, 2755,
2861, 2969, 3079, 3191, 3247, 3362, 3539, 3659, 3657, 3905, 4031, 4094,
3893, 4421, 4147, 4691, 4829, 7736, 8061, 8173, 5401, 5549, 5167, 5851,
5927, 6161, 6079, 6236, 6559, 6805, 6971, 6969, 7309, 6785, 7655, 7119,
8009, 8189, 8371, 8276, 8741, 8644, 8831, 8438, 8623, 9305, 9899
%N A000001 The minimal number a(n) so that the 'reverse and add!'-algorithm
in base n does not terminate in a palindrome. If there is no such number in
base n, then a(n):=-1.
%C A000001 All the values from this sequence, except the first one, are not
confirmed yet but only conjectured. (See [2] Walker, [3] Irvin on a(10)=196,
and [1] Brockhaus on a(2)=22)

An obvious algorithm is: Start with r:=n and check, wether the 'reverse and
add!'-algorithm in base n halts in a palindrome or not. If it stops,
increment r by one and repeat the process, else return r.
To obtain the values above, an upper limit of 100 'reverse and add!'-steps
was used, which seemed to suffice. I can not guarantee for it, though.

I conjecture: a(n) shows the same asymptotic behaviour as n^2. Additionally:
For infinite many n, we have a(n)=n^2-n-1.

Again, it is an open question, if the values of the sequence really lead to
infinitely many 'reverse and add!' steps or not. Furthermore: Is the
sequence always positive? I.e. has each base n a value a(n), so that the
'reverse and add!'-process never reaches a palindrome?
%e A000001 a(2)=22, see [1].
%Y A000001 Cf.
[1] K. Brockhaus, On the 'Reverse and Add!' algorithm in base 2
http://www.research.att.com/~njas/sequences/a058042.txt
[2] J. Walker, Three Years Of Computing: Final Report On The Palindrome
Quest
[3] T. Irvin, About Two Months of Computing, or An Addendum to Mr. Walker's
Three Years of Computing
%O A000001 2
%K A000001 ,look,nice,nonn,unkn,
%A A000001 Frederick Magata (frederick.magata at t-online.de), Dec 29 2001