cp's OEIS Frontend

A171922 For definition see Comments lines.

%I A171922 #18 Aug 17 2020 22:58:13
%S A171922 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 A171922 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 A171922 42,12,9,71,4,11,35,53,6,11,24,14,71,23,9,11,32,35,47,2,58,24,58
%N A171922 For definition see Comments lines.
%C A171922 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 A171922 However, the sequence is well-defined, even if should fail to satisfy that property.
%C A171922 The sequence is constructed as follows:
%C A171922 1) Given a(n-1) = k, we require min(m : a(n+m) = a(n), m > 0) = k.
%C A171922 2) If a(1) = a(2) = 1, we find by induction that a(n) = 1 for all n, so this is forbidden.
%C A171922 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 A171922 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 A171922 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 A171922 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 A171922 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 A171922 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 A171922 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 A171922 Hugo van der Sanden, <a href="/A171922/b171922.txt">Table of n, a(n) for n = 1..15137</a>
%H A171922 Hugo van der Sanden, <a href="/A171922/a171922.pl.txt">Perl program for this and related sequences</a>
%H A171922 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%Y A171922 Cf. A171921, A171898, A171925, A171926, A171927, A171930, A171939, A171940, A309681.
%K A171922 nonn
%O A171922 1,2
%A A171922 _Hugo van der Sanden_ and _N. J. A. Sloane_, Oct 23 2010, Oct 24 2010