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

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

Offset

0,7

Comments

The sequence A181391 gives the minimal number of leftward moves of [a(n-1)] such that [a(n-1) - a(i)] = [0] , thus a(n) = n - 1 - i and 0 <= i <= n-2 .

This sequence gives the minimal number of leftward moves of [a(n-2); a(n-1)].

Possible generalizations:

a) [a(n-k) ; ... ; a(n-1)]

This sequence has k=2, A181391 has k=1.

b) Moves of the "reading head".

a(n) = n - k - f(i) ; 0 <= f(i) <= (n-k) .

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 2-chain [0;0] in the sequence before.
Thus a(3)=0.
[a(2);a(3)] = [0;0]. The nearest previous 2-chain [0;0] is [a(1);a(2)].
Thus a(4)=1.
[a(3);a(4)] = [0;1]. No 2-chain [0;1] in the sequence before.
Thus a(5)=0.
[a(4);a(5)] = [1;0]. No 2-chain [1;0] in the sequence before.
Thus a(6)=0.
[a(5);a(6)] = [0;0]. The nearest previous 2-chain [0;0] is [a(2);a(3)].
Thus a(7)=3.
[a(6);a(7)] = [0;3]. No 2-chain [0;3] in the sequence before.
Thus a(8)=0.
[a(7);a(8)] = [3;0]. No 2-chain [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(i-1, -1, -1):
        if a[j:j+2] == a[-2:]:
            a.append(i-j)
            break
    else:
        a.append(0)
print(a)
# Andrey Zabolotskiy, Oct 27 2016

Crossrefs

Cf. A181391.

Sequence in context: A230661 A178952 A178153 * A282499 A216194 A365462

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