'Recaman transform' of the odd numbers

Nick Hobson nickh at qbyte.org
Mon Feb 19 12:10:37 CET 2007

```Hi Seqfans,

The 'Recaman transform' (see A005132 and e.g. A053461) of the odd numbers
has a rather odd property.  The first few terms of the sequence a(n) are:

0, 1, 4, 9, 2, 11, 22, 35, 20, 3, 22, 43, 66, 41, 14, 43, 12, 45, 10, 47,
8, 49, 6, 51, 98, 147, 96, 149, 94, 37, 96, 157, 220, 155, 88, 19, 90, 17,
... .

The 'inverse' of this sequence -- i.e., the index number at which a(n)
first appears -- denoted by b(n), begins:

0, 1, 4, 9, 2, 749283, 22, None, 20, 3, 18, 5, 16, 41, 14, 39, 1418, 37,
1416, 35, 8, 733, 6, 731, 78, 729, 76, 727, 74, 725, 72, 11775, ... ,

where None indicates that the index does not appear in the first 5 million
terms of a(n).

Notice that the first five terms (and several others) coincide with a(n)!
In fact, over the first 1100 terms, a(n) and b(n) coincide at the
following 168 indices:

0, 1, 2, 3, 4, 6, 8, 9, 13, 14, 20, 22, 41, 101, 103, 105, 107, 109, 111,
113, 115, 117, 119, 120, 121, 123, 125, 127, 129, 131, 352, 537, 539, 541,
543, 545, 547, 549, 551, 553, 555, 557, 559, 561, 563, 565, 567, 569, 571,
573, 575, 577, 579, 581, 583, 585, 587, 589, 591, 593, 595, 597, 599, 601,
603, 605, 607, 609, 900, 902, 904, 906, 908, 910, 912, 914, 916, 918, 920,
922, 924, 926, 928, 930, 932, 934, 936, 938, 940, 942, 944, 946, 948, 950,
952, 954, 956, 958, 960, 962, 964, 966, 968, 970, 972, 974, 976, 978, 980,
982, 984, 986, 988, 990, 992, 994, 996, 998, 1000, 1002, 1004, 1006, 1008,
1010, 1012, 1014, 1016, 1018, 1020, 1022, 1024, 1026, 1028, 1030, 1032,
1034, 1036, 1038, 1040, 1042, 1044, 1046, 1048, 1050, 1052, 1054, 1056,
1058, 1060, 1062, 1064, 1066, 1068, 1070, 1072, 1074, 1076, 1078, 1080,
1082, 1084, 1086, 1088, 1090, 1092, 1094, 1096, 1098.

There is then a break until a run of 2830 consecutive odd indices: 29225,
29227, ... , 34883, at which a(n) and b(n) coincide.

By contrast, the Recaman sequence itself (i.e., the 'Recaman transform' of
the positive integers) coincides much more rarely with its 'inverse'
(A057167), at the following indices for the first 1001 terms:

1, 17, 25, 132, 777, 877.

Curious, don't you think?  I suspect the number of a(n)-b(n) coincidences
is only partly coincidence.

Python script for a(n):

import itertools

def a005132_gen(gen):
"""Generator function for the 'Recaman transform'."""
s, x = set(), 0
gen.next()
yield x
for t in gen:
x -= t
if not (x > 0 and x not in s): x += 2*t
yield x

def a_list(n):
"""Returns a list of the first n >= 0 terms of the 'Recaman transform'
of the odd numbers."""
return list(itertools.islice(a005132_gen(2*x-1 for x in
itertools.count()), n))

Nick

```