A085002 a(n) = floor(phi*n) - 2*floor(phi*n/2) where phi is the golden ratio.

1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1

Offset: 1

Author

Benoit Cloitre, Jun 17 2003

Keywords

• nonn
• easy

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.

Crossrefs

Characteristic function of A283766.

Cf. A000035, A001622, A083035, A083036, A083037, A083038, A085003 (partial sums), A085004, A085005, A105774.

See also A171587.

Programs

Mathematica

Table[Floor[GoldenRatio n] - 2 Floor[GoldenRatio n/2], {n, 110}] (* Harvey P. Dale, Dec 11 2012 *)

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

Scheme

(define (A085002 n) (A000035 (A105774 n))) ;; Antti Karttunen, Mar 17 2017

Formula

a(n) = A105774(n) mod 2 = A000201(n) mod 2. - Benoit Cloitre, May 10 2005

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)