|
| |
|
|
A014577
|
|
The regular paper-folding (or dragon curve) sequence.
|
|
22
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,1
|
|
|
COMMENTS
| Can be computed by storing only one large integer. It 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 (benoit7848c(AT)orange.fr), 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,...). [From Gary W. Adamson , Aug 30 2009]
Contribution from, Apr 11 2010: (Start)
After changing the offset to 1: (1, 1, 0, 1, 1, 0, 0, 1, 1, 1,...) = the
characteristic function of A091072: (1, 2, 4, 5, 8, 9, 10, 13,...). (End)
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. [From 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]
|
|
|
REFERENCES
| 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
| J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences.
Joerg Arndt, Fxtbook, p.88-92, image of the dragon curve on p. 89
J. E. S. Socolar and J. M. Taylor, An aperiodic hexagonal tile
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Index entries for sequences obtained by enumerating foldings
|
|
|
FORMULA
| 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 modifided string substitution.) [Benjamin Heiland, Dec 11 2011]
|
|
|
EXAMPLE
| 1 + x + x^3 + x^4 + x^7 + x^8 + x^9 + x^12 + x^15 + x^16 + x^17 + x^19 + ...
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
[Joerg Arndt, Aug 28 2011]
|
|
|
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 */
|
|
|
CROSSREFS
| See A014707, A014709, A014710 for other versions.
Cf. A038189, A082410, A059125, A065339.
A082410(n+2)=a(n).
A088748 [Gary W. Adamson, Aug 30 2009]
Cf. A091072 [Gary W. Adamson, Apr 11 2010]
Sequence in context: A100672 A079559 A175480 * A157926 A131377 A077049
Adjacent sequences: A014574 A014575 A014576 * A014578 A014579 A014580
|
|
|
KEYWORD
| nonn,easy,nice,changed
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Eric Weisstein (eric(AT)weisstein.com)
|
|
|
EXTENSIONS
| More terms from Ralf Stephan (ralf(AT)ark.in-berlin.de), Jul 03 2003
|
| |
|
|
