%I #28 Mar 09 2024 11:17:54
%S 1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,
%T 1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,
%U 1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0
%N Fixed point of the morphism 0->{1}, 1->{1,0,1}.
%C A080764 and this sequence contain (arbitrarily?) long common substrings.
%C Yes, A080764 and this sequence contain arbitrarily long common substrings, since the morphism 0 -> 1, 1 -> 110 of A080764 and the morphism 0 -> 1, 1 -> 101 generate the same language: the second morphism is a rotation of the first (so they are conjugate to each other). - _Michel Dekking_, Feb 03 2017
%C Zak Seidov points out (Mar 17 2006) that essentially the same sequence arises from the following process: Start with {0,1}; between each pair of digits, insert their sum written in binary. We get successively:
%C {0,1,1}
%C {0,1,1,1,0,1}
%C {0,1,1,1,0,1,1,0,1,1,0,1,1}
%C {0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1}, etc.,
%C which is the current sequence without the initial 1.
%C A Sturmian word with slope sqrt(2)/2 and intercept (3-sqrt(2))/2; see formula. - _Jeffrey Shallit_, Mar 06 2024
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 38.12.1 "Pell palindromes", p. 759 (fast algorithm to compute a function whose value at x=1/2 gives the constant 0.7321604330... whose binary value is 0.1011101101101...)
%F a(n) = floor((n+2)a + b)-floor((n+1)a+b), where a = sqrt(2)/2, b = (3-sqrt(2))/2. - _Jeffrey Shallit_, Mar 06 2024
%F a(n) = round((n+1)/sqrt(2))-round(n/sqrt(2)). - _Chai Wah Wu_, Mar 07 2024
%e The evolution starting with 0 is:
%e 0
%e 1
%e 101
%e 1011101
%e 10111011011011101
%e 10111011011011101101110110111011011011101
%t Nest[ Flatten[ # /. {0 -> {1}, 1 -> {1, 0, 1}}] &, 0, 7] (* _Robert G. Wilson v_, Apr 23 2005 *)
%t h[n_] := Floor[n / Sqrt[2] + 1/2]; Table[h[n + 1] - h[n], {n, 0, 104}]
%t (* _Peter Luschny_, Mar 06 2024 *)
%o (zsh)
%o #! /usr/bin/env zsh
%o function N { local w=$1; for (( i=0; i<7; i+=1 )); do echo $w; w=$(echo $w | S); done }
%o function S { sed 's/1/1_1/g; s/0/1/g; s/_/0/g;' } # 0->1, 1->101
%o N "0"
%o # _Joerg Arndt_, Apr 24 2005
%Y Cf. A049473, A080764.
%K nonn
%O 0,1
%A _Joerg Arndt_, Apr 20 2005
|