%I #34 Feb 23 2022 22:51:44
%S 1,6,108,27876,1826942052,7846656369001524324,
%T 144745261873314177475604083946266324068,
%U 49254260310842419635956203183145610297351659359183114324190902443509341776996
%N 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 The first iterations of the dragon curve produce the following sequence of turns:
%C 1st iteration: L
%C 2nd iteration: L L R
%C 3rd iteration: L L R L L R R
%C 4th iteration: L L R L L R R L L L R R L R R
%C 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 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dragon_curve">Dragon curve</a>
%F Recursive, in base 2:
%F 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 Continuing (in base 2):
%F The n-th digit, d(n), of any element is given by A014577. The following algorithm can also be used:
%F Express n in the form k2^m with k odd.
%F d(n) = -1/2 mod(k,4) + 3/2
%F Explicit formula: the n-th element in the sequence is given by (in base 10):
%F 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 Asymptotic growth:
%F a(n) ~ 2^(2^n-2).
%F a(n)/2^(2^(n+1)-1)) ~ A143347 (paper-folding constant).
%e Recurrence:
%e a(0) = 1.
%e a(1) = 1|1|rev(not(1)) = 110.
%e a(2) = 110|1|rev(not(110)) = 1101|rev(001) = 1101100.
%e n-th digit:
%e d(1) = -(1/2)*(1 mod 4) + 3/2 = 1.
%e d(2) = -(1/2)*(1 mod 4) + 3/2 = 1 (since 2=2*1).
%e d(3) = -(1/2)*(3 mod 4) + 3/2 = 0.
%e Explicit formula:
%e 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 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 (Python)
%o a=[]
%o a.append('1')
%o def bnot(string):
%o nstring=''
%o for letter in string:
%o nstring+=str(-int(letter)+1)
%o return nstring
%o for i in range(10):
%o a.append(a[i]+'1'+bnot(a[i])[::-1])
%o print([int(i,2) for i in a])
%Y Cf. A014577, A348162.
%Y Cf. A060032 (terdragon turns in digits).
%K nonn,easy
%O 1,2
%A _Michal D. Kuczynski_, Sep 01 2020