login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014577 The regular paper-folding sequence (or dragon curve sequence). 27
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. E.g. n = 4 = 100, so a(4) = complement of bit to left of 1, = 1. - Bob Brown (bobb(AT)webaccess.net), Nov 28 2001

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: (1, 1, 0, 1, 1,...) = 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 L-system with rules L->L1R, R->L0R, 1->1, 0->0, starting with L, and dropping all L and R (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, else 0; getting A014557, the Harter-Heighway dragon curve: (1, 1, 0, 1, 1, 0, 0, 1, 1,...).  (End)

REFERENCES

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

Franz Gahler and Johan Nilsson, Substitution rules for higher-dimensional paperfolding structures, http://arxiv.org/pdf/1408.4997.pdf, 2014

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.

LINKS

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

J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences.

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

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

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

J. E. S. Socolar and J. M. Taylor, An aperiodic hexagonal tile

Eric Weisstein's World of Mathematics, Dragon curve.

Index entries for sequences obtained by enumerating foldings

Index entries for sequences related to binary expansion of n

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 flicked. (Proof via isomorphism of both formulae 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; else 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

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

MATHEMATICA

Boole[ EvenQ[ (#/2^IntegerExponent[#, 2] - 1)/2]] &  /@ Range[99] (* Jean-François Alcover, Feb 16 2012, after Gary W. Adamson *)

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

CROSSREFS

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

Cf. A038189, A059125, A065339, A005811, A220466.

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

Cf. A088748 [Gary W. Adamson, Aug 30 2009]

Cf. A091072 [Gary W. Adamson, Apr 11 2010]

Sequence in context: A079559 A175480 A229062 * A157926 A131377 A077049

Adjacent sequences:  A014574 A014575 A014576 * A014578 A014579 A014580

KEYWORD

nonn,easy,nice,changed

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 22 11:49 EDT 2014. Contains 247064 sequences.