A003230 -id:A003230 - cp's OEIS frontend

A003229 a(n) = a(n-1) + 2*a(n-3) with a(0)=a(1)=1, a(2)=3.

1, 1, 3, 5, 7, 13, 23, 37, 63, 109, 183, 309, 527, 893, 1511, 2565, 4351, 7373, 12503, 21205, 35951, 60957, 103367, 175269, 297183, 503917, 854455, 1448821, 2456655, 4165565, 7063207, 11976517, 20307647, 34434061, 58387095, 99002389

Offset: 0

N. J. A. Sloane

Equals eigensequence of an infinite lower triangular matrix with 1's in the main diagonal, 0's in the subdiagonal and 2's in the subsubdiagonal (the triangle in the lower section of A155761). - Gary W. Adamson, Jan 28 2009
The operation in the comment of Jan 28 2009 is equivalent to the INVERT transform of (1, 0, 2, 0, 0, 0, ...). - Gary W. Adamson, Jan 21 2017
For n>=1, a(n) equals the number of ternary words of length n-1 having at least 2 zeros between every two successive nonzero letters. - Milan Janjic, Mar 09 2015

D. E. Daykin and S. J. Tucker, Introduction to Dragon Curves. Unpublished, 1976. See links below for an earlier version.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
D. E. Daykin, Letter to N. J. A. Sloane, Dec 1973.
D. E. Daykin, Letter to N. J. A. Sloane, Mar 1974.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, page 1.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, page 2.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, page 3.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, page 4.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, reverse side of page 4.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 417.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Index entries for linear recurrences with constant coefficients, signature (1,0,2).

Cf. A077949, A077974. First differences of A003479. Partial sums of A052537. Equals |A077906(n)|+|A077906(n+1)|.

Cf. A155761, A003230.

a003229 n = a003229_list !! n
a003229_list = 1 : 1 : 3 : zipWith (+)
                           (map (* 2) a003229_list) (drop 2 a003229_list)
-- Reinhard Zumkeller, Jan 01 2014

I:=[1, 1, 3]; [n le 3 select I[n] else Self(n-1)+2*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 12 2012

seq(add(binomial(n-2*k,k)*2^k,k=0..floor(n/3)),n=1..38); # Zerinvary Lajos, Apr 03 2007
with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S), S=Sequence(U, card >= 1), U=Sequence(Z, card >=3)}, unlabeled]: seq(count(SeqSeqSeqL, size=n+4), n=0..35); # Zerinvary Lajos, Apr 04 2009
a := n -> `if`(n<3,[1,1,3][n+1], hypergeom([-n/3, -(1+n)/3, (1-n)/3], [-n/2, -(1+n)/2], -27/2)); seq(simplify(a(n)),n=0..35); # Peter Luschny, Mar 09 2015

LinearRecurrence[{1,0, 2},{1,1,3},40] (* Vincenzo Librandi, Jun 12 2012 *)

G.f.: (1+2*z^2)/(1-z-2*z^3). - Simon Plouffe in his 1992 dissertation
a(n) = A077949(n+1) = |A077974(n+1)|.
a(n) = u(n+1) - 3*u(n) + 2*u(n-1) where u(i) = A003230(i) [Daykin and Tucker]. - N. J. A. Sloane, Jul 08 2014
a(n) = hypergeom([-n/3,-(1+n)/3,(1-n)/3],[-n/2,-(1+n)/2],-27/2) for n>=3. - Peter Luschny, Mar 09 2015

A003477 Expansion of 1/((1-2x)(1+x^2)(1-x-2x^3)).

Original entry on oeis.org

1, 3, 6, 14, 33, 71, 150, 318, 665, 1375, 2830, 5798, 11825, 24039, 48742, 98606, 199113, 401455, 808382, 1626038, 3267809, 6562295, 13169814, 26416318, 52962681, 106145855, 212665582, 425965126, 853005201, 1707833095, 3418756806

Offset: 0

N. J. A. Sloane

The number of simple squares in the biggest 'cloud' of the Harter-Heighway dragon of degree (n+4). Equals the number of double points in the biggest 'cloud' of the very same. - Manfred Lindemann, Dec 06 2015

D. E. Daykin and S. J. Tucker, Introduction to Dragon Curves. Unpublished, 1976. See links in A003229 for an earlier version.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. E. Daykin, Letter to N. J. A. Sloane, Mar 1974
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Kevin Ryde, Iterations of the Dragon Curve, see index "BlobA".
Index entries for linear recurrences with constant coefficients, signature (3,-3,5,-6,2,-4).

Cf. A003230, A077949. - Manfred Lindemann, Dec 06 2015

Cf. A077854.

A003477:=1/(2*z-1)/(-1+z+2*z**3)/(1+z**2); # Simon Plouffe in his 1992 dissertation
S:=series(1/((1-x-2*x^3)*(1-2*x)*(1+x^2)), x, 101): a:=n->coeff(S, x, n):
seq(a(n), n=0..100); # Manfred Lindemann, Dec 06 2015
a:= gfun:-rectoproc({a(n) = 3*a(n-1)-3*a(n-2)+5*a(n-3)-6*a(n-4)+2*a(n-5)-4*a(n-6),seq(a(i)=[1,3,6,14,33,71][i+1],i=0..5)},a(n),remember):
seq(a(n),n=0..100); # Robert Israel, Dec 14 2015

CoefficientList[Series[1/((1-2x)(1+x^2)(1-x-2x^3)),{x,0,40}],x] (* Vincenzo Librandi, Jun 11 2012 *)
LinearRecurrence[{3, -3, 5, -6, 2, -4}, {1, 3, 6, 14, 33, 71}, 31] (* Arie Bos, Dec 03 2019 *)

Vec(1/((1-2*x)*(1+x^2)*(1-x-2*x^3))+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

a(0) = 1; for n > 0, a(n) = 3*a(n-1) - 3*a(n-2) + 5*a(n-3) - 6*a(n-4) + 2*a(n-5) - 4*a(n-6) (where a(n)=0 for -5 <= n <= -1). - Jon E. Schoenfield, Apr 23 2010
From Manfred Lindemann, Dec 06 2015: (Start)
a(n) = 3*a(n-1) - 2*a(n-2) + 2*a(n-3) - 4*a(n-4) + Re(i^(n-4)), a(-5)=a(-4)=a(-3)=a(-2)=0 for all integers n element Z.
a(n+2)+a(n) = A003230(n+2)-A003230(n+1). [Daykin and Tucker equation (5)]
With thrt:=(54+6*sqrt(87))^(1/3), ROR:=(thrt/6-1/thrt) and RORext:=(thrt/6+1/thrt) becomes ROC:=(1/2)*(i*sqrt(3)*RORext-ROR), where i^2=-1.
Now ROR, ROC and conjugate(ROC) are the zeros of 1-x-2*x^3.
With BR:=1/(2*ROR-3), BC:=1/(2*ROC-3) and the zeros of (1-2*x) and (1+x^2) becomes
a(n) = (1/2)*(BR*ROR^-(n+4) + BC*ROC^-(n+4) + conjugate(BC*ROC^-(n+4)) + (2/5)*(1/2)^-(n+4) + (3/10 + i*(1/10))*i^-(n+4) + conjugate((3/10 + i*(1/10))*i^-(n+4))).
Simplified: a(n) = (BR/2)*ROR^-(n+4) + Re(BC*ROC^-(n+4)) + (1/5)*(1/2)^-(n+4) + Re((3/10 + i*(1/10))*i^-(n+4)).
(End)
Conjecture: a(n) = A077854(n) + 2*(a(n-3) + a(n-4) + ... + a(1)). - Arie Bos, Nov 29 2019

More terms from Jon E. Schoenfield, Apr 23 2010

A227036 Expansion of 2(1+x^2)/((1-x)(1-x-2*x^3)).

Original entry on oeis.org

2, 4, 8, 16, 28, 48, 84, 144, 244, 416, 708, 1200, 2036, 3456, 5860, 9936, 16852, 28576, 48452, 82160, 139316, 236224, 400548, 679184, 1151636, 1952736, 3311108, 5614384, 9519860, 16142080, 27370852, 46410576, 78694740, 133436448, 226257604, 383647088, 650519988, 1103035200, 1870329380

Offset: 0

Roland Kneer, Jun 28 2013

Conjecture: The perimeter of the n-th iteration of the Harter-Heighway dragon is a(n) segments or a(n)/2^(n/2) base units.
a(n) = 2^(n+1)-4*A003230(n-4) (two times the number of segments, minus four times the number of squares)
The first differences 2, 2, 4, 8, 12, 20,.. are twice the (empirical) A203175. - R. J. Mathar, Jul 02 2013

			For the 4th iteration, take two 3rd iteration dragons (2*16); put together, they will make one square, so subtract the inner perimeter 4.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Kevin Ryde, Iterations of the Dragon Curve, see index "B" and "R".
Helena Verrill, On the Boundary of the Harter-Heighway dragon curve, arXiv:2407.17326 [math.CO], 2024.
Wikipedia, Dragon curve
Index entries for linear recurrences with constant coefficients, signature (2,-1,2,-2).

Cf. A014577.

LinearRecurrence[{2, -1, 2, -2}, {2, 4, 8, 16}, 40] (* T. D. Noe, Jul 02 2013 *)
CoefficientList[Series[2 (1 + x^2) / ((1 - x) (1 - x - 2 x^3)), {x, 0, 40}], x] (* Vincenzo Librandi, Jul 17 2013 *)

Vec(2*(1+x^2)/((1-x)*(1-x-2*x^3))+O(x^66)) \\ Joerg Arndt, Jul 01 2013

A339739 a(n) gives the number of squares in the n-th iteration of the Harter-Heighway dragon.

Original entry on oeis.org

0, 0, 0, 1, 4, 11, 30, 78, 205, 546, 1455, 4062, 11192, 31889, 88487, 254594, 710683, 2047705, 5711439, 16455169, 45894868, 132118562, 368149344, 1059171430, 2950384277, 8484556353

Offset: 1

Peter Kagey, Jan 05 2021

a(n) >= A003230(n-4) for n >= 4, and a(n) > A003230(n-4) for n >= 7.

			For n = 5, the fifth iteration of the Harter-Heighway dragon has a(5) = 4 squares, as illustrated below. All of the squares are 1 X 1.
    *---*
    |   |
*---*   *
|
*---*
    |
*---*---*   *---*   *---*
|   |   |   |   |   |   |
*---*   *---*---*---*   *---*
            |   |           |
        *---*---*       *---*
        |   |
        *---*
For n = 7, the seventh iteration of the Harter-Heighway dragon has a(7) = 30 squares, as illustrated below. It contains A003230(7) = 28 1 X 1 squares and two 2 X 2 squares.
       _   _
      |_|_| |_
   _   _|    _|
  |_|_|_
    |_|_|
      |_   _       _       _
   _   _|_|_|    _|_|    _|_|
  |_|_|_|_|_   _|_|_   _|_|_   _
    |_| |_| |_|_|_|_|_| |_| |_|_|
              |_|_|_|_        |_
           _   _|_| |_|        _|
          |_|_|_|_          |_|
            |_| |_|

Code Golf Stack Exchange user Domenico Modica, Eye test - How many squares are in this picture?
Wikipedia, Dragon Curve

A003230 gives the number of 1 X 1 squares.

a(17)-a(26) from Bert Dobbelaere, Jun 15 2024

cp's OEIS Frontend

A003229 a(n) = a(n-1) + 2*a(n-3) with a(0)=a(1)=1, a(2)=3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Formula

A003477 Expansion of 1/((1-2x)(1+x^2)(1-x-2x^3)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A227036 Expansion of 2*(1+x^2)/((1-x)*(1-x-2*x^3)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A339739 a(n) gives the number of squares in the n-th iteration of the Harter-Heighway dragon.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A227036 Expansion of 2(1+x^2)/((1-x)(1-x-2*x^3)).