This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A014577 #321 Aug 11 2025 11:06:33
%S A014577 1,1,0,1,1,0,0,1,1,1,0,0,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1,0,0,1,1,1,
%T A014577 0,1,1,0,0,1,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0,0,1,0,0,1,1,1,0,1,
%U A014577 1,0,0,1,1,1,0,0,1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,0,1,0,0,0,1,1,0
%N A014577 The regular paper-folding sequence (or dragon curve sequence). Alphabet {1,0}.
%C A014577 a(n) is the complement of the bit to the left of the least significant "1" in the binary expansion of n+1. E.g., n = 3, n+1 = 4 = 100_2, so a(3) = (complement of bit to left of 1) = 1. - _Robert L. Brown_, Nov 28 2001 [Adjusted to match offset by _N. J. A. Sloane_, Apr 15 2021]
%C A014577 To construct the sequence: start from 1,(..),0,(..),1,(..),0,(..),1,(..),0,(..),1,(..),0,... and fill undefined places with the sequence itself. - _Benoit Cloitre_, Jul 08 2007
%C A014577 This is the characteristic function of A091072 - 1. - _Gary W. Adamson_, Apr 11 2010
%C A014577 Turns (by 90 degrees) of the Heighway dragon which can be rendered as follows: [Init] Set n=0 and direction=0. [Draw] Draw a unit line (in the current direction). Turn left/right if a(n) is zero/nonzero respectively. [Next] Set n=n+1 and goto (draw). See fxtbook link below. - _Joerg Arndt_, Apr 15 2010
%C A014577 Sequence can be obtained by the L-system with rules L->L1R, R->L0R, 1->1, 0->0, starting with L, and then dropping all L's and R's (see example). - _Joerg Arndt_, Aug 28 2011
%C A014577 From _Gary W. Adamson_, Jun 20 2012: (Start)
%C A014577 One half of the infinite Farey tree can be mapped one-to-one onto A014577 since both sequences can be derived directly from the binary. First few terms are
%C A014577 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, ...
%C A014577 1/2 2/3 1/3 3/4 3/5 2/5 1/4 4/5 5/7 5/8, ...
%C A014577 Infinite Farey tree fractions can be derived from the binary by appending a repeat of rightmost binary term to the right, then recording the number of runs to obtain the continued fraction representation. Example: 9 = 1001 which becomes 10011 which becomes [1,2,2] = 5/7. (End)
%C A014577 The sequence can be considered as a binomial transform operator for a target sequence S(n). Replace the first 1 in A014577 with the first term in S(n), then for successive "1" term in A014577, map the next higher term in S(n). If "0" in A014577, map the next lower term in S(n). Using the sequence S(n) = (1, 3, 5, 7, ...), we obtain (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), .... Then parse the terms into subsequences of 2^k terms, adding the terms in each string. We obtain (1, 4, 12, 32, 80, ...), the binomial transform of (1, 3, 5, 7, ...). The 8-bit string has one 1, three 5's, three 7's and one 1) as expected, or (1, 3, 3, 1) dot (1, 3, 5, 7). - _Gary W. Adamson_, Jun 24 2012
%C A014577 From _Gary W. Adamson_, May 29 2013: (Start)
%C A014577 The sequence can be generated directly from the lengths of continued fraction representations of fractions in one half of the Stern-Brocot tree (fractions between 0 and 1):
%C A014577 1/2
%C A014577 1/3 2/3
%C A014577 1/4 2/5 3/5 3/4
%C A014577 1/5 2/7 3/8 3/7 4/7 5/8 5/7 4/5
%C A014577 ...
%C A014577 and their corresponding continued fraction representations are:
%C A014577 [2]
%C A014577 [3] [1,2]
%C A014577 [4] [2,2] [1,1,2] [1,3]
%C A014577 [5] [3,2] [2,1,2] [2,3] [1,1,3] [1,1,1,2] [1,2,2] [1,4]
%C A014577 ...
%C A014577 Record the lengths by rows then reverse rows, getting:
%C A014577 1,
%C A014577 2, 1,
%C A014577 2, 3, 2, 1,
%C A014577 2, 3, 4, 3, 2, 3, 2, 1,
%C A014577 ...
%C A014577 start with "1" and if the next term is greater than the current term, record a 1, otherwise 0; getting the present sequence, the Harter-Heighway dragon curve. (End)
%C A014577 The paper-folding word "110110011100100111011000..." can be created by concatenating the terms of a fixed point of the morphism or string substitution rule: 00 -> 1000, 01 -> 1001, 10 -> 1100 & 11 -> 1101, beginning with "11". - _Robert G. Wilson v_, Jun 11 2015
%C A014577 From _Gary W. Adamson_, Jun 04 2021: (Start)
%C A014577 Since the Heighway dragon is composed of right angles, it can be mapped with unit trajectories (Right = 1, Left = (-1), Up = i and Down = -i) on the complex plane where i = sqrt(-1). The initial (0th) iterate is chosen in this case to be the unit line from (0,0) to (-1,0). Then follow the directions below as indicated, resulting in a reflected variant of the dragon curve shown at the Eric Weisstein link. The conjectured system of complex plane trajectories is:
%C A014577 0 -1
%C A014577 1 -1, i
%C A014577 2 -1, i, 1, i
%C A014577 3 -1, i, 1, i, 1, -i, 1, i
%C A014577 4 -1, i, 1, i, 1, -i, 1, i, 1, -i, -1, -i, 1, -i, 1, i
%C A014577 ...
%C A014577 The conjecture succeeds through the 4th iterate. It appears that to generate the (n+1)-th row, bring down the n-th row as the left half of row (n+1). For the right half of row (n+1), bring down the n-th row but change the signs of the first half of row n. For example, to get the complex plane instructions for the third iterate of the dragon curve, bring down (-1, i, 1, i) as the left half, and the right half is (1, -i, 1, i). (End)
%C A014577 From _Gary W. Adamson_, Jun 09 2021: (Start)
%C A014577 Partial sums of the iterate trajectories produce a sequence of complex addresses for unit segments. Partial sums of row 4 are: -1, (-1+i), i, 2i, (1+2i), (1+i), (2+i), (2+2i), (3+2i), (3+i), (2+i), 2, 3, (3-i), (4-i), 4. (zeros are omitted with terms of the form a+0i). The reflected variant of the dragon curve has the 0th iterate from (0,0) to (1,0), and the respective addresses simply change the signs of the real terms. (End)
%D A014577 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 155, 182.
%D A014577 Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted in Donald E. Knuth, Selected Papers on Fun and Games, CSLI Publications, 2010, pages 571-614.
%D A014577 Michel Dekking, Michel Mendes France, and Alf van der Poorten, "Folds", The Mathematical Intelligencer, 4.3 (1982): 130-138 & front cover, and 4:4 (1982): 173-181 (printed in two parts).
%D A014577 Martin Gardner, Mathematical Magic Show, New York: Vintage, pp. 207-209 and 215-220, 1978.
%D A014577 Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%H A014577 Ivan Panchenko, <a href="/A014577/b014577.txt">Table of n, a(n) for n = 0..10000</a>
%H A014577 Ibrahim M. Alabdulmohsin, <a href="https://doi.org/10.1007/978-3-319-74648-7_4">"Analytic Summability Theory"</a>, in Summability Calculus: A Comprehensive Theory of Fractional Finite Sums, Springer, Cham, pp 65-91.
%H A014577 Jean-Paul Allouche and Michel Mendès France, <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/allmendeshouches.pdf">Automata and Automatic Sequences</a>, in: F. Axel and D. Gratias (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
%H A014577 Jean-Paul Allouche and Michel Mendès France, <a href="/A003842/a003842.pdf">Automata and Automatic Sequences</a>, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
%H A014577 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 88-92; image of the dragon curve on p. 89.
%H A014577 Paul Barry, <a href="https://arxiv.org/abs/2107.00442">Conjectures and results on some generalized Rueppel sequences</a>, arXiv:2107.00442 [math.CO], 2021.
%H A014577 Michael Coons, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Coons/coons3.html">An Irrationality Measure for Regular Paperfolding Numbers</a>, Journal of Integer Sequences, Vol. 15 (2012), Article #12.1.6.
%H A014577 Danielle Cox and K. McLellan, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/55-2/CoxMcLellan021717.pdf">A problem on generation sets containing Fibonacci numbers</a>, Fib. Quart., 55 (No. 2, 2017), 105-113.
%H A014577 Chandler Davis and Donald E. Knuth, <a href="/A005811/a005811.pdf">Number Representations and Dragon Curves</a>, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
%H A014577 Alexey Garber, <a href="https://arxiv.org/abs/1807.05627">On triangular paperfolding patterns</a>, arXiv:1807.05627 [math.CO], 2018.
%H A014577 Franz Gahler and Johan Nilsson, <a href="http://arxiv.org/abs/1408.4997">Substitution rules for higher-dimensional paperfolding structures</a>, arXiv:1408.4997 [math.DS], 2014.
%H A014577 Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 63. <a href="http://tohbook.info">Book's website</a>
%H A014577 Eve Kivivuori, <a href="http://hdl.handle.net/10138/562976">Implementing, analyzing, and benchmarking the Relative Lempel-Ziv compression algorithm</a>, Master's Thesis, Univ. Helsinki (Finland 2023).
%H A014577 Guy Melançon, Factorizing infinite words using Maple, <a href="https://www.researchgate.net/publication/322200645_MapleTech_Volume_4_no_1_Spring_1997">MapleTech journal</a>, (14 Mb) vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
%H A014577 Johan Nilsson, <a href="https://arxiv.org/abs/2409.03068">The Pattern Complexity of the 2-Dimensional Paperfolding Sequence</a>, arXiv:2409.03068 [math.CO], 2024. See p. 1.
%H A014577 Larry Riddle, <a href="https://larryriddle.agnesscott.org/ifs/heighway/heighway.htm">Heighway Dragon</a>, Classic Iterated Function Systems.
%H A014577 Luke Schaeffer and Jeffrey Shallit, <a href="https://doi.org/10.37236/5752">Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences</a>, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
%H A014577 Joshua E. S. Socolar and Joan M. Taylor, <a href="http://arxiv.org/abs/1003.4279">An aperiodic hexagonal tile</a>, arXiv:1003.4279 [math.CO], 2010.
%H A014577 László Tóth, <a href="https://arxiv.org/abs/2508.04151">Evaluating zeta(s) At Odd Positive Integers Using Automatic Dirichlet Series</a>, arXiv:2508.04151 [math.NT], 2025.
%H A014577 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DragonCurve.html">Dragon curve</a>.
%H A014577 Hans Zantema, <a href="https://doi.org/10.1007/978-3-030-40608-0_18">Complexity of Automatic Sequences</a>, International Conference on Language and Automata Theory and Applications (LATA 2020): Language and Automata Theory and Applications, 260-271.
%H A014577 <a href="/index/Ar#2-automatic">Index entries for 2-automatic sequences</a>.
%H A014577 <a href="/index/Fo#fold">Index entries for sequences obtained by enumerating foldings</a>.
%H A014577 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.
%F A014577 a(n) = (1+Jacobi(-1,n+1))/2 (cf. A034947). - _N. J. A. Sloane_, Jul 27 2012 [Adjusted to match offset by _Peter Munn_, Jul 01 2022]
%F A014577 Set a=1, b=0, S(0)=a, S(n+1) = S(n), a, F(S(n)), where F(x) reverses x and then interchanges a and b; sequence is limit S(infinity).
%F A014577 From _Ralf Stephan_, Jul 03 2003: (Start)
%F A014577 a(4*n) = 1, a(4*n+2) = 0, a(2*n+1) = a(n).
%F A014577 a(n) = 1 - A014707(n) = 2 - A014709(n) = A014710(n) - 1. (End)
%F A014577 Set a=1, b=0, S(0)=a, S(n+1)=S(n), a, M(S(n)), where M(S) is S but the bit in the middle position flipped. (Proof via isomorphism of both formulas to a modified string substitution.) - _Benjamin Heiland_, Dec 11 2011
%F A014577 a(n) = 1 if A005811(n+1) > A005811(n), otherwise a(n) = 0. - _Gary W. Adamson_, Jun 20 2012
%F A014577 a((2*n+1)*2^p-1) = (n+1) mod 2, p >= 0. - _Johannes W. Meijer_, Jan 28 2013
%F A014577 G.f. g(x) satisfies g(x) = x*g(x^2) + 1/(1-x^4). - _Robert Israel_, Jan 06 2015
%F A014577 a(n) = 1 - A065339(n+1) mod 2. - _Peter Munn_, Jun 29 2022
%F A014577 From _A.H.M. Smeets_, Mar 19 2023: (Start)
%F A014577 a(n) = 1 - A038189(n+1).
%F A014577 a(n) = A082410(n+2).
%F A014577 a(n) = 1 - A089013(n+1)
%F A014577 a(n) = (3 - A099545(n+1))/2.
%F A014577 a(n) = (A112347(n+1) + 1)/2.
%F A014577 a(n) = (A121238(n+1) + 1)/2.
%F A014577 a(n) = (A317335(n) + 2)/3.
%F A014577 a(n) = (A317336(n) + 10)/3. (End)
%F A014577 Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/2. - _Amiram Eldar_, Sep 14 2024
%e A014577 1 + x + x^3 + x^4 + x^7 + x^8 + x^9 + x^12 + x^15 + x^16 + x^17 + x^19 + ...
%e A014577 From _Joerg Arndt_, Aug 28 2011: (Start)
%e A014577 Generation via string substitution:
%e A014577 Start: L
%e A014577 Rules:
%e A014577 L --> L1R
%e A014577 R --> L0R
%e A014577 0 --> 0
%e A014577 1 --> 1
%e A014577 -------------
%e A014577 0: (#=1)
%e A014577 L
%e A014577 1: (#=3)
%e A014577 L1R
%e A014577 2: (#=7)
%e A014577 L1R1L0R
%e A014577 3: (#=15)
%e A014577 L1R1L0R1L1R0L0R
%e A014577 4: (#=31)
%e A014577 L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R
%e A014577 5: (#=63)
%e A014577 L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R1L1R1L0R1L1R0L0R0L1R1L0R0L1R0L0R
%e A014577 Drop all L and R to obtain 1101100111001001110110001100100
%e A014577 (End)
%p A014577 nmax:=98: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 0 to ceil(nmax/(p+2))+1 do a((2*n+1)*2^p-1) := (n+1) mod 2 od: od: seq(a(n), n=0..nmax); # _Johannes W. Meijer_, Jan 28 2013
%p A014577 a014577 := proc(n) local p,s1,s2,i;
%p A014577 if n=0 then return(1); fi;
%p A014577 s1:=convert(n,base,2); s2:=nops(s1);
%p A014577 for i from 1 to s2 do if s1[i]=1 then p:=i; break; fi; od:
%p A014577 if p <= s2-1 then 1-s1[p+1]; else 1; fi; end;
%p A014577 [seq(a014577(i),i=1..120)]; # _N. J. A. Sloane_, Apr 08 2021
%p A014577 # third Maple program:
%p A014577 a:= n-> 1-irem(iquo((n+1)/2^padic[ordp](n+1, 2), 2), 2):
%p A014577 seq(a(n), n=0..120); # _Alois P. Heinz_, Apr 08 2021
%t A014577 a[n_] := Boole[EvenQ[((n+1)/2^IntegerExponent[n+1, 2]-1)/2]]; Table[a[n], {n, 0, 98}] (* _Jean-François Alcover_, Feb 16 2012, after _Gary W. Adamson_, updated Nov 21 2014 *)
%t A014577 Table[1-(((Mod[#1,2^(#2+2)]/2^#2)&[n,IntegerExponent[n,2]])-1)/2,{n,1,100,1}] (* WolframAlpha compatible code; _Robert L. Brown_, Jan 06 2015 *)
%t A014577 MapThread[(a[x_/;IntegerQ[(x-#1)/4]]:= #2)&,{{1,3},{1,0}}];a[x_/;IntegerQ[x/2]]:=a[x/2];a/@ Range[100] (* _Bradley Klee_, Aug 04 2015 *)
%t A014577 (1 + JacobiSymbol[-1, Range[100]])/2 (* _Paolo Xausa_, May 22 2024 *)
%t A014577 Array[Boole[BitAnd[#, BitAnd[#, -#]*2] == 0] &, 100] (* _Paolo Xausa_, May 22 2024, after _Joerg Arndt_ C++ code *)
%o A014577 (C++) /* code from the fxt library, about 5 CPU cycles per computation */
%o A014577 bool bit_paper_fold(ulong k)
%o A014577 {
%o A014577 ulong h = k & -k; /* == lowest_one(k) */
%o A014577 k &= (h<<1);
%o A014577 return ( k==0 );
%o A014577 } /* _Joerg Arndt_, Apr 15 2010 */
%o A014577 (PARI) {a(n) = if( n%2, a(n\2), 1 - (n/2%2))} /* _Michael Somos_, Feb 05 2012 */
%o A014577 (PARI) a(n)=1/2*(1+(-1)^(1/2*((n+1)/2^valuation(n+1,2)-1))) \\ _Ralf Stephan_, Sep 02 2013
%o A014577 (PARI) a(n)=!bittest(n+1,valuation(n+1,2)+1); \\ _Robert L. Brown_, Jul 07 2025
%o A014577 (Magma) [(1+KroneckerSymbol(-1,n))/2: n in [1..100]]; // _Vincenzo Librandi_, Aug 05 2015
%o A014577 (Magma) [Floor(1/2*(1+(-1)^(1/2*((n+1)/2^Valuation(n+1, 2)-1)))): n in [0..100]]; // _Vincenzo Librandi_, Aug 05 2015
%o A014577 (Python)
%o A014577 def A014577(n):
%o A014577 s = bin(n+1)[2:]
%o A014577 m = len(s)
%o A014577 i = s[::-1].find('1')
%o A014577 return 1-int(s[m-i-2]) if m-i-2 >= 0 else 1 # _Chai Wah Wu_, Apr 08 2021
%Y A014577 Essentially the same: A014707, A014709, A014710, A034947, A038189, A082410, A089013, A099545, A112347, A121238, A317335, A317336.
%Y A014577 Cf. A059125, A065339, A005811, A220466, A088748, A091072, A343173 (first differences), A343174 (partial sums).
%Y A014577 The two bisections are A000035 and the sequence itself.
%Y A014577 See A343181 for prefixes of length 2^k-1.
%K A014577 nonn,easy,nice
%O A014577 0,1
%A A014577 _N. J. A. Sloane_, _Eric W. Weisstein_
%E A014577 More terms from _Ralf Stephan_, Jul 03 2003