OFFSET
1,1
COMMENTS
The lower Wythoff sequence (A000201) mod 2 (see formula section). - Michel Dekking, Feb 01 2021
A fractal sequence.
From Michel Dekking, Apr 24 2018: (Start)
Usually an integer sequence is called 'fractal' if it has the self-generating properties of a morphic sequence, i.e., the letter to letter projection of a fixed point of a morphism. Indeed, take the alphabet {1,2,...,8} and the morphism eta defined by
eta: 1->5, 2->7, 3->8, 4->6, 5->53, 6->71, 7->82, 8->64.
Then eta has fixed point
x = (5,3,8,6,4,7,1,6,8,2,5,71,6,4,7,5,3,...).
Let pi be the projection morphism
pi(1)=1, pi(2)=0, pi(3)=1, pi(4)=0, pi(5)=1, pi(6)=0, pi(7)=1, pi(8)=0.
Then pi(x) = (a(n)).
To prove this, one may use my paper "Iteration of maps by an automaton".
The two maps are phi_a and phi_b defined by
phi_a(0) = 1, phi_a(1) = 0, phi_b(0) = 0, phi_b(1) = 1.
The substitution is the Fibonacci substitution sigma given by
sigma(a) = b, sigma(b) = ba.
Since the first differences of the lower Wythoff sequence are given by the Fibonacci substitution 1->2, 2-> 21, it follows from replacing 1 with a and 2 with b that (a(n)) is generated by iterating the two maps phi_a and phi_b according to the fixed point babba...of sigma. The two maps phi_a and phi_b are commuting bijections on {a,b}, exactly as in the Example on page 85 of "Iteration of maps by an automaton". It follows as in that example that (a(n)) is generated by the projection of a fixed point of a substitution on an alphabet of 8 letters, and a simple computation as on that page yields the morphism eta. (End)
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..10946
B. Cloitre, Graph of A085005(n) for n=1 up to 3874 [archive.org link]
Benoit Cloitre, Fractal walk starting at (0,0) with step of unit length turning 90° right if a(n)=0 left otherwise for n=1 up to 10^6
Michel Dekking, Iteration of maps by an automaton, Discrete Mathematics 126 (1994), 81-86.
M. Schaefer, E. Sedgwick, and D. Štefankovič, Spiraling and folding: the word view, Algorithmica 60 (2011), 609-626. See section 4.
FORMULA
From Michel Dekking, Apr 24 2018: (Start)
Proof that this sequence is the parity sequence of the lower Wythoff sequence:
if n*phi/2 = M + e, with 0 < e < 1, then 2*floor(phi*n/2) = 2M, and
floor(phi*n) = floor(2M+2e) = 2M or 2M+1.
So floor(phi*n) - 2*floor(phi*n/2) = 0 if floor(phi*n) is even, and equals 1 if floor(phi*n) is odd. (End)
MATHEMATICA
Table[Floor[GoldenRatio n] - 2 Floor[GoldenRatio n/2], {n, 110}] (* Harvey P. Dale, Dec 11 2012 *)
PROG
(PARI) a(n)=(n+sqrtint(5*n^2))%4>1 \\ Charles R Greathouse IV, Feb 07 2013
(Python)
from math import isqrt
def A085002(n): return ((n+isqrt(5*n**2))&2)>>1 # Chai Wah Wu, Aug 10 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Benoit Cloitre, Jun 17 2003
STATUS
approved