A171922 - OEIS

%I #18 Aug 17 2020 22:58:13

%S 1,2,2,4,2,4,6,4,2,11,6,11,2,4,12,4,16,11,12,14,16,6,24,2,29,9,29,4,

%T 24,12,32,14,24,11,16,29,23,6,38,8,41,26,32,40,38,16,24,2,41,43,41,29,

%U 42,12,9,71,4,11,35,53,6,11,24,14,71,23,9,11,32,35,47,2,58,24,58

%N For definition see Comments lines.

%C Constructed in an attempt to find the lexicographically earliest sequence of positive integers, not all 1's, with the property that for n >= 2, if a(n-1) = k, then min(m : a(n+m) = a(n), m > 0) = k.

%C However, the sequence is well-defined, even if should fail to satisfy that property.

%C The sequence is constructed as follows:

%C 1) Given a(n-1) = k, we require min(m : a(n+m) = a(n), m > 0) = k.

%C 2) If a(1) = a(2) = 1, we find by induction that a(n) = 1 for all n, so this is forbidden.

%C 3) For n > 1, if a(n) = k then a(n+b_n(i)) = k for all i, with b_n(0) = 0 and b_n(i+1) = b_n(i) + a(n+b_n(i)-1). Hence every such k appears infinitely often.

%C 4) Hence any a(n) not forced to be equal to a previous a(m) must have some new, never-seen-before value (or violate (1)). Whether such force exists is completely determined by the a(m): 1 <= m < n.

%C 5) We can fully characterize a valid sequence by C = [ c_i ], the distinct values that it takes in order of first appearance. We can then generate the original sequence using (1) and (4). The desired sequence is that generated by the lexically earliest C.

%C 6) Given a(n) = k, we must avoid a(n+m) = k-m for all m > 0, else we would have a(n+1) = a(n+1+k) = a(n+m+1), violating (1).

%C 7) Given known a(n-1) = x, a(n+1) = y and trying to find a(n) = k, we have a(n+1) = a(n+k+1) = y. So by (6) and (3) we must avoid b_n(i) = y+1 for all i.

%C We make the (unproved) assumption that defending against both (6) and (7) is sufficient to avoid backtracking. That appears to work, and produces the current sequence. The associated sequence C is A171921.

%C The sequence has the property that its forwards van Eck transform (see A171898) is the same sequence prefixed with 0. - _N. J. A. Sloane_, Oct 23 2010

%H Hugo van der Sanden, <a href="/A171922/b171922.txt">Table of n, a(n) for n = 1..15137</a>

%H Hugo van der Sanden, <a href="/A171922/a171922.pl.txt">Perl program for this and related sequences</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%Y Cf. A171921, A171898, A171925, A171926, A171927, A171930, A171939, A171940, A309681.

%K nonn

%O 1,2

%A _Hugo van der Sanden_ and _N. J. A. Sloane_, Oct 23 2010, Oct 24 2010