login
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.
3

%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