login
This site is supported by donations to The OEIS Foundation.

 

Logo


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)
46
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). [Email from Andreas M. Hinz, Feb 15 2017]. - N. J. A. Sloane, Feb 18 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-2k). 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-2x^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) = 1+2^(n-1)-a(n-1) = a(n-1)+2a(n-2)-1 = a(n-2)+2^(n-2). - Paul Curtz, Jan 31 2009

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

a(n)= 1 + floor((2^n)/3) (proof by mathematical induction)

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.

Andreas M. Hinz, The Lichtenberg sequence, Fib. Quart., 55 (2017), 2-12.

G. Manku, J. Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.

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

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.

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.

J. P. McSorley, Counting structures in the Moebius ladder, Discrete Math., 184 (1998), 137-164.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 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. - From N. J. A. Sloane, Sep 21 2012

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) = 2*a(n-1) + a(n-2) - 2*a(n-3).

a(n) = A001045(n)+A000035(n+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. - Paul Barry, Jul 20 2003

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[F(i)*a(n-4-i), i=0, n-4] where the F(i) are Fibonacci numbers. - 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(mod(j-k, 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

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 *)

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

CROSSREFS

Cf. A071922, A072176, A135229.

Bisections: A007583 and A047849.

Cf. A000975, (first differences) A001045.

Sequence in context: A226594 A043327 A247968 * A058050 A026418 A063895

Adjacent sequences:  A005575 A005576 A005577 * A005579 A005580 A005581

KEYWORD

easy,nonn

AUTHOR

N. J. A. Sloane

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 27 14:58 EDT 2017. Contains 288790 sequences.