OFFSET
1
COMMENTS
This is defined to be the lexicographically earliest binary sequence with the following property:
If a(n) = 0, underline a(n+1); if a(n) = 1, underline a(n+2). Now, the subsequence of (once or twice) underlined terms must be equal to the original sequence (copy #1), and the subsequence of non-underlined terms must also reproduce the original sequence (copy #2).
From Lars Blomberg: (Start)
For e = (3,4,5,6,7,8,9) the first 10^e terms contain (70, 696, 6928, 69249, 693289, 6941990, 69507187, 694529637) ones. The fraction of '1's seems to be rather constant, but there are subtle differences from any regular trend.
Furthermore, if runs of '0's and '1's are counted, it turns out that from 10^3 terms upwards there is never more than 4 in a run of zeros and from 10^5 terms and upwards never more than 17 in a run of ones.
(End)
Ternary sequences based on the same idea are possible; the lexicographically earliest of them begins with 2, 1, 0, 2, 2, 2, 1, 0, 2, 2, 1, 2, 2, 0, 1, 0, 2, 2, 2, 2, 1, 2, 2, 1, 0, 1, 2, 0, 2, 2, 2, 2, 2, 1, 2, 2, 1,...
The lexicographically earliest sequence dealing with four distinct values seems to begin with 3, 2, 1, 0, 3, 3, 3, 3, 2, 1, 0, 3, 3, 2, 1, 3, 3, 0, 3, 2, 1, 3, 0, 3, 3, 3, 2, 2, 1, 3, 3, 1, 3, 0, 3, 3, 2, 0,...
etc.
From M. F. Hasler, Mar 29 2019: (Start)
The property can be rewritten as follows: For a given sequence a(.), let
U = U(a) := { k >= 2 | a(k-1) = 0 or k >= 3 and a(k-2) = 1 }
be the set or sequence of indices of "underlined" terms, and its complement V = V(a) := { k >= 1 | k not in U(a) } the set of indices of "non-underlined" terms.
Then sequence a(.) must be equal to u = (a(k))_{ k in U }, i.e., u(n) = a(U[n]), and also equal to v = (a(k))_{ k in V }, i.e., v(n) = a(V[n]).
In short: a(n) = a(U[n]) = a(V[n]).
Obviously, each of U (underlined) and V (non-underlined) must be infinite.
Thus a(.) cannot become constant (..., 0, 0, 0, ...) or (..., 1, 1, 1, ...).
Therefore a(.) cannot start (0, ...) nor (1, 1, ...), since a(k) = 0 for all k < n => a(n) = 0; and a(k) = 1 for all k < n, n >= 3 => a(n) = 1.
This proves that the sequence must start a = (1, 0, ...), whence U = {3, ...} and V = {1, 2, ...}.
This implies that we must have a(3) = a(U[1]) = u(1) = a(1) = 1, whence U = U union {3 + 2 = 5}. No smaller term can appear in U, so V = V union {4} = {1, 2, 4,...}.
This implies that we must have a(4) = a(V[3]) = v(3) = a(3) = 1, and U = U union {4 + 2 = 6}.
For any given n > 2, we can calculate a(n) in this way: either n = U[k] or n = V[k] for some k < n (because 1 is not in U and 3 is not in V), and in either case, a(n) = a(k). As we do so, we require U to contain either n+1 or n+2, and all smaller numbers not in U must be in V. Therefore, a(n) will be well defined by the property for all indices n. This shows existence *and uniqueness* of the sequence a(.). The requirement of being the lexicographically first such sequence is not needed. (End)
LINKS
Lars Blomberg, Table of n, a(n) for n = 1..1000
EXAMPLE
The sequence starts (1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1,...)
Instead of underlining terms, we will put parentheses around the terms we want to emphasize:
a(1) = 1 produces parentheses around a(1 + 2 = 3):
1,0,(1),1,0,1,1,1,0,1,0,1,1,1,0,1,...
a(2) = 0 produces parentheses around a(2 + 1 = 3), which is now already done. Then,
a(3) = 1 produces parentheses around a(3 + 2 = 5), and
a(4) = 1 produces parentheses around a(4 + 2 = 6):
1,0,(1),1,(0),(1),1,1,0,1,0,1,1,1,0,1,...
a(5) = 0 produces parentheses around a(5 + 1 = 6), which is already done. Then,
a(6) = 1 produces parentheses around a(6 + 2 = 8),
a(7) = 1 produces parentheses around a(7 + 2 = 9),
a(8) = 1 produces parentheses around a(8 + 2 = 10):
1,0,(1),1,(0),(1),1,(1),(0),(1),0,1,1,1,0,1,...
a(9) = 0 produces parentheses around a(9 + 1 = 10), which is already done. Next,
a(10) = 1 produces parentheses around a(10 + 2 = 12), and
a(11) = 0 produces parentheses around a(11 + 1 = 12) - already done:
1,0,(1),1,(0),(1),1,(1),(0),(1),0,(1),1,1,0,1,... Now,
a(12) = 1 produces parentheses around a(12 + 2 = 14),
a(13) = 1 produces parentheses around a(13 + 2 = 15), and
a(14) = 1 produces parentheses around a(14 + 2 = 16):
1,0,(1),1,(0),(1),1,(1),(0),(1),0,(1),1,(1),(0),(1), ..., and so on.
We see in this small example that the parenthesized terms reproduce the initial sequence:
(1),(0),(1),(1),(0),(1),(1),(1),(0),(1),...
The same is true for the subsequence of non-parenthesized terms:
1, 0, 1, 1, 0, 1, ...
PROG
(PARI) A307183_upto(N, a=List([1, 0]), U=[], u, v=2)={while(#a<N, U=setunion(U, [#a+a[#a]+1]); listput(a, a[if(#a+1<U[1], v++, U=U[^1]; u++)])); Vec(a)} \\ Returns 10^5 terms in a fraction of a second. - M. F. Hasler, Mar 29 2019
CROSSREFS
KEYWORD
base,nonn,nice
AUTHOR
Eric Angelini and Lars Blomberg, Mar 28 2019
EXTENSIONS
Edited by M. F. Hasler, Mar 29 2019
STATUS
approved