

A106665


Alternate paperfolding (or alternate dragon curve) sequence.


3



1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

Regular dragon curve (A014577) sequence results from repeated folding of long strip of paper in half in the same direction, say right to left. This alternate dragon curve sequence results from repeated folding of long strip of paper in half in alternating directions, right to left, then left to right and so forth.
In the Wikipedia article "Dragon Curve" note the illustrated description under the heading "[Un]Folding the Dragon" and note that the 1's and 0's in the A106665 description correspond to the L and R folds in the Wikipedia discussion.  Robert Munafo, Jun 03 2010


REFERENCES

C. Davis and D. E. Knuth, Number Representations and Dragon Curves  II, Journal of Recreational Mathematics, Vol. 3, No. 3, 1970, pp. 133149
M. Gardner, "The Dragon Curve and Other Problems (Mathematical Games)", Scientific American, 1967, columns for March, April, July.
M. Gardner, "Mathematical Magic Show" (contains the dragon curve columns).
D. E. Knuth, "Art of Computer Programming," vol. 2, 3rd. ed., "Seminumerical > Algorithms," (section 4.1)


LINKS

Table of n, a(n) for n=0..104.
Joerg Arndt, Matters Computational (The Fxtbook), section 1.31.3.2 "The alternate paperfolding sequence", pp. 9092
William J. Gilbert, Fractal geometry derived from complex bases, The Mathematical Intelligencer, Volume 4, Number 2 (June 1982), pp. 7886 (ISSN 03436993; DOI 10.1007/BF03023486)
Wikipedia, Dragon curve


FORMULA

For n >= 0, a(4n) = 1, a(4n+2) = 0, a(2n+1) = 1  a(n).
(1)^a(n) = A209615(n+1).  Michael Somos, Mar 10 2012


EXAMPLE

1 + x^3 + x^4 + x^5 + x^8 + x^12 + x^13 + x^15 + x^16 + x^19 + x^20 + ...


MAPLE

a:= proc(n) option remember;
`if`(irem(n, 4)=0, 1, `if`(irem(n, 2)=1, 1a((n1)/2), 0))
end:
seq(a(n), n=0..120); # Alois P. Heinz, Mar 10 2012


PROG

(C++) /* "ulong" stands for "unsigned long" */
bool bit_paper_fold_alt(ulong k)
{
ulong h = k & k; // == lowest_one(k)
h <<= 1;
ulong t = h & (k ^ 0xaaaaaaaaUL); // 32bit version
return ( t!=0 );
} /* Joerg Arndt, Jun 03 2010 */
(PARI) {a(n) = n++; if( n==0, 0, v = valuation( n, 2); (n/2^v\2 + v+1) %2 )} /* Michael Somos, Mar 10 2012 */


CROSSREFS

Cf. A014577, A209615.
(1)^a(n) = A034947(n+1) * (1)^A096268(n).  Alec Edgington (alec(AT)obtext.com), Aug 02 2010
Sequence in context: A051341 A057211 A120531 * A004609 A071001 A072792
Adjacent sequences: A106662 A106663 A106664 * A106666 A106667 A106668


KEYWORD

easy,nonn


AUTHOR

Duane K. Allen (computeruser(AT)sprintmail.com), May 13 2005


EXTENSIONS

Edited by N. J. A. Sloane, Jun 04 2010 to include material from discussions on the Sequence Fans Mailing List.


STATUS

approved



