analysis of one of Leroy's sequences

[N. J. A. Sloane]

I believe I have analyzed one of Leroy's sequences, namely:

%I A058747
%S A058747 1,2,13,3,6,26,4,11,205,9,5,24,7,51,22,102,20,49,18,8,410,10,16,12,47,
%T A058747 14,100,45,203,43,98,41,3277,39,96,37,201,35,94,15,33,17,408,19,31,21,
%U A058747 92,23,29,25,199,27,90,819,88,197,86,406,84,195,82,1638,80,193,78,404
%N A058747 a(1)=1; for n >= 2, set a(n)=m, where n is the smallest unassigned index with exactly m-1 unassigned indices still remaining between m and m-1.
%C A058747 Suggested by Leroy Quet in SeqFan memo 3602 on Feb. 16, 2004, where he gave the terms with values 1-16, with a(6) the first unassigned term.
%C A058747 Considering the number of unassigned indices to the left of the current position gives an equivalent sequence, A069974, which is easier to analyze. - njas, Feb 23, 2004
%H A058747 Hans Havermann, <a href="http://www.research.att.com/~njas/sequences/a058747.jpg">Illustration of first 1600 terms (with some gaps)</a>
%e A058747 After 1 has been assigned to a(1), the first unassigned term that is one term away from 1 is a(2), so a(2)=2;
%e A058747 the first unassigned term that is two terms away from 2 is a(4), so a(4)=3;
%e A058747 the first unassigned term that is 3 terms away from 3 is a(7), so a(7)=4;
%e A058747 the first unassigned term that is 4 terms away from 4 is a(11), so a(11)=5;
%e A058747 at this point we have 1,2,*,3,*,*,4,*,*,*,5,..., where * indicates a term to which a value has not yet been assigned.
%e A058747 The next value to assign is 6 which must be assigned to the first term of the sequence that is 5 terms away from a(11)=5; since a(5) has not yet been assigned a value, and since at this point 5 terms with unassigned values lie between a(5) and a(11), we must assign 6 to a(5), i.e. a(5)=6.
%Y A058747 Cf. A060153, A062500 (records); A063879 (inverse).
%K A058747 nonn,nice,new,more
%O A058747 1,2
%A A058747 John W. Layman (layman(AT)math.vt.edu), Feb 23 2004

First we transform it into a simpler sequence, namely:

%I A069974
%S A069974 0,0,1,3,6,1,6,12,4,12,2,12,0,12,25,10,25,8,25,6,25,4,25,2,25,0,25,
%T A069974 51,23,51,21,51,19,51,17,51,15,51,13,51,11,51,9,51,7,51,5,51,3,51,1,
%U A069974 51,102,49,102,47,102,45,102,43,102,41,102,39,102,37,102,35,102,33
%N A069974 a(0) = 0; for n>0, a(n) = a(n-1) - n if that is >= 0, else a(n) = a(n-1) + n - 1.
%C A069974 A sequence equivalent to A058747. Let b(k) = A058747(k) for all k. Suppose we have just assigned b(x) = n. Then a(n-1) is the number of b(k) for 1 <= k < x that are not yet assigned.
%e A069974 a(4) = 6, 6-5 = 1 >= 0, so a(5) = 1. 1-6 < 0, so a(6) = 1 + 5 = 6. 
%e A069974 When in A058747 we assign b(8) = 11, there are 2 unassigned b's to the left, namely b(3) and b(6), and indeed a(10) = 2. 
%K A069974 nonn,new
%Y A069974 Cf. A058747, A008344.
%O A069974 0,4
%A A069974 njas, Feb 23 2004

I believe this has the following structure:

It is a concatenation of blocks:

b(-2) = [0]
b(-1) = [0]
b(0) = [1]
b(1) = [3]
b(2) = [6 1 6]
b(3) = [12 4 12 2 12 0 12]
b(4) = [25 10 25 8 25 6 25 ... 25 2 25 0 25]
...

The first few blocks are special. The rest are simple:

Let M(k) be the k-th term of the following sequence:

%I A077854
%S A077854 1,3,6,12,25,51,102,204,409,819,1638,3276,6553,13107,26214,52428,104857,
%T A077854 209715,419430,838860,1677721,3355443,6710886,13421772,26843545,53687091,
%U A077854 107374182,214748364,429496729,858993459,1717986918,3435973836,6871947673
%N A077854 Expansion of 1/((1-x)*(1-2*x)*(1+x^2)).
%K A077854 nonn
%O A077854 0,2
%A A077854 njas, Nov 17 2002

This has the recurrence

M(n) = 3*M(n-1)-3*M(n-2)+3*M(n-3)-2*M(n-4);

with initial values 1 3 6 12.

Then block b(k) is

[M(k), x, M(k), x-2, M(k), x-4, M(k), ..., M(k), 0 or 1, M(k)]

where x = M(k-1) - 2.

The length of the block is M(k+1) - 2 M(k) + M(k-1) .  (That's the second difference
of A077854, shifted one place.)

 From this one can unravel A069974 and hence A058747.

If Benoit Cloitre is reading this, he will recognize that it is
similar to things we did with the Aronson-type sequences
(see A008344).

I haven't actually proved any of this yet, but that
should be straightforward (assuming it's true! - will check
in the daylight tomorrow).

NJAS