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