

A267794


a(n) = n2i, where i (0 <= i < n2) is the largest number such that [a(n2)a(i); a(n1)a(i+1)] = [0; 0], or a(n) = 0 if no such i exists.


4



0, 0, 0, 1, 0, 0, 3, 0, 0, 3, 3, 0, 4, 0, 0, 6, 0, 0, 3, 9, 0, 0, 4, 10, 0, 0, 4, 4, 0, 15, 0, 0, 6, 17, 0, 0, 4, 10, 14, 0, 0, 5, 0, 0, 3, 26, 0, 0, 4, 12, 0, 0, 4, 4, 26, 0, 9, 0, 37, 0, 0, 9, 5, 0, 21, 0, 0, 6, 35, 0, 0, 4, 19, 0, 0, 4, 4, 23, 0, 0, 5, 39
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,7


COMMENTS

The sequence A181391 gives the minimal number of leftward moves of [a(n1)] such that [a(n1)  a(i)] = [0] , thus a(n) = n  1  i and 0 <= i <= n2 .
This sequence gives the minimal number of leftward moves of [a(n2); a(n1)].
Possible generalizations:
a) [a(nk) ; ... ; a(n1)]
This sequence has k=2, A181391 has k=1.
b) Moves of the "reading head".
a(n) = n  k  f(i) ; 0 <= f(i) <= (nk) .
This sequence moves function f(i) = i, same for A181391.
c) Higher dimensional version of it.
Such sequences can be viewed as a kind of a self referential Turing machine.
Maximal number of successive zeros in A181391 is 1, in this sequence 2. Conjecture : maximal number of successive zeros is k: a(0); ...; a(j)>0; a(j+1)=0; ...; a(j+k)=0; a(j+k+1)>0; ...
The conjecture is true since (k+1)th zero can occur only on the first occurrence of k successive zeros, by definition of such sequences.  Andrey Zabolotskiy, Oct 31 2016


REFERENCES

Ming Li, P. Vitányi, An Introduction to Kolmogorov Complexity and its Applications, 3rd Edition, Springer, 2008.
M. Sipser, Introduction to the Theory of Computation, 3rd Edition, CENGAGE Learning, 2013.


LINKS

Andrey Zabolotskiy, Table of n, a(n) for n = 0..10001
Nancy Lynch, Automata computability and complexity or great ideas in theoretical computer science, MIT Course, Spring 2010.


EXAMPLE

[a(1);a(2)] = [0;0]. No 2chain [0;0] in the sequence before.
Thus a(3)=0.
[a(2);a(3)] = [0;0]. The nearest previous 2chain [0;0] is [a(1);a(2)].
Thus a(4)=1.
[a(3);a(4)] = [0;1]. No 2chain [0;1] in the sequence before.
Thus a(5)=0.
[a(4);a(5)] = [1;0]. No 2chain [1;0] in the sequence before.
Thus a(6)=0.
[a(5);a(6)] = [0;0]. The nearest previous 2chain [0;0] is [a(2);a(3)].
Thus a(7)=3.
[a(6);a(7)] = [0;3]. No 2chain [0;3] in the sequence before.
Thus a(8)=0.
[a(7);a(8)] = [3;0]. No 2chain [3;0] in the sequence before.
Thus a(9)=0.
and so on.


PROG

(Python)
a=[0, 0]
for i in range(1000):
for j in range(i1, 1, 1):
if a[j:j+2] == a[2:]:
a.append(ij)
break
else:
a.append(0)
print(a)
# Andrey Zabolotskiy, Oct 27 2016


CROSSREFS

Cf. A181391.
Sequence in context: A230661 A178952 A178153 * A282499 A216194 A279168
Adjacent sequences: A267791 A267792 A267793 * A267795 A267796 A267797


KEYWORD

nonn


AUTHOR

Ctibor O. Zizka, Jan 20 2016


EXTENSIONS

Name and terms corrected by Andrey Zabolotskiy, Oct 27 2016


STATUS

approved



