cp's OEIS Frontend

A106665 Alternate paper-folding (or alternate dragon curve) sequence.

%I A106665 #72 Feb 26 2025 01:58:48
%S A106665 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,
%T A106665 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,
%U A106665 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
%N A106665 Alternate paper-folding (or alternate dragon curve) sequence.
%C A106665 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.
%C A106665 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
%D A106665 M. Gardner, "The Dragon Curve and Other Problems (Mathematical Games)", Scientific American, 1967, columns for March, April, July.
%D A106665 M. Gardner, "Mathematical Magic Show" (contains the dragon curve columns).
%D A106665 D. E. Knuth, "Art of Computer Programming," vol. 2, 3rd. ed., "Seminumerical > Algorithms," (section 4.1)
%H A106665 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 1.31.3.2 "The alternate paper-folding sequence", pp. 90-92
%H A106665 Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves - II, Journal of Recreational Mathematics, Vol. 3, No. 3, 1970, pp. 133-149, see section 4. Reprinted in Donald E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~uno/fg.html">Selected Papers on Fun and Games</a>, 2011, pages 571-614.
%H A106665 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 A106665 William J. Gilbert, <a href="http://www.math.uwaterloo.ca/~wgilbert/Research/MathIntel.pdf">Fractal geometry derived from complex bases</a>, The Mathematical Intelligencer, Volume 4, Number 2 (June 1982), pp. 78-86. (ISSN 0343-6993; DOI 10.1007/BF03023486)
%H A106665 Kevin Ryde, <a href="http://user42.tuxfamily.org/alternate/index.html">Iterations of the Alternate Paperfolding Curve</a>, see index "TurnLpred" with a(n) = TurnLpred(n+1).
%H A106665 Wikipedia, <a href="http://en.wikipedia.org/wiki/Dragon_curve">Dragon curve</a>
%F A106665 For n >= 0, a(4n) = 1, a(4n+2) = 0, a(2n+1) = 1 - a(n).
%F A106665 (-1)^a(n) = -A034947(n+1) * (-1)^A096268(n). - Alec Edgington (alec(AT)obtext.com), Aug 02 2010
%F A106665 -(-1)^a(n) = A209615(n+1). - _Michael Somos_, Mar 10 2012
%F A106665 G.f.: 1/(1 - x^4) + Sum_{k>=1} x^(2*((-1 - (-2)^(k - 1)) mod 2^(k + 1)) + 1)/(1 - x^(2^(k + 2))). - _Miles Wilson_, Nov 18 2024
%e A106665 1 + x^3 + x^4 + x^5 + x^8 + x^12 + x^13 + x^15 + x^16 + x^19 + x^20 + ...
%p A106665 a:= proc(n) option remember;
%p A106665       `if`(irem(n, 4)=0, 1, `if`(irem(n, 2)=1, 1-a((n-1)/2), 0))
%p A106665     end:
%p A106665 seq(a(n), n=0..120);  # _Alois P. Heinz_, Mar 10 2012
%t A106665 a[n_] := a[n] = Switch[Mod[n, 4], 0, 1, 2, 0, _, 1-a[(n-1)/2]];
%t A106665 Table[a[n], {n, 0, 120}] (* _Jean-François Alcover_, Mar 15 2017 *)
%o A106665 (C++) /* "ulong" stands for "unsigned long" */
%o A106665 bool bit_paper_fold_alt(ulong k)
%o A106665 {
%o A106665    ulong h = k & -k; // == lowest_one(k)
%o A106665    h <<= 1;
%o A106665    ulong t = h & (k ^ 0xaaaaaaaaUL); // 32-bit version
%o A106665    return ( t!=0 );
%o A106665 } /* _Joerg Arndt_, Jun 03 2010 */
%o A106665 (PARI) {a(n) = n++; if( n==0, 0, v = valuation( n, 2); (n/2^v\2 + v+1) %2 )} /* _Michael Somos_, Mar 10 2012 */
%o A106665 (Python)
%o A106665 def A106665(n): return ((n+1>>(m:=(~(n+1)&n).bit_length()))+1>>1)+m&1 # _Chai Wah Wu_, Feb 25 2025
%Y A106665 Cf. A014577, A209615.
%Y A106665 Cf. A034947, A096268.
%K A106665 easy,nonn
%O A106665 0,1
%A A106665 Duane K. Allen (computeruser(AT)sprintmail.com), May 13 2005
%E A106665 Edited by _N. J. A. Sloane_, Jun 04 2010 to include material from discussions on the Sequence Fans Mailing List.