cp's OEIS Frontend

A005578 a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.

%I A005578 M0788 #221 Jun 24 2025 11:25:02
%S A005578 1,1,2,3,6,11,22,43,86,171,342,683,1366,2731,5462,10923,21846,43691,
%T A005578 87382,174763,349526,699051,1398102,2796203,5592406,11184811,22369622,
%U A005578 44739243,89478486,178956971,357913942,715827883,1431655766,2863311531,5726623062,11453246123
%N A005578 a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.
%C A005578 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
%C A005578 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
%C A005578 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
%C A005578 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
%C A005578 Row sums of Riordan array (1/(1-x), x/(1-2*x^2)). - _Paul Barry_, Apr 24 2005
%C A005578 For n > 0, record-values of A107910: a(n) = A107910(A023548(n)). - _Reinhard Zumkeller_, May 28 2005
%C A005578 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
%C A005578 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
%C A005578 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
%C A005578 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
%C A005578 Apparently, the sequence gives the distinct values taken by A129761, the first differences of fibbinary numbers. - _Rémy Sigrist_, Oct 26 2019
%C A005578 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
%D A005578 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.
%D A005578 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005578 Vincenzo Librandi, <a href="/A005578/b005578.txt">Table of n, a(n) for n = 0..1000</a>
%H A005578 Sujith Uthsara Kalansuriya Arachchi, Hung Viet Chu, Jiasen Liu, Qitong Luan, Rukshan Marasinghe, and Steven J. Miller, <a href="https://arxiv.org/abs/2309.04488">On a Pair of Diophantine Equations</a>, arXiv:2309.04488 [math.NT], 2023.
%H A005578 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 315.
%H A005578 Ji Young Choi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Choi/choi6.html">Ternary Modified Collatz Sequences And Jacobsthal Numbers</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.7.5.
%H A005578 Ji Young Choi, <a href="https://www.emis.de/journals/JIS/VOL21/Choi/choi10.html">A Generalization of Collatz Functions and Jacobsthal Numbers</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
%H A005578 Fan Chung and Shlomo Sternberg, <a href="http://www.math.ucsd.edu/~fan/amer.pdf">Mathematics and the Buckyball</a>
%H A005578 Johann Cigler, <a href="http://arxiv.org/abs/1501.04750">Some remarks and conjectures related to lattice paths in strips along the x-axis</a>, arXiv:1501.04750 [math.CO], 2015.
%H A005578 Johann Cigler, <a href="https://arxiv.org/abs/2212.02118">Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials</a>, arXiv:2212.02118 [math.NT], 2022.
%H A005578 Madeleine Goertz and Aaron Williams, <a href="https://arxiv.org/abs/2411.19291">The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles</a>, arXiv:2411.19291 [math.CO], 2024. See pp. 6, 17.
%H A005578 R. K. Guy, <a href="/A259095/a259095.pdf">Letter to N. J. A. Sloane, Apr 08 1988</a> (annotated scanned copy, included with permission)
%H A005578 Clemens Heuberger and Helmut Prodinger, <a href="http://dx.doi.org/10.1007/s006070170021">On minimal expansions in redundant number systems: Algorithms and quantitative analysis</a>, Computing 66(2001), 377-393.
%H A005578 Andreas M. Hinz, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/55-1/Hinz09152016.pdf">The Lichtenberg sequence</a>, Fib. Quart., 55 (2017), 2-12.
%H A005578 Andreas M. Hinz and Paul K. Stockmeyer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Hinz/hinz5.html">Precious Metal Sequences and Sierpinski-Type Graphs</a>, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
%H A005578 Gurmeet Singh Manku and Joe Sawada, <a href="http://www.cis.uoguelph.ca/~sawada/papers/esa-loopless.pdf">A loopless Gray code for minimal signed-binary representations</a>, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.
%H A005578 Thor Martinsen, <a href="https://doi.org/10.7546/nntdm.2025.31.2.370-389">Non-Fisherian generalized Fibonacci numbers</a>, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See pp. 385, 387.
%H A005578 John P. McSorley, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00086-1">Counting structures in the Moebius ladder</a>, Discrete Math., 184 (1998), 137-164.
%H A005578 Hans Olofsen, <a href="https://ojs.bibsys.no/index.php/NIK/article/view/644/525">Blending functions based on trigonometric and polynomial approximations of the Fabius function</a>, The Arctic University of Norway (Narvik, 2019).
%H A005578 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A005578 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H A005578 Chloe E. Shiff and Noah A. Rosenberg, <a href="https://arxiv.org/abs/2410.14915">Enumeration of rooted binary perfect phylogenies</a>, arXiv:2410.14915 [q-bio.PE], 2024. See p. 16.
%H A005578 Andrew V. Sills and Hua Wang, <a href="http://dx.doi.org/10.1016/j.dam.2012.03.002">On the maximal Wiener index and related questions</a>, Discrete Applied Mathematics, Volume 160, Issues 10-11, July 2012, Pages 1615-1623.
%H A005578 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WalshFunction.html">Walsh Function</a>
%H A005578 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2).
%F A005578 a(n) = ceiling(2^n/3).
%F A005578 a(n) = 1 + floor((2^n)/3) (proof by mathematical induction).
%F A005578 a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).
%F A005578 From _Paul Barry_, Jul 20 2003: (Start)
%F A005578 a(n) = A001045(n) + A000035(n+1), where A000035 = (0, 1, 0, 1, ...).
%F A005578 G.f.: (1 - x - x^2)/((1-x^2)*(1-2*x)). [Guy, 1988];
%F A005578 E.g.f.: (exp(2*x) - exp(-x))/3 + cosh(x) = (2*exp(2*x) + 3*exp(x) + exp(-x))/6. (End)
%F A005578 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
%F A005578 a(n) = (2^(n+1) + 3 + (-1)^n)/6. - _Vladeta Jovovic_, Jul 02 2002
%F A005578 Binomial transform of A001045(n-1)(-1)^n + 0^n/2. - _Paul Barry_, Apr 28 2004
%F A005578 a(n) = (1 + A001045(n+1))/2. - _Paul Barry_, Apr 28 2004
%F A005578 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
%F A005578 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
%F A005578 Starting (1, 2, 3, 6, 11, 22, ...), = row sums of triangle A135229. - _Gary W. Adamson_, Nov 23 2007
%F A005578 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
%F A005578 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
%F A005578 a(n) = A023105(n+1) - 1. - _Carl Joshua Quines_, Jul 17 2019
%p A005578 A005578:=-(-1+z+z^2)/((z-1)*(2*z-1)*(z+1)); # _Simon Plouffe_ in his 1992 dissertation
%p A005578 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
%t A005578 a=0; Table[a=2^n-a;(a/2+1)/2,{n,5!}] (* _Vladimir Joseph Stephan Orlovsky_, Nov 22 2009 *)
%t A005578 LinearRecurrence[{2,1,-2}, {1,1,2}, 40] (* _G. C. Greubel_, Aug 26 2019 *)
%o A005578 (Magma) [(2^(n+1)+3+(-1)^n)/6: n in [0..40]]; // _Vincenzo Librandi_, Aug 14 2011
%o A005578 (PARI) a(n)=(2^(n+1)+3+(-1)^n)/6 \\ _Charles R Greathouse IV_, Mar 22 2016
%o A005578 (GAP) List([0..40],n->(2^(n+1)+3+(-1)^n)/6); # _Muniru A Asiru_, Dec 22 2018
%o A005578 (Sage) [(2^(n+1)+3+(-1)^n)/6 for n in (0..40)] # _G. C. Greubel_, Aug 26 2019
%o A005578 (Python)
%o A005578 print([1+2**n//3 for n in range(40)])  # _Gennady Eremin_, Feb 05 2022
%Y A005578 Cf. A071922, A072176, A135229.
%Y A005578 Bisections: A007583 and A047849.
%Y A005578 Cf. also A000975, A001045 (first differences), A129761.
%Y A005578 Cf. A006356.
%K A005578 easy,nonn
%O A005578 0,3
%A A005578 _N. J. A. Sloane_
%E A005578 Edited by _N. J. A. Sloane_, Jun 20 2015