cp's OEIS Frontend

A337580 a(n) is the sequence of turns in the n-th iteration of the dragon curve encoded in binary (L=1, R=0) represented in decimal.

%I A337580 #38 Dec 22 2024 09:08:24
%S A337580 1,6,108,27876,1826942052,7846656369001524324,
%T A337580 144745261873314177475604083946266324068,
%U A337580 49254260310842419635956203183145610297351659359183114324190902443509341776996
%N A337580 a(n) is the sequence of turns in the n-th iteration of the dragon curve encoded in binary (L=1, R=0) represented in decimal.
%C A337580 The first iterations of the dragon curve produce the following sequence of turns:
%C A337580 1st iteration: L
%C A337580 2nd iteration: L L R
%C A337580 3rd iteration: L L R L L R R
%C A337580 4th iteration: L L R L L R R L L L R R L R R
%C A337580 Substituting L=1 and R=0 one obtains the sequence (1, 110, 1101100, ...). Finally the entries are interpreted as binary numbers. In decimal the result is: (1, 6, 108, ...).
%H A337580 Martin Gardner, <a href="http://www.jstor.org/stable/24931474">Mathematical Games</a>, Scientific American, volume 216 number 4, April 1967, pages 116-123. Page 118 "binary formulas" shown (and drawn) are a(n) written in binary (description in answer 3, pages 119-120).
%H A337580 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dragon_curve">Dragon curve</a>
%F A337580 Recursive, in base 2:
%F A337580 a(0) = 1; a(n) = a(n-1)|1|rev(not(a(n-1))), where | denotes concatenation, not() denotes binary not, and rev() denotes order reverse (e.g., rev(110) = 011).
%F A337580 Continuing (in base 2):
%F A337580 The n-th digit, d(n), of any element is given by A014577. The following algorithm can also be used:
%F A337580 Express n in the form k2^m with k odd.
%F A337580 d(n) = -1/2 mod(k,4) + 3/2
%F A337580 Explicit formula: the n-th element in the sequence is given by (in base 10):
%F A337580 a(n) = d(1)*2^(2^n-2) + d(2)*2^(2^n-3) + d(3)*2^(2*n-4) + ... + 2^n + ... + (1-d(3))*2^2 + (1-d(2))*2^1 + (1-d(1))*2^0.
%F A337580 Asymptotic growth:
%F A337580 a(n) ~ 2^(2^n-2).
%F A337580 a(n)/2^(2^n-1) ~ A143347 (paper-folding constant).
%e A337580 Recurrence:
%e A337580 a(0) = 1.
%e A337580 a(1) = 1|1|rev(not(1)) = 110.
%e A337580 a(2) = 110|1|rev(not(110)) = 1101|rev(001) = 1101100.
%e A337580 n-th digit:
%e A337580 d(1) = -(1/2)*(1 mod 4) + 3/2 = 1.
%e A337580 d(2) = -(1/2)*(1 mod 4) + 3/2 = 1 (since 2=2*1).
%e A337580 d(3) = -(1/2)*(3 mod 4) + 3/2 = 0.
%e A337580 Explicit formula:
%e A337580 a(3) = d(1)*2^6 + d(2)*2^5 + d(3)*2^4 + 2^3 + (1-d(3))*2^2 + (1-d(2))*2^1 + (1-d(1))*2^0 = 2^6 + 2^5 + 2^3 + 2^2 = 108.
%t A337580 a[1] = 1; a[n_] := a[n] = FromDigits[Join[(d = IntegerDigits[a[n - 1], 2]), {1}, 1 - Reverse[d]], 2]; Array[a, 8] (* _Amiram Eldar_, Sep 03 2020 *)
%o A337580 (Python)
%o A337580 a=[]
%o A337580 a.append('1')
%o A337580 def bnot(string):
%o A337580     nstring=''
%o A337580     for letter in string:
%o A337580         nstring+=str(-int(letter)+1)
%o A337580     return nstring
%o A337580 for i in range(10):
%o A337580     a.append(a[i]+'1'+bnot(a[i])[::-1])
%o A337580 print([int(i,2) for i in a])
%Y A337580 Cf. A014577, A348162.
%Y A337580 Cf. A060032 (terdragon turns in digits).
%K A337580 nonn,easy
%O A337580 1,2
%A A337580 _Michal D. Kuczynski_, Sep 01 2020