login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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(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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 02:12 EDT 2018. Contains 316275 sequences. (Running on oeis4.)