A267794 - OEIS

%I #38 Nov 02 2016 05:34:05

%S 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,

%T 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,

%U 21,0,0,6,35,0,0,4,19,0,0,4,4,23,0,0,5,39

%N 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.

%C 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 .

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

%C Possible generalizations:

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

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

%C b) Moves of the "reading head".

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

%C This sequence moves function f(i) = i, same for A181391.

%C c) Higher dimensional version of it.

%C Such sequences can be viewed as a kind of a self referential Turing machine.

%C 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; ...

%C 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

%D Ming Li, P. Vitányi, An Introduction to Kolmogorov Complexity and its Applications, 3rd Edition, Springer, 2008.

%D M. Sipser, Introduction to the Theory of Computation, 3rd Edition, CENGAGE Learning, 2013.

%H Andrey Zabolotskiy, <a href="/A267794/b267794.txt">Table of n, a(n) for n = 0..10001</a>

%H Nancy Lynch, <a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec10.pdf">Automata computability and complexity or great ideas in theoretical computer science</a>, MIT Course, Spring 2010.

%e [a(1);a(2)] = [0;0]. No 2-chain [0;0] in the sequence before.

%e Thus a(3)=0.

%e [a(2);a(3)] = [0;0]. The nearest previous 2-chain [0;0] is [a(1);a(2)].

%e Thus a(4)=1.

%e [a(3);a(4)] = [0;1]. No 2-chain [0;1] in the sequence before.

%e Thus a(5)=0.

%e [a(4);a(5)] = [1;0]. No 2-chain [1;0] in the sequence before.

%e Thus a(6)=0.

%e [a(5);a(6)] = [0;0]. The nearest previous 2-chain [0;0] is [a(2);a(3)].

%e Thus a(7)=3.

%e [a(6);a(7)] = [0;3]. No 2-chain [0;3] in the sequence before.

%e Thus a(8)=0.

%e [a(7);a(8)] = [3;0]. No 2-chain [3;0] in the sequence before.

%e Thus a(9)=0.

%e and so on.

%o (Python)

%o a=[0, 0]

%o for i in range(1000):

%o     for j in range(i-1, -1, -1):

%o         if a[j:j+2] == a[-2:]:

%o             a.append(i-j)

%o             break

%o     else:

%o         a.append(0)

%o print(a)

%o # _Andrey Zabolotskiy_, Oct 27 2016

%Y Cf. A181391.

%K nonn

%O 0,7

%A _Ctibor O. Zizka_, Jan 20 2016

%E Name and terms corrected by _Andrey Zabolotskiy_, Oct 27 2016