

A000975


a(2n) = 2*a(2n1), a(2n+1) = 2*a(2n)+1 (also a(n) is the nth number without consecutive equal binary digits).


149



0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381, 174762, 349525, 699050, 1398101, 2796202, 5592405, 11184810, 22369621, 44739242, 89478485, 178956970, 357913941, 715827882, 1431655765, 2863311530
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Might be called the "Lichtenberg sequence" after Georg Christoph Lichtenberg who discussed it in 1769 in connection with the Chinese Rings puzzle (baguenaudier). [Email from Andreas M. Hinz, Feb 15 2017]  N. J. A. Sloane, Feb 18 2017
Number of steps to change from a binary string of n 0's to n 1's using a Gray code.  Jon Stadler (jstadler(AT)coastal.edu)
Popular puzzles such as SpinOut and The Brain Puzzler are based on the Gray binary system and require a(n) steps to complete for some number n.
Conjecture: a(n) gives also all j for which A048702(j) = A000217(j), i.e., if we take a(n)th triangular number (a(n)^2 + a(n))/2 and multiply it by 3, we get a(n)th evenlength binary palindrome A048701(a(n)) concatenated from a(n) and its reverse. E.g., a(4) = 10, 1010 in binary, the tenth triangular number is 55, * 3 = 165 = 10100101 in binary.  Antti Karttunen, circa 1999. (This has been now proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.)  Antti Karttunen, Aug 31 2016
Number of ways to tie a tie of n or fewer half turns, excluding mirror images. Also number of walks of length n or less on a triangular lattice with the following restrictions; given l, r and c as the lattice axes. 1. All steps are taken in the positive axis direction. 2. No two consecutive steps are taken on the same axis. 3. All walks begin with l. 4. All walks end with rlc or lrc.  Bill Blewett, Dec 21 2000
a(n) = minimal number of vertices to be selected in a vertexcover of the balanced tree B_n.  Senpeng Eu, Jun 15 2002
A087117(a(n)) = A038374(a(n)) = 1 for n > 1; see also A090050.  Reinhard Zumkeller, Nov 20 2003
Intersection of A003754 and A003714; complement of A107911; a(n) = A107909(A104161(n)); A007088(a(n)) = A056830(n).  Reinhard Zumkeller, May 28 2005
a(n+1) gives row sums of Riordan array (1/(1x), x(1+2x)).  Paul Barry, Jul 18 2005
Total number of initial 01's in all binary words of length n+1. Example: a(3)=5 because the binary words of length 4 that start with 01 are (01)00, (01)(01), (01)10 and (01)11 and the total number of initial 01's is 5 (shown between parentheses). a(n) = Sum_{k>=0} k*A119440(n+1,k).  Emeric Deutsch, May 19 2006
2^n = 2*A005578(n1) + 2*A001045(n) + 2*a(n2).  Gary W. Adamson, Dec 25 2007
In Norway we call the 10ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts.  Hans Isdahl, Jan 07 2008
Equals A002450 and A020988 interlaced.  Zak Seidov, Feb 10 2008
For n > 1, let B_n = the complete binary tree with vertex set V where V = 2^n  1. If VC is a minimumsize vertex cover of B_n, SenPeng Eu points out that a(n) = VC. It also follows that if IS = V\VC, a(n+1) = IS.  K.V.Iyer, Apr 13 2009
Starting with 1 and convolved with [1, 2, 2, 2, ...] = A000295.  Gary W. Adamson, Jun 02 2009
a(n) written in base 2 is sequence A056830(n).  Jaroslav Krizek, Aug 05 2009
a(n)+ A001045(n) = A166920(n). a(n) + A001045(n+2) = A051049(n+1).  Paul Curtz, Oct 29 2009
This is the sequence A(0,1;1,2;1) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below.  Wolfdieter Lang, Oct 18 2010
From Vladimir Shevelev, Jan 30 2012, Feb 13 2012: (Start)
1) Denote by {n,k} the number of permutations of 1,...,n with the updown index k (for definition, see comment in A203827). Then max_k{n,k} = {n,a(n)} = A000111(n).
2) a(n) is the minimal number > a(n1) with the Hamming distance d_H(a(n1),a(n)) = n. Thus this sequence is the Hamming analog of triangular numbers 0,1,3,6,10,... (End)
From Hieronymus Fischer, Nov 22 2012: (Start)
Represented in binary form each term after the second one contains every previous term as a substring.
The terms a(2)=2 and a(3)=5 are the only primes. Proof: For even n we get a(n) = 2*(2^(2n)  1)/3, which shows that a(n) is even, too, and obviously a(n) > 2 for all even n > 2. For odd n we have a(n) = (2^(n+1)  1)/3 = (2^((n+1)/2)  1) * (2^((n+1)/2) + 1)/3. Evidently, at least one of these factors is divisible by 3, both are > 6, provided n > 3. Hence it follows that a(n) is composite for all odd n > 3.
Represented as a binary number, a(n+1) has exactly n prime substrings. Proof: Evidently, a(1)=1_2 has zero and a(2)=10_2 has 1 prime substring. Let n > 1. Written in binary, a(n+1) is 101010101...01 (if n+1 is odd) and is 101010101...10 (if n+1 is even) with n+1 digits. Only the 2 and 3digits substrings 10_2 (=2) and 101_2 (=5) are prime substrings. All the other substrings are nonprime since every substring is a previous term and all terms unequal to 2 and 5 are nonprime. For even n+1, the number of prime substrings equal to 2 = 10_2 is (n+1)/2, and the number of prime substrings equal to 5 = 101_2 is (n1)/2, makes a sum of n. For odd n+1 we get n/2 for both, the number of 2's and 5's prime substrings, in any case, the sum is n.
(End)
Also the number of different 3colorings for the vertices of all triangulated planar polygons on a base with n+2 vertices if the colors of the two base vertices are fixed.  Patrick Labarque, Feb 09 2013
A090079(a(n)) = a(n) and A090079(m) <> a(n) for m < a(n).  Reinhard Zumkeller, Feb 16 2013
a(n) is the number of length n binary words containing at least one 1 and ending in an even number (possibly zero) of 0's. a(3) = 5 because we have: 001, 011, 100, 101, 111.  Geoffrey Critzer, Dec 15 2013
a(n) is the number of permutations of length n+1 having exactly one descent such that the first element of the permutation is an even number.  Ran Pan, Apr 18 2015
a(n) is the sequency of the last row of the Hadamard matrix H(2^n) obtained via Sylvester's construction: H(2) = [1,1;1,1], H(2^n) = H(2^(n1))*H(2), where * is the Kronecker product.  William P. Orrick, Jun 28 2015
Conjectured record values of A264784: a(n) = A264784(A155051(n1)).  Reinhard Zumkeller, Dec 04 2015. (This is proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.)  Antti Karttunen, Aug 31 2016
Decimal representation of the xaxis, from the origin to the right edge, of the nth stage of growth of the twodimensional cellular automaton defined by "Rule 131", based on the 5celled von Neumann neighborhood. See A279053 for references and links.  Robert Price, Dec 05 2016
For n > 4, a(n2) is the secondlargest number in row n of A127824.  Dmitry Kamenetsky, Feb 11 2017


REFERENCES

Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.


LINKS

T. D. Noe, Table of n, a(n) for n=0..300
Sergei L. Bezrukov et al., The congestion of ncube layout on a rectangular grid, Discrete Mathematics 213.13 (2000): 1319. See Theorem 1.
F. Chapoton, S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv preprint arXiv:1310.4521 [math.CO], 2013. Is the sequence in Table 2 this sequence?  N. J. A. Sloane, Jan 04 2014. (Yes, it is. see Stockmeyer's arXiv:1608.08245 2016 paper for the proof).
David Hayes, Kaveh Khodjasteh, Lorenza Viola and Michael J. Biercuk, Reducing sequencing complexity in dynamical quantum error suppression by Walsh modulation, arXiv preprint arXiv:1109.6002 [quantph], 2011.
Andreas M. Hinz, The Lichtenberg sequence, Fib. Quart., 55 (2017), 212.
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi  Myths and Maths, Birkhäuser 2013. See page 56. Book's website
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 394
Hans Isdahl, "Knitwear" puzzle
D. E. Knuth and O. P. Lossers, Partitions of a circular set, Problem 11151 in Amer. Math. Monthly 114 (3) (2007) p 265, E_3.
S. Lafortune, A. Ramani, B. Grammaticos, Y. Ohta and K.M. Tamizhmani, Blending two discrete integrability criteria: singularity confinement and algebraic entropy, arXiv:nlin/0104020 [nlin.SI], 2001.
Robert L. Lamphere, A Recurrence Relation in the Spinout Puzzle, The College Mathematics Journal, Vol. 27, Nbr. 4, Page 289, Sep. 96.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
Kival Ngaokrajang, Illustration of initial terms
Vladimir Shevelev, On the Basis Polynomials in the Theory of Permutations with Prescribed UpDown Structure, arXiv:0801.0072 [math.CO], 20072010. See Example 3.
A. V. Sills and H. Wang, On the maximal Wiener index and related questions, Discrete Applied Mathematics, Volume 160, Issues 1011, July 2012, Pages 16151623  N. J. A. Sloane, Sep 21 2012
N. J. A. Sloane, Transforms
Paul K. Stockmeyer, An Exploration of Sequence A000975, arXiv:1608.08245 [math.CO], 2016; Fib. Quart. 55 (2017) 174
Eric Weisstein's World of Mathematics, Baguenaudier
A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.
Index entries for sequences related to binary expansion of n
Index entries for linear recurrences with constant coefficients, signature (2,1,2).


FORMULA

a(n) = ceiling(2*(2^n1)/3).
Alternating sum transform (PSumSIGN) of {2^n  1} (A000225).
a(n) = a(n1) + 2*a(n2) + 1.
a(n) = 2*2^n/3  1/2  (1)^n/6.
a(n) = Sum_{i=0..n} A001045(i), partial sums of A001045.  Bill Blewett
a(n) = n + 2*Sum_{k = 1..n2} a(k).
G.f.: x/((1+x)*(1x)*(12*x)) = x/(12*xx^2+2*x^3).  Paul Barry, Feb 11 2003
a(n) = 2*a(n1) + a(n2)  2*a(n3).  Paul Barry, Feb 11 2003
a(n) = Sum_{k=0..floor((n1)/2)} 2^(n2k1)}; a(n+1) = Sum_{k=0..floor(n/2)} 2^(n2k).  Paul Barry, Nov 11 2003
a(n+1) = Sum_{k=0..floor(n/2)} 2^(n2k); a(n+1) = Sum_{k=0..n} Sum_{j=0..k} (1)^(j+k)2^j.  Paul Barry, Nov 12 2003
(1)^(n+1)*a(n) = Sum_{i=0..n} Sum_{k=1..i} k!*k* Stirling2(i, k)*(1)^(k1) = (1/3)*(2)^(n+1)(1/6)(3*(1)^(n+1)1).  Mario Catalani (mario.catalani(AT)unito.it), Dec 22 2003
a(n+1) = (n!/3)*Sum_{i(1)^i+j=n, i=0..n, j=0..n} 1/(i(1)^i)!/j!.  Benoit Cloitre, May 24 2004
a(n) = A001045(n+1)  A059841(n).  Paul Barry, Jul 22 2004
a(n) = Sum_{k=0..n} 2^(nk1)*(1(1)^k).  Paul Barry, Jul 28 2004
a(n) = Sum_{k=0..n} binomial(k, nk+1)2^(nk); a(n) = Sum_{k=0..floor(n/2)} binomial(nk, k+1)2^k.  Paul Barry, Oct 07 2004
a(n) = floor(2^(n+1)/3) = ceiling(2^(n+1)/3)  1 = A005578(n+1)  1.  Paul Barry, Oct 08 2005
Convolution of "Number of fixed points in all 231avoiding involutions in S_n." (A059570) with "1n" (A024000), treating the result as if offset=0.  Graeme McRae, Jul 12 2006
a(n) = A081254(n)  2^n.  Philippe Deléham, Oct 15 2006
Equals row sums of triangle A130125.  Gary W. Adamson, May 11 2007
Starting (1, 2, 5, 10, 21, 42, ...), = row sums of triangle A135228.  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), a(n1)].  Gary W. Adamson, Dec 25 2007
If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*stirling2(k,j)*x^(mk) then a(n3) = (1)^(n1)*f(n,3,2), (n>=3).  Milan Janjic, Apr 26 2009
a(n) = floor(A051049(n+1)/3).  Gary Detlefs Dec 19 2010
a(n) = round((2^(n+2)3)/6) = floor((2^(n+1)1)/3) = round((2^(n+1)2)/3); a(n) = a(n2) + 2^(n1), n>1.  Mircea Merca, Dec 27 2010
a(n) = binary XOR of 2^k1 for k=0..n.  Paul D. Hanna, Nov 05 2011
E.g.f.: 2/3*exp(2*x)1/2*exp(x)1/6*exp(x) = 2/3*U(0); U(k)=13/(4*(2^k)4*(2^k)/(1+3*(1)^k 24*x*(2^k)/(8*x*(2^k)*(1)^k(k+1)/U(k+1)))); (continued fraction).  Sergei N. Gladkovskii, Nov 21 2011
Starting with "1" = triangle A059260 * [1, 2, 2, 2, ...] as a vector.  Gary W. Adamson, Mar 06 2012
a(n) = 2*(2^n  1)/3, for even n; a(n) = (2^(n+1)  1)/3 = (1/3)*(2^((n+1)/2)  1)*(2^((n+1)/2) + 1), for odd n.  Hieronymus Fischer, Nov 22 2012
a(n) + a(n+1) = 2^(n+1)  1.  Arie Bos, Apr 03 2013
G.f.: Q(0)/(3*(1x)), where Q(k)= 1  1/(4^k  2*x*16^k/(2*x*4^k  1/(1 + 1/(2*4^k  8*x*16^k/(4*x*4^k + 1/Q(k+1)))))); (continued fraction).  Sergei N. Gladkovskii, May 21 2013
floor(a(n+2)*3/5) = A077854(n), for n>=0.  Armands Strazds, Sep 21 2014
a(n) = (2^(n+1)  2 + (n mod 2))/3.  Paul Toms, Mar 18 2015
a(0) = 0, a(n) = 2*(a(n1)) + (n mod 2).  Paul Toms, Mar 18 2015
Binary: a(n) = (a(n1) shift left 1) + (a(n1))NOR(...11110).  Paul Toms, Mar 18 2015
Binary: for n>1, a(n) = 2*a(n1) OR a(n2).  Stanislav Sykora, Nov 12 2015
a(n) = A266613(n)  20*2^(n5), for n > 2.  Andres Cicuttin, Mar 31 2016
From Michael Somos, Jul 23 2017: (Start)
a(n) = (2^n)*a(n) for even n; a(n) = (2^(n+1))*a(n) + 1 for odd n.
0 = +a(n)*(+2 +4*a(n) 4*a(n+1)) + a(n+1)*(1 +a(n+1)) for all n in Z. (End)


EXAMPLE

a(4)=10 since 0001,0011,0010,0110,0111,0101,0100,1100,1101,1111 are the 10 binary strings switching 0000 to 1111.
a(3) = 1 because "lrc" is the only way to tie a tie with 3 half turns, namely, pass the business end of the tie behind the standing part to the left, bring across the front to the right, then behind to the center. The final motion of tucking the loose end down the front behind the "lr" piece is not considered a "step".
a(4) = 2 because "lrlc" is the only way to tie a tie with 4 half turns. Note that since the number of moves is even, the first step is to go to the left in front of the tie, not behind it. This knot is the standard "four in hand", the most commonly known men's tie knot. By contrast, the second most well known tie knot, the Windsor, is represented by "lcrlcrlc".
a(n) = 2^01 XOR 2^11 XOR 2^21 XOR 2^31 XOR ... XOR 2^n1.  Paul D. Hanna, Nov 05 2011
G.f. = x + 2*x^2 + 5*x^3 + 10*x^4 + 21*x^5 + 42*x^6 + 85*x^7 + 170*x^8 + ...


MAPLE

A000975 := proc(n) option remember; if n <= 1 then n else if n mod 2 = 0 then 2*A000975(n1) else 2*A000975(n1)+1 fi; fi; end;
seq(iquo(2^n, 3), n=1..33); # Zerinvary Lajos, Apr 20 2008
f:=n> if n mod 2 = 0 then (2^n1)/3 else (2^n2)/3; fi; [seq(f(n), n=0..40)]; # N. J. A. Sloane, Mar 21 2017


MATHEMATICA

f[n_] := Ceiling[2(2^n1)/3]; Array[f, 41, 0]
RecurrenceTable[{a[0]==0, a[1]==1, a[n]==a[n1]+2a[n2]+1}, a, {n, 40}] (* or *)
LinearRecurrence[{2, 1, 2}, {0, 1, 2}, 40] (* Harvey P. Dale, Aug 10 2013 *)
f[n_] := Block[{exp = n  2}, Sum[2^i, {i, exp, 0, 2}]]; Array[f, 33] (* Robert G. Wilson v, Oct 30 2015 *)
f[s_List] := Block[{a = s[[1]]}, Append[s, If[ OddQ@ Length@ s, 2a +1, 2a]]]; Nest[f, {0}, 32] (* Robert G. Wilson v, Jul 20 2017 *)


PROG

(PARI) {a(n) = if( n<0, 0, 2 * 2^n \ 3)}; /* Michael Somos, Sep 04 2006 */
(PARI) {a(n)=if(n<=0, 0, bitxor(a(n1), 2^n1))} /* Paul D. Hanna, Nov 05 2011 */
(PARI) concat(0, Vec(x/(12*xx^2+2*x^3) + O(x^100))) \\ Altug Alkan, Oct 30 2015
(PARI) {a(n) = (4*2^n  3  (1)^n) / 6}; /* Michael Somos, Jul 23 2017 */
(Haskell)
a000975 n = a000975_list !! n
a000975_list = 0 : 1 : map (+ 1)
(zipWith (+) (tail a000975_list) (map (* 2) a000975_list))
 Reinhard Zumkeller, Mar 07 2012
(MAGMA) [(2^(n+1)  2 + (n mod 2))/3: n in [0..40]]; // Vincenzo Librandi, Mar 18 2015


CROSSREFS

Partial sums of A001045.
Row sums of triangle A013580.
Equals A026644/2.
Union of A002450 and 2*A002450 (= A020988).  Robert G. Wilson v, Jun 09 2014
Column k=3 of A261139.
Cf. A000295, A005578, A015441, A026644, A043291, A053404, A059260, A077854, A119440, A127824, A130125, A135228, A155051, A179970, A264784.
Sequence in context: A243988 A279811 A279751 * A280148 A215410 A279668
Adjacent sequences: A000972 A000973 A000974 * A000976 A000977 A000978


KEYWORD

nonn,easy,nice


AUTHOR

Mira Bernstein, N. J. A. Sloane, Robert G. Wilson v, Sep 13 1996


EXTENSIONS

Additional comments from Barry E. Williams, Jan 10 2000


STATUS

approved



