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

%I #63 Jun 03 2023 07:25:41

%S 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,

%T 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,

%U 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

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

%C The lower Wythoff sequence (A000201) mod 2 (see formula section). - _Michel Dekking_, Feb 01 2021

%C A fractal sequence.

%C From _Michel Dekking_, Apr 24 2018: (Start)

%C 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

%C eta: 1->5, 2->7, 3->8, 4->6, 5->53, 6->71, 7->82, 8->64.

%C Then eta has fixed point

%C x = (5,3,8,6,4,7,1,6,8,2,5,71,6,4,7,5,3,...).

%C Let pi be the projection morphism

%C pi(1)=1, pi(2)=0, pi(3)=1, pi(4)=0, pi(5)=1, pi(6)=0, pi(7)=1, pi(8)=0.

%C Then pi(x) = (a(n)).

%C To prove this, one may use my paper "Iteration of maps by an automaton".

%C The two maps are phi_a and phi_b defined by

%C phi_a(0) = 1, phi_a(1) = 0, phi_b(0) = 0, phi_b(1) = 1.

%C The substitution is the Fibonacci substitution sigma given by

%C sigma(a) = b, sigma(b) = ba.

%C 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)

%H Antti Karttunen, <a href="/A085002/b085002.txt">Table of n, a(n) for n = 1..10946</a>

%H B. Cloitre, <a href="http://web.archive.org/web/20060326144944/http://membres.lycos.fr/bgourevitch/temporaires/benoit/phifractal.jpg">Graph of A085005(n) for n=1 up to 3874</a> [archive.org link]

%H Benoit Cloitre, <a href="/A085002/a085002.png">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</a>

%H Michel Dekking, <a href="https://doi.org/10.1016/0012-365X(94)90254-2">Iteration of maps by an automaton</a>, Discrete Mathematics 126 (1994), 81-86.

%H M. Schaefer, E. Sedgwick, and D. Štefankovič, <a href="https://doi.org/10.1007/s00453-009-9362-8">Spiraling and folding: the word view</a>, Algorithmica 60 (2011), 609-626. See section 4.

%F a(n) = A105774(n) mod 2 = A000201(n) mod 2. - _Benoit Cloitre_, May 10 2005

%F From _Michel Dekking_, Apr 24 2018: (Start)

%F Proof that this sequence is the parity sequence of the lower Wythoff sequence:

%F if n*phi/2 = M + e, with 0 < e < 1, then 2*floor(phi*n/2) = 2M, and

%F floor(phi*n) = floor(2M+2e) = 2M or 2M+1.

%F 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)

%t Table[Floor[GoldenRatio n] - 2 Floor[GoldenRatio n/2], {n, 110}] (* _Harvey P. Dale_, Dec 11 2012 *)

%o (PARI) a(n)=(n+sqrtint(5*n^2))%4>1 \\ _Charles R Greathouse IV_, Feb 07 2013

%o (Scheme) (define (A085002 n) (A000035 (A105774 n))) ;; _Antti Karttunen_, Mar 17 2017

%o (Python)

%o from math import isqrt

%o def A085002(n): return ((n+isqrt(5*n**2))&2)>>1 # _Chai Wah Wu_, Aug 10 2022

%Y Characteristic function of A283766.

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

%Y See also A171587.

%K nonn,easy

%O 1,1

%A _Benoit Cloitre_, Jun 17 2003