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