[seqfan] Re: Subtracting or adding n to a(n-1)

[David Wilson]

I have another sequence related to Recaman:

0 852655
1 0
2 42
3 261
4 490
5 494
6 5447
7 10023
8 18519
9 33543
10 34292
11 62263
12 62267
13 113405
14 113406
15 199251
16 199252
17 199504
18 2060609
19 2060610
20 2060612
21 2060614
22 2060616
23 2060617
24 2060618
25 2060701
26 11526662
27 11526664
28 11526665
29 11526667
30 11526670
31 11526840
32 11526842
33 11526845
34 11526855
35 20389507
36 20389510
37 20389512
38 20389514
39 20389516
40 20389517
41 20389520
42 20390434
43 20390435
44 20390438
45 20390440
46 20390443
47 20390445
48 20390448

This would be the smallest number that appears n times in Recaman's 
sequence.

a(0) is conjectural, based on the observations noted on A005132. The 
a(n) for n >= 1 can be proved. Specifically, you can show that if the 
value N appears more than once in Recaman's sequence, then the index of 
each occurrence must be <= N. For example, 261 appears three times in 
Recaman's sequence, at indices 109, 125 and 205, all <= 261. If a number 
N < 261 appeared 3 times in Recaman's sequence, it would have to appear 
on indices < 261. Empirically, there is no such number, so 261 is the 
smallest number appearing 3 times in Recaman's sequence. To obtain the 
numbers above, I computed Recaman up to 10^9, far enough to establish 
that the given values are correct.

I suspect that there are numbers that appear arbitrarily many times in 
Recaman's sequence, which is curious given that the definition attempts 
to avoid repeated elements.


For Recaman's sequence r = A005132, you can show that