OFFSET
0,1
COMMENTS
A080764 and this sequence contain (arbitrarily?) long common substrings.
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
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:
{0,1,1}
{0,1,1,1,0,1}
{0,1,1,1,0,1,1,0,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,1,1,0,1}, etc.,
which is the current sequence without the initial 1.
A Sturmian word with slope sqrt(2)/2 and intercept (3-sqrt(2))/2; see formula. - Jeffrey Shallit, Mar 06 2024
LINKS
Joerg Arndt, Matters Computational (The Fxtbook), 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...)
FORMULA
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
a(n) = round((n+1)/sqrt(2))-round(n/sqrt(2)). - Chai Wah Wu, Mar 07 2024
EXAMPLE
The evolution starting with 0 is:
0
1
101
1011101
10111011011011101
10111011011011101101110110111011011011101
MATHEMATICA
Nest[ Flatten[ # /. {0 -> {1}, 1 -> {1, 0, 1}}] &, 0, 7] (* Robert G. Wilson v, Apr 23 2005 *)
h[n_] := Floor[n / Sqrt[2] + 1/2]; Table[h[n + 1] - h[n], {n, 0, 104}]
(* Peter Luschny, Mar 06 2024 *)
PROG
(zsh)
#! /usr/bin/env zsh
function N { local w=$1; for (( i=0; i<7; i+=1 )); do echo $w; w=$(echo $w | S); done }
function S { sed 's/1/1_1/g; s/0/1/g; s/_/0/g; ' } # 0->1, 1->101
N "0"
# Joerg Arndt, Apr 24 2005
CROSSREFS
KEYWORD
nonn
AUTHOR
Joerg Arndt, Apr 20 2005
STATUS
approved