login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014577 The regular paper-folding sequence (or dragon curve sequence). 51
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

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]

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

A014577 is a generator for A088748: begin A088748 with "1", then add 1 if A014577 is 1; subtract 1 otherwise, getting (1, 2, 3, 2, ...). - Gary W. Adamson, Aug 30 2009

The characteristic function is A091072 - 1. Gary W. Adamson, Apr 11 2010

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

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

From Gary W. Adamson, Jun 20 2012: (Start)

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

1,...1,...0,...1,...1,...0,...0,...1,...1,...1,...

1/2.2/3..1/3..3/4..3/5..2/5..1/4..4/5..5/7..5/8,..

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)

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

From Gary W. Adamson, May 29 2013: (Start)

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):

1/2

1/3 2/3

1/4 2/5 3/5 3/4

1/5 2/7 3/8 3/7 4/7 5/8 5/7 4/5

...

and their corresponding continued fraction representations are:

[2]

[3] [1,2]

[4] [2,2] [1,1,2] [1,3]

[5] [3,2] [2,1,2] [2,3] [1,1,3] [1,1,1,2] [1,2,2] [1,4]

... Record the lengths by rows then reverse rows, getting:

1,

2, 1,

2, 3, 2, 1,

2, 3, 4, 3, 2, 3, 2, 1,

... start with "1" and if the next term is greater than the current term, record a 1, otherwise 0; getting A014557, the Harter-Heighway dragon curve: (1, 1, 0, 1, 1, 0, 0, 1, 1, ...).  (End)

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

From Gary W. Adamson, Jun 04 2021: (Start)

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:

  0   -1

  1   -1, i

  2   -1, i, 1, i

  3   -1, i, 1, i, 1, -i, 1, i

  4   -1, i, 1, i, 1, -i  1, i, 1, -i, -1, -i, 1, -i, 1, i

  ...

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)

From Gary W. Adamson, Jun 09 2021:  (Start)

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)

REFERENCES

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 155, 182.

Danielle Cox and K. McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.

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.

Dekking, Michel, 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).

M. Gardner, Mathematical Magic Show. New York: Vintage, pp. 207-209 and 215-220, 1978.

G. Melancon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

Larry Riddle, Classic Iterated Function Systems. larryriddle.agnesscott.org/ifs/

heighway/heighway.htm

LINKS

Ivan Panchenko, Table of n, a(n) for n = 0..10000

Ibrahim M. Alabdulmohsin, "Analytic Summability Theory", in Summability Calculus: A Comprehensive Theory of Fractional Finite Sums, Springer, Cham, pp 65-91.

J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, 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.

J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, 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]

Joerg Arndt, Matters Computational (The Fxtbook), pp. 88-92; image of the dragon curve on p. 89.

Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.

Michael Coons, An Irrationality Measure for Regular Paperfolding Numbers, Journal of Integer Sequences, Vol. 15 (2012), Article #12.1.6.

Alexey Garber, On triangular paperfolding patterns, arXiv:1807.05627 [math.CO], 2018.

Franz Gahler and Johan Nilsson, Substitution rules for higher-dimensional paperfolding structures, arXiv:1408.4997 [math.DS], 2014.

A. M. Hinz, S. Klavžar and U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 63. Book's website

Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.

J. E. S. Socolar and J. M. Taylor, An aperiodic hexagonal tile, arXiv:1003.4279 [math.CO], 2010.

Eric Weisstein's World of Mathematics, Dragon curve.

Hans Zantema, Complexity of Automatic Sequences, International Conference on Language and Automata Theory and Applications (LATA 2020): Language and Automata Theory and Applications, 260-271.

Index entries for 2-automatic sequences.

Index entries for sequences related to binary expansion of n

Index entries for sequences obtained by enumerating foldings

FORMULA

a(n) = (1+Jacobi(-1,n))/2 (cf. A034947). - N. J. A. Sloane, Jul 27 2012

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).

a(4*n) = 1, a(4*n+2) = 0, a(2*n+1) = a(n). a(n) = 1 - A014707(n) = 2 - A014709(n) = A014710(n) - 1. - Ralf Stephan, Jul 03 2003

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

Can be generated directly from A005811:

1,...2,...1,...2,...3,...2,...1,...2,...3,... = A005811.

1,...1,...0,...1,...1,...0,...0,...1,...1,... = A014577.

By inspection, A014577 = 1 if the corresponding term in A005811 is greater than the previous A005811 term, otherwise 0. - Gary W. Adamson, Jun 20 2012

a((2*n+1)*2^p-1) = (n+1) mod 2, p >= 0. - Johannes W. Meijer, Jan 28 2013

G.f. g(x) satisfies g(x) = x*g(x^2) + 1/(1-x^4). - Robert Israel, Jan 06 2015

EXAMPLE

1 + x + x^3 + x^4 + x^7 + x^8 + x^9 + x^12 + x^15 + x^16 + x^17 + x^19 + ...

From Joerg Arndt, Aug 28 2011: (Start)

Generation via string substitution:

Start: L

Rules:

  L --> L1R

  R --> L0R

  0 --> 0

  1 --> 1

-------------

0:   (#=1)

  L

1:   (#=3)

  L1R

2:   (#=7)

  L1R1L0R

3:   (#=15)

  L1R1L0R1L1R0L0R

4:   (#=31)

  L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R

5:   (#=63)

  L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R1L1R1L0R1L1R0L0R0L1R1L0R0L1R0L0R

Drop all L and R to obtain 1101100111001001110110001100100

(End)

MAPLE

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

a014577 := proc(n) local p, s1, s2, i;

if n=0 then return(1); fi;

s1:=convert(n, base, 2); s2:=nops(s1);

for i from 1 to s2 do if s1[i]=1 then p:=i; break; fi; od:

if p <= s2-1 then 1-s1[p+1]; else 1; fi; end;

[seq(a014577(i), i=1..120)]; # N. J. A. Sloane, Apr 08 2021

# third Maple program:

a:= n-> 1-irem(iquo((n+1)/2^padic[ordp](n+1, 2), 2), 2):

seq(a(n), n=0..120);  # Alois P. Heinz, Apr 08 2021

MATHEMATICA

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 *)

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 *)

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 *)

PROG

(C++) /* code from the fxt library, about 5 CPU cycles per computation */

bool bit_paper_fold(ulong k)

{

  ulong h = k & -k; /* == lowest_one(k) */

  k &= (h<<1);

  return ( k==0 );

} /* Joerg Arndt, Apr 15 2010 */

(PARI) {a(n) = if( n%2, a(n\2), 1 - (n/2%2))} /* Michael Somos, Feb 05 2012 */

(PARI) a(n)=1/2*(1+(-1)^(1/2*((n+1)/2^valuation(n+1, 2)-1))) \\ Ralf Stephan, Sep 02 2013

(MAGMA) [(1+KroneckerSymbol(-1, n))/2 : n in [1..100]] /* or */ [Floor(1/2*(1+(-1)^(1/2*((n+1)/2^Valuation(n+1, 2)-1)))): n in [0..100]]; // Vincenzo Librandi, Aug 05 2015

(Python)

def A014577(n):

    s = bin(n+1)[2:]

    m = len(s)

    i = s[::-1].find('1')

    return 1-int(s[m-i-2]) if m-i-2 >= 0 else 1 # Chai Wah Wu, Apr 08 2021

CROSSREFS

The following are all essentially the same sequence: A014577, A014707, A014709, A014710, A034947, A038189, A082410. - N. J. A. Sloane, Jul 27 2012

A082410(n+2)=a(n).

Cf. A038189, A059125, A065339, A005811, A220466, A088748, A091072, A343173 (first differences), A343174 (partial sums).

The two bisections are A000035 and the sequence itself.

See A343181 for prefixes of length 2^k-1.

Sequence in context: A175480 A285568 A229062 * A157926 A263243 A131377

Adjacent sequences:  A014574 A014575 A014576 * A014578 A014579 A014580

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Eric W. Weisstein

EXTENSIONS

More terms from Ralf Stephan, Jul 03 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 11:13 EST 2021. Contains 349462 sequences. (Running on oeis4.)