The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005578 a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1. (Formerly M0788) 55
 1, 1, 2, 3, 6, 11, 22, 43, 86, 171, 342, 683, 1366, 2731, 5462, 10923, 21846, 43691, 87382, 174763, 349526, 699051, 1398102, 2796203, 5592406, 11184811, 22369622, 44739243, 89478486, 178956971, 357913942, 715827883, 1431655766 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS Might be called the "Arima sequence" after Yoriyuki Arima who in 1769 constructed this sequence as the number of moves of the outer ring in the optimal solution for the Chinese Rings puzzle (baguenaudier). - Andreas M. Hinz, Feb 15 2017 Let u(k), v(k), w(k) be the 3 sequences defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1) = u(k) + v(k), v(k+1) = u(k) + w(k), w(k+1) = v(k) + w(k); let M(k) = Max(u(k), v(k), w(k)); then a(n) = M(n). - Benoit Cloitre, Mar 25 2002 Unimodal analog of Fibonacci numbers: a(n+1) = Sum_{k=0..n/2} A071922(n-k, n-2*k). Based on the observation that F_{n+1} = Sum_{k} binomial (n-k, k). - Michele Dondi (bik.mido(AT)tiscalinet.it), Jun 30 2002 Numbers n at which the length of the symmetric signed digit expansion of n with q=2 (i.e., the length of the representation of n in the (-1,0,1)_2 number system) increases. - Ralf Stephan, Jun 30 2003 Row sums of Riordan array (1/(1-x), x/(1-2*x^2)). - Paul Barry, Apr 24 2005 For n > 0, record-values of A107910: a(n) = A107910(A023548(n)). - Reinhard Zumkeller, May 28 2005 2^(n+1) = 2*a(n) + 2*A001045(n) + A000975(n-1); e.g., 2^6 = 64 = 2*a(5) + 2*A001045(5) + 2*A000975(4) = 2*11 + 2*11 + 2*10. Let a(n), A001045(n) and A000975(n-1) = the legs of a triangle (a, b, c). Then a(n-1), A001045(n-1) and A000975(n-2) = (S-c), (S-b), (S-a), where S = the triangle semiperimeter. Example: a(5), A001045(5) and A000975(4) = triangle (a, b, c) = (11, 11, 10). Then a(4), A001045(4), A000975(3) = (S-c), (S-b), (S-a) = (6, 5, 5). - Gary W. Adamson, Dec 24 2007 a(n) is the number of length-n binary representations of a nonnegative integer that is divisible by 3. The initial digits are allowed to be 0's. a(4) = 6 because we have 0000, 0011, 0110, 1001, 1100, 1111. - Geoffrey Critzer, Jan 13 2014 a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 0, 1; 0, 1, 1; 1, 1, 0] or of the 3 X 3 matrix [1, 1, 0; 1, 0, 1; 0, 1, 1]. - R. J. Mathar, Feb 04 2014 With 0 prefixed, this sequence is an autosequence of the first kind because the sequence of first differences A001045 is. Its companion is A052950. - Paul Curtz, Dec 18 2018, edited by M. F. Hasler, Dec 21 2018 Apparently, the sequence gives the distinct values taken by A129761, the first differences of fibbinary numbers. - Rémy Sigrist, Oct 26 2019 The sequence with offset 1 can be generated in three steps starting with A158780. First, put in alternate signs (1, -1, 1, -2, 2, -4, ...) and take the inverse; getting (1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, ...). Take the invert transform of the latter, resulting in the sequence. It follows from the inverti transform being 1, 1, 0, 1, 1, 2, 3, ... that (for example), a(9) = 171 = (1, 1, 0, 1, 1, 2, 3, 5, 8) dot (86, 43, 0, 11, 6, 6, 6, 5, 8) = (86 + 43 + 0 + 11 + 6 + 6 + 6 + 5 + 8). A similar procedure is shown in the Aug 08 2019 comment of A006356. - Gary W. Adamson, Feb 04 2022 REFERENCES R. K. Guy, Graphs and the strong law of small numbers. Graph theory, combinatorics and applications. Vol. 2 (Kalamazoo, MI, 1988), 597-614, Wiley-Intersci. Publ., Wiley, New York, 1991. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS Vincenzo Librandi, Table of n, a(n) for n = 0..1000 Joerg Arndt, Matters Computational (The Fxtbook), p. 315. Ji Young Choi, Ternary Modified Collatz Sequences And Jacobsthal Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.7.5. Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4. Fan Chung and Shlomo Sternberg, Mathematics and the Buckyball Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015. R. K. Guy, Letter to N. J. A. Sloane, Apr 08 1988 (annotated scanned copy, included with permission) C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393. Andreas M. Hinz, The Lichtenberg sequence, Fib. Quart., 55 (2017), 2-12. Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8. G. Manku and J. Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447. J. P. McSorley, Counting structures in the Moebius ladder, Discrete Math., 184 (1998), 137-164. Hans Olofsen, Blending functions based on trigonometric and polynomial approximations of the Fabius function, The Arctic University of Norway (Narvik, 2019). 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 A. V. Sills and H. Wang, On the maximal Wiener index and related questions, Discrete Applied Mathematics, Volume 160, Issues 10-11, July 2012, Pages 1615-1623. Eric Weisstein's World of Mathematics, Walsh Function Index entries for linear recurrences with constant coefficients, signature (2,1,-2). FORMULA a(n) = ceiling(2^n/3). a(n) = 1 + floor((2^n)/3) (proof by mathematical induction). a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3). From Paul Barry, Jul 20 2003: (Start) a(n) = A001045(n) + A000035(n+1), where A000035 = (0, 1, 0, 1, ...). G.f.: (1 - x - x^2)/((1-x^2)*(1-2*x)) [Guy, 1988]; E.g.f.: (exp(2*x) - exp(-x))/3 + cosh(x) = (2*exp(2*x) + 3*exp(x) + exp(-x))/6. (End) The 30 listed terms are given by a(0)=1, a(1)=1 and, for n > 1, by a(n) = a(n-1) + a(n-2) + Sum_{i=0..n-4} Fibonacci(i)*a(n-4-i). - John W. Layman, Jan 07 2000 a(n) = (2^(n+1) + 3 + (-1)^n)/6. - Vladeta Jovovic, Jul 02 2002 Binomial transform of A001045(n-1)(-1)^n + 0^n/2. - Paul Barry, Apr 28 2004 a(n) = (1 + A001045(n+1))/2. - Paul Barry, Apr 28 2004 a(n) = Sum_{k=0..n} (-1)^k*Sum_{j=0..n-k} (if((j-k) mod 2)=0, binomial(n-k, j), 0). - Paul Barry, Jan 25 2005 Let M = the 6 X 6 adjacency matrix of a benzene ring, (reference): [0,1,0,0,0,1; 1,0,1,0,0,0; 0,1,0,1,0,0; 0,0,1,0,1,0; 0,0,0,1,0,1; 1,0,0,0,1,0]. Then a(n) = leftmost nonzero term of M^n * [1,0,0,0,0,0]. E.g.: a(6) = 22 since M^6 * [1,0,0,0,0,0] = [22,0,21,0,21,0]. - Gary W. Adamson, Jun 14 2006 Starting (1, 2, 3, 6, 11, 22, ...), = row sums of triangle A135229. - Gary W. Adamson, Nov 23 2007 Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0] = [A005578(n), A001045(n), A000975(n-1)]. - Gary W. Adamson, Dec 24 2007 a(n) = 1 + 2^(n-1) - a(n-1) = a(n-1) + 2*a(n-2) - 1 = a(n-2) + 2^(n-2). - Paul Curtz, Jan 31 2009 a(n) = A023105(n+1) - 1. - Carl Joshua Quines, Jul 17 2019 MAPLE A005578:=-(-1+z+z^2)/((z-1)*(2*z-1)*(z+1)); # Simon Plouffe in his 1992 dissertation with(combstruct):ZL0:=S=Prod(Sequence(Prod(a, Sequence(b))), a):ZL1:=Prod(begin_blockP, Z, end_blockP):ZL2:=Prod(begin_blockLR, Z, Sequence(Prod(mu_length, Z), card>=1), end_blockLR): ZL3:=Prod(begin_blockRL, Sequence(Prod(mu_length, Z), card>=1), Z, end_blockRL):Q:=subs([a=Union(ZL3), b=ZL3], ZL0), begin_blockP=Epsilon, end_blockP=Epsilon, begin_blockLR=Epsilon, end_blockLR=Epsilon, begin_blockRL=Epsilon, end_blockRL=Epsilon, mu_length=Epsilon:temp15:=draw([S, {Q}, unlabelled], size=15):seq(count([S, {Q}, unlabelled], size=n), n=2..34); # Zerinvary Lajos, Mar 08 2008 MATHEMATICA a=0; Table[a=2^n-a; (a/2+1)/2, {n, 5!}] (* Vladimir Joseph Stephan Orlovsky, Nov 22 2009 *) LinearRecurrence[{2, 1, -2}, {1, 1, 2}, 40] (* G. C. Greubel, Aug 26 2019 *) PROG (Magma) [(2^(n+1)+3+(-1)^n)/6: n in [0..40]]; // Vincenzo Librandi, Aug 14 2011 (PARI) a(n)=(2^(n+1)+3+(-1)^n)/6 \\ Charles R Greathouse IV, Mar 22 2016 (GAP) List([0..40], n->(2^(n+1)+3+(-1)^n)/6); # Muniru A Asiru, Dec 22 2018 (Sage) [(2^(n+1)+3+(-1)^n)/6 for n in (0..40)] # G. C. Greubel, Aug 26 2019 (Python) print([1+2**n//3 for n in range(40)])  # Gennady Eremin, Feb 05 2022 CROSSREFS Cf. A071922, A072176, A135229. Bisections: A007583 and A047849. Cf. also A000975, A001045 (first differences), A129761. Cf. A006356. Sequence in context: A226594 A043327 A247968 * A058050 A026418 A063895 Adjacent sequences:  A005575 A005576 A005577 * A005579 A005580 A005581 KEYWORD easy,nonn AUTHOR EXTENSIONS Edited by N. J. A. Sloane, Jun 20 2015. STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 30 21:21 EDT 2022. Contains 357106 sequences. (Running on oeis4.)