A104521 Fixed point of the morphism 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, 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, 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, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0

Offset: 0

Author

Joerg Arndt, Apr 20 2005

Keywords

• nonn

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

Examples

			The evolution starting with 0 is:
  0
  1
  101
  1011101
  10111011011011101
  10111011011011101101110110111011011011101
		

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...)

Crossrefs

Cf. A049473, A080764.

Programs

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 *)

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

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