A343949 Shortest distance from curve start to end along the segments of dragon curve expansion level n, and which is the diameter of the curve as a graph.

1, 2, 4, 8, 12, 18, 26, 36, 52, 70, 102, 136, 200, 266, 394, 524, 780, 1038, 1550, 2064, 3088, 4114, 6162, 8212, 12308, 16406, 24598, 32792, 49176, 65562, 98330, 131100, 196636, 262174, 393246, 524320, 786464, 1048610, 1572898, 2097188, 3145764, 4194342, 6291494

Offset

0,2

Comments

Expansion level n is the first 2^n segments of the curve, and can be taken as a graph with visited points as vertices and segments as edges.

Links

Kevin Ryde, Table of n, a(n) for n = 0..1000

Kevin Ryde, Iterations of the Dragon Curve, see index "Diameter".

Index entries for linear recurrences with constant coefficients, signature (1,3,-3,-2,2).

Formula

a(0) = 1.

a(2*n) = 3*2^n + 2*n - 4 = 2*A275970(n-1), for n>=1.

a(2*n+1) = 4*2^n + 2*n - 2 = 2*A083706(n).

a(n+1) - a(n) = 2*A228693(n), for n>=1.

a(n) = a(n-1) + 3*a(n-2) - 3*a(n-3) - 2*a(n-4) + 2*a(n-5) for n >= 6.

G.f.: (1 + x - x^2 + x^3 - 4*x^5) / ((1+x) * (1-x)^2 * (1-2*x^2)).

G.f.: 2 - (1/2)/(1+x) - (9/2)/(1-x) + 1/(1-x)^2 + (3 + 4*x)/(1 - 2*x^2).

Example

Curve n=4:
     *--*  *--*
     |  |  |  |        Start S to end E along segments.
     *--*--*  *--*     Distance a(4) = 12,
        |        |     which is also graph diameter.
  E  *--*     S--*
  |  |
  *--*

Prog

(PARI) a(n) = if(n==0, 1, my(t=n%2); (3+t)<<(n>>1) + n-4 + t);

Crossrefs

Cf. A275970, A083706, A228693.

Cf. A332383, A332384 (curve coordinates).

Sequence in context: A293495 A330130 A053799 * A284122 A212585 A085891

Adjacent sequences: A343946 A343947 A343948 * A343950 A343951 A343952

Keyword

nonn,easy

Author

Kevin Ryde, May 05 2021

Status

approved