A079583 a(n) = 3*2^n - n - 2.

1, 3, 8, 19, 42, 89, 184, 375, 758, 1525, 3060, 6131, 12274, 24561, 49136, 98287, 196590, 393197, 786412, 1572843, 3145706, 6291433, 12582888, 25165799, 50331622, 100663269, 201326564, 402653155, 805306338, 1610612705, 3221225440

Offset

0,2

Comments

Row sums of A132110. - Gary W. Adamson, Aug 09 2007

Consider the infinite sequence of strings x(1) = a, x(2) = aba, x(3) = ababbaba, ..., where x(n+1) = x(n).b^{n+1}.x(n), for n >= 1. Each x(n), for n >= 2, has borders x(1), x(2), ..., x(n-1), none of which cover x(n). The length of x(n+1) is 3*2^n-n-2. - William F. Smyth, Feb 29 2012

Number of edges in the rooted tree g[n] (n>=0) defined recursively in the following manner: denoting by P[n] the path on n vertices, we define g[0] =P[2] while g[n] (n>=1) is the tree obtained by identifying the roots of 2 copies of g[n-1] and one of the end-vertices of P[n+1]; the root of g[n] is defined to be the other end-vertex of P[n+1]. Roughly speaking, g[4], for example, is obtained from the planted full binary tree of height 5 by replacing the edges at the levels 1,2,3,4 with paths of lengths 4, 3, 2, and 1, respectively. - Emeric Deutsch, Aug 08 2013

References

T. Flouri, C. S. Iliopoulos, T. Kociumaka, S. P. Pissis, S. J. Puglisi, W. F. Smyth, W. Tyczynski, New and efficient approaches to the quasiperiodic characterization of a string, Proc. Prague Stringology Conf., 2012, 75-88.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Tomas Flouri, Costas S. Iliopoulos, Solon P. Pissis, W. F. Smyth, On approximate string covering (draft, 2012).

Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Formula

a(0)=1, a(n) = 2*a(n-1) + n;

Binomial transform of [1, 2, 3, 3, 3, ...]. - Gary W. Adamson, Aug 09 2007

G.f.: (x^2-x+1)/((1-2*x)*(1-x)^2) = 3*U(0)x, where U(k) = 1 - (k+2)/(3*2^k - 18*x*4^k/(6*x*2^k - (k+2)/U(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Jul 04 2012

a(n) = (A227712(n) - 1)/3 - Emeric Deutsch, Feb 18 2016

a(n) = A007283(n) - n - 2. - Miquel Cerda, Aug 07 2016

a(n) = A000225(n) + A000325(n). - Miquel Cerda, Aug 08 2016

Mathematica

lst={}; Do[AppendTo[lst, 3*2^n-n-2], {n, 0, 4!}]; lst (* Vladimir Joseph Stephan Orlovsky, Oct 25 2008 *)
LinearRecurrence[{4, -5, 2}, {1, 3, 8}, 40] (* Vincenzo Librandi, Jun 23 2012 *)

Prog

(PARI) a(n)=3<<n-n-2 \\ Charles R Greathouse IV, Feb 29 2012
(Magma) I:=[1, 3, 8]; [n le 3 select I[n] else 4*Self(n-1)-5*Self(n-2)+2*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 23 2012

Crossrefs

Cf. A000295, A132110, A227712, A083329 (first differences).

Sequence in context: A002318 A229198 A095681 * A357291 A099050 A065352

Adjacent sequences: A079580 A079581 A079582 * A079584 A079585 A079586

Keyword

nonn,easy

Author

Benoit Cloitre, Jan 25 2003

Status

approved