|
| |
|
|
A307183
|
|
A fractal binary sequence: For all n >= 1, underline the term with index n + a(n) + 1; then the two subsequences of underlined terms and of non-underlined terms are both equal to the sequence itself.
|
|
12
|
|
|
|
1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
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
|
|
|
|
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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
