Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #501 Dec 10 2024 11:13:48
%S 0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690,
%T 87381,174762,349525,699050,1398101,2796202,5592405,11184810,22369621,
%U 44739242,89478485,178956970,357913941,715827882,1431655765,2863311530,5726623061,11453246122
%N a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).
%C Might be called the "Lichtenberg sequence" after Georg Christoph Lichtenberg, who discussed it in 1769 in connection with the Chinese Rings puzzle (baguenaudier). - _Andreas M. Hinz_, Feb 15 2017
%C 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)
%C Popular puzzles such as Spin-Out and The Brain Puzzler are based on the Gray binary system and require a(n) steps to complete for some number n.
%C Conjecture: {a(n)} also gives all j for which A048702(j) = A000217(j); i.e., if we take the a(n)-th triangular number (a(n)^2 + a(n))/2 and multiply it by 3, we get a(n)-th even-length binary palindrome A048701(a(n)) concatenated from a(n) and its reverse. E.g., a(4) = 10, which is 1010 in binary; the tenth triangular number is 55, and 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
%C 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
%C a(n) is the minimal number of vertices to be selected in a vertex-cover of the balanced tree B_n. - _Sen-peng Eu_, Jun 15 2002
%C A087117(a(n)) = A038374(a(n)) = 1 for n > 1; see also A090050. - _Reinhard Zumkeller_, Nov 20 2003
%C Intersection of A003754 and A003714; complement of A107907. - _Reinhard Zumkeller_, May 28 2005
%C Equivalently, numbers m whose binary representation is effectively, for some number k, both the lazy Fibonacci and the Zeckendorf representation of k (in which case k = A022290(m)). - _Peter Munn_, Oct 06 2022
%C a(n+1) gives row sums of Riordan array (1/(1-x), x(1+2x)). - _Paul Barry_, Jul 18 2005
%C 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
%C In Norway we call the 10-ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts. - _Hans Isdahl_, Jan 07 2008
%C Equals A002450 and A020988 interlaced. - _Zak Seidov_, Feb 10 2008
%C For n > 1, let B_n = the complete binary tree with vertex set V where |V| = 2^n - 1. If VC is a minimum-size vertex cover of B_n, Sen-Peng 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
%C Starting with 1 and convolved with [1, 2, 2, 2, ...] = A000295. - _Gary W. Adamson_, Jun 02 2009
%C a(n) written in base 2 is sequence A056830(n). - _Jaroslav Krizek_, Aug 05 2009
%C 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
%C From _Vladimir Shevelev_, Jan 30 2012, Feb 13 2012: (Start)
%C 1) Denote by {n, k} the number of permutations of 1, ..., n with the up-down index k (for definition, see comment in A203827). Then max_k{n, k} = {n, a(n)} = A000111(n).
%C 2) a(n) is the minimal number > a(n-1) with the Hamming distance d_H(a(n-1), a(n)) = n. Thus this sequence is the Hamming analog of triangular numbers 0, 1, 3, 6, 10, ... (End)
%C From _Hieronymus Fischer_, Nov 22 2012: (Start)
%C Represented in binary form each term after the second one contains every previous term as a substring.
%C The terms a(2) = 2 and a(3) = 5 are the only primes. Proof: For even n we get a(n) = 2*(2^(2*n) - 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 greater than 6, provided n > 3. Hence it follows that a(n) is composite for all odd n > 3.
%C 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 3-digits 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 (n-1)/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.
%C (End)
%C Also the number of different 3-colorings 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
%C A090079(a(n)) = a(n) and A090079(m) <> a(n) for m < a(n). - _Reinhard Zumkeller_, Feb 16 2013
%C 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
%C 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
%C a(n) is the sequence 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^(n-1))*H(2), where * is the Kronecker product. - _William P. Orrick_, Jun 28 2015
%C Conjectured record values of A264784: a(n) = A264784(A155051(n-1)). - _Reinhard Zumkeller_, Dec 04 2015. (This is proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - _Antti Karttunen_, Aug 31 2016
%C Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 131", based on the 5-celled von Neumann neighborhood. See A279053 for references and links. - _Robert Price_, Dec 05 2016
%C For n > 4, a(n-2) is the second-largest number in row n of A127824. - _Dmitry Kamenetsky_, Feb 11 2017
%C Conjecture: a(n+1) is the number of compositions of n with two kinds of parts, n and n', where the order of the 1 and 1' does not matter. For n=2, a(3) = 5 compositions, enumerated as follows: 2; 2'; 1,1; 1',1 = 1',1; 1',1'. - _Gregory L. Simay_, Sep 02 2017
%C Conjecture proved by recognizing the appropriate g.f. is x/(1 - x)(1 - x)(1 - 2*x^2 - 2x^3 - ...) = x/(1 - 2*x - x^2 + 2x^3). - _Gregory L. Simay_, Sep 10 2017
%C a(n) = 2^(n-1) + 2^(n-3) + 2^(n-5) + ... a(2*k -1) = A002450(k) is the sum of the powers of 4. a(2*k) = 2*A002450(k). - _Gregory L. Simay_, Sep 27 2017
%C a(2*n) = n times the string [10] in binary representation, a(2*n+1) = n times the string [10] followed with [1] in binary representation. Example: a(7) = 85 = (1010101) in binary, a(8) = 170 = (10101010) in binary. - _Ctibor O. Zizka_, Nov 06 2018
%C Except for 0, these are the positive integers whose binary expansion has cuts-resistance 1. For the operation of shortening all runs by 1, cuts-resistance is the number of applications required to reach an empty word. Cuts-resistance 2 is A329862. - _Gus Wiseman_, Nov 27 2019
%C From _Markus Sigg_, Sep 14 2020: (Start)
%C Let s(k) be the length of the Collatz orbit of k, e.g. s(1) = 1, s(2) = 2, s(3) = 5. Then s(a(n)) = n+3 for n >= 3. Proof by induction: s(a(3)) = s(5) = 6 = 3+3. For odd n >= 5 we have s(a(n)) = s(4*a(n-2)+1) = s(12*a(n-2)+4)+1 = s(3*a(n-2)+1)+3 = s(a(n-2))+2 = (n-2)+3+2 = n+3, and for even n >= 4 this gives s(a(n)) = s(2*a(n-1)) = s(a(n-1))+1 = (n-1)+3+1 = n+3.
%C Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)
%C From _Gary W. Adamson_, May 14 2021: (Start)
%C With offset 1 the sequence equals the numbers of 1's from n = 1 to 3, 3 to 7, 7 to 15, ...; of A035263; as shown below:
%C ..1 3 7 15...
%C ..1 0 1 1 1 0 1 0 1 0 1 1 1 0 1...
%C ..1.....2...........5......................10...; a(n) = Sum_(k=1..2n-1)A035263(k)
%C .....1...........2.......................5...; as to zeros.
%C ..1's in the Tower of Hanoi game represent CW moves On disks in the pattern:
%C ..0, 1, 2, 0, 1, 2, ... whereas even numbered disks move in the pattern:
%C ..0, 2, 1, 0, 2, 1, ... (End)
%C Except for 0, numbers that are repunits in Gray-code representation (A014550). - _Amiram Eldar_, May 21 2021
%C From _Gus Wiseman_, Apr 20 2023: (Start)
%C Also the number of nonempty subsets of {1..n} with integer median, where the median of a multiset is the middle part in the odd-length case, and the average of the two middle parts in the even-length case. For example, the a(1) = 1 through a(4) = 10 subsets are:
%C {1} {1} {1} {1}
%C {2} {2} {2}
%C {3} {3}
%C {1,3} {4}
%C {1,2,3} {1,3}
%C {2,4}
%C {1,2,3}
%C {1,2,4}
%C {1,3,4}
%C {2,3,4}
%C The complement is counted by A005578.
%C For mean instead of median we have A051293, counting empty sets A327475.
%C For normal multisets we have A056450, strongly normal A361202.
%C For partitions we have A325347, strict A359907, complement A307683.
%C (End)
%D Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.
%D Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.
%H G. C. Greubel, <a href="/A000975/b000975.txt">Table of n, a(n) for n = 0..3300</a> (terms 0..300 from T. D. Noe)
%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.
%H Thomas Baruchel, <a href="https://arxiv.org/abs/1908.02250">Properties of the cumulated deficient binary digit sum</a>, arXiv:1908.02250 [math.NT], 2019.
%H Sergei L. Bezrukov et al., <a href="https://doi.org/10.1016/S0012-365X(99)00162-4">The congestion of n-cube layout on a rectangular grid</a>, Discrete Mathematics 213.1-3 (2000): 13-19. See Theorem 1.
%H F. Chapoton and S. Giraudo, <a href="http://arxiv.org/abs/1310.4521">Enveloping operads and bicoloured noncrossing configurations</a>, 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.)
%H 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 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 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. 1, 17, 42.
%H David Hayes, Kaveh Khodjasteh, Lorenza Viola and Michael J. Biercuk, <a href="http://arxiv.org/abs/1109.6002">Reducing sequencing complexity in dynamical quantum error suppression by Walsh modulation</a>, arXiv:1109.6002 [quant-ph], 2011.
%H Clemens Heuberger and Daniel Krenn, <a href="https://arxiv.org/abs/1808.00842">Esthetic Numbers and Lifting Restrictions on the Analysis of Summatory Functions of Regular Sequences</a>, arXiv:1808.00842 [math.CO], 2018. See p. 10.
%H Clemens Heuberger and Daniel Krenn, <a href="https://arxiv.org/abs/1810.13178">Asymptotic Analysis of Regular Sequences</a>, arXiv:1810.13178 [math.CO], 2018. See p. 29.
%H Andreas M. Hinz, <a href="https://www.fq.math.ca/Papers1/55-1/Hinz09152016.pdf">The Lichtenberg sequence</a>, Fib. Quart., 55 (2017), 2-12.
%H Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 56. <a href="http://tohbook.info">Book's website</a>
%H 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 Jia Huang, <a href="https://arxiv.org/abs/2001.05547">Nonassociativity of the Norton Algebras of some distance regular graphs</a>, arXiv:2001.05547 [math.CO], 2020.
%H Jia Huang, <a href="https://arxiv.org/abs/2101.05711">Norton algebras of the Hamming Graphs via linear characters</a>, arXiv:2101.05711 [math.CO], 2021.
%H Jia Huang and Erkko Lehtonen, <a href="https://arxiv.org/abs/2401.15786">Associative-commutative spectra for some varieties of groupoids</a>, arXiv:2401.15786 [math.CO], 2024. See p. 17.
%H Jia Huang, Madison Mickey, and Jianbai Xu, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Huang/huang3.html">The Nonassociativity of the Double Minus Operation</a>, Journal of Integer Sequences, Vol. 20 (2017), #17.10.3.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=394">Encyclopedia of Combinatorial Structures 394</a>
%H Hans Isdahl, <a href="/A000975/a000975.jpg">"Knitwear" puzzle</a>
%H D. E. Knuth and O. P. Lossers, <a href="http://www.jstor.org/stable/27642185">Partitions of a circular set</a>, Problem 11151 in Amer. Math. Monthly 114 (3) (2007) p 265, E_3.
%H S. Lafortune, A. Ramani, B. Grammaticos, Y. Ohta and K.M. Tamizhmani, <a href="http://arXiv.org/abs/nlin.SI/0104020">Blending two discrete integrability criteria: singularity confinement and algebraic entropy</a>, arXiv:nlin/0104020 [nlin.SI], 2001.
%H Robert L. Lamphere, <a href="http://www.maa.org/sites/default/files/0746834214182.di020773.02p0248n.pdf">A Recurrence Relation in the Spinout Puzzle</a>, The College Mathematics Journal, Vol. 27, Nbr. 4, Page 289, Sep. 96.
%H Wolfdieter Lang, <a href="/A000975/a000975.pdf">Notes on certain inhomogeneous three term recurrences.</a>
%H Georg Christoph Lichtenberg, <a href="https://play.google.com/store/books/details?id=8FAmAAAAMAAJ">Vermischte Schriften, Band 6</a> (1805). See chapter 6, <a href="https://play.google.com/books/reader?id=8FAmAAAAMAAJ&printsec=frontcover&source=gbs_atb_hover&pg=GBS.PA256">p. 257</a>.
%H Saad Mneimneh, <a href="http://www.cs.hunter.cuny.edu/~saad/teaching/ToH.pdf">Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction</a>, Department of Computer Science, Hunter College, CUNY, 2019.
%H Richard Moot, <a href="https://arxiv.org/abs/2008.06351">Partial Orders, Residuation, and First-Order Linear Logic</a>, arXiv:2008.06351 [cs.LO], 2020.
%H Gregg Musiker and Son Nguyen, <a href="https://arxiv.org/abs/2206.02007">Labeled Chip-firing on Binary Trees</a>, arXiv:2206.02007 [math.CO], 2022.
%H Kival Ngaokrajang, <a href="/A000975/a000975_1.pdf">Illustration of initial terms</a>
%H Ahmet Öteleş, <a href="https://dx.doi.org/10.1063/1.4992479">On the sum of Pell and Jacobsthal numbers by the determinants of Hessenberg matrices</a>, AIP Conference Proceedings 1863, 310003 (2017).
%H Vladimir Shevelev, <a href="http://arxiv.org/abs/0801.0072">On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure</a>, arXiv:0801.0072 [math.CO], 2007-2010. See Example 3.
%H 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 pp. 15, 17.
%H A. V. Sills and H. 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 - _N. J. A. Sloane_, Sep 21 2012
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H Paul K. Stockmeyer, <a href="http://arxiv.org/abs/1608.08245">An Exploration of Sequence A000975</a>, arXiv:1608.08245 [math.CO], 2016; <a href="https://www.fq.math.ca/Papers1/55-5/Stockmeyer.pdf">Fib. Quart. 55 (2017) 174</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Baguenaudier.html">Baguenaudier</a>
%H A. K. Whitford, <a href="http://www.fq.math.ca/Scanned/15-1/whitford-a.pdf">Binet's Formula Generalized</a>, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2).
%F a(n) = ceiling(2*(2^n-1)/3).
%F Alternating sum transform (PSumSIGN) of {2^n - 1} (A000225).
%F a(n) = a(n-1) + 2*a(n-2) + 1.
%F a(n) = 2*2^n/3 - 1/2 - (-1)^n/6.
%F a(n) = Sum_{i = 0..n} A001045(i), partial sums of A001045. - _Bill Blewett_
%F a(n) = n + 2*Sum_{k = 1..n-2} a(k).
%F G.f.: x/((1+x)*(1-x)*(1-2*x)) = x/(1-2*x-x^2+2*x^3). - _Paul Barry_, Feb 11 2003
%F a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3). - _Paul Barry_, Feb 11 2003
%F a(n) = Sum_{k = 0..floor((n-1)/2)} 2^(n-2*k-1). - _Paul Barry_, Nov 11 2003
%F a(n+1) = Sum_{k=0..floor(n/2)} 2^(n-2*k); a(n+1) = Sum_{k = 0..n} Sum_{j = 0..k} (-1)^(j+k)*2^j. - _Paul Barry_, Nov 12 2003
%F (-1)^(n+1)*a(n) = Sum_{i = 0..n} Sum_{k = 1..i} k!*k* Stirling2(i, k)*(-1)^(k-1) = (1/3)*(-2)^(n+1)-(1/6)(3*(-1)^(n+1)-1). - Mario Catalani (mario.catalani(AT)unito.it), Dec 22 2003
%F 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
%F a(n) = A001045(n+1) - A059841(n). - _Paul Barry_, Jul 22 2004
%F a(n) = Sum_{k = 0..n} 2^(n-k-1)*(1-(-1)^k), row sums of A130125. - _Paul Barry_, Jul 28 2004
%F a(n) = Sum_{k = 0..n} binomial(k, n-k+1)2^(n-k); a(n) = Sum_{k = 0..floor(n/2)} binomial(n-k, k+1)2^k. - _Paul Barry_, Oct 07 2004
%F a(n) = A107909(A104161(n)); A007088(a(n)) = A056830(n). - _Reinhard Zumkeller_, May 28 2005
%F a(n) = floor(2^(n+1)/3) = ceiling(2^(n+1)/3) - 1 = A005578(n+1) - 1. - _Paul Barry_, Oct 08 2005
%F Convolution of "Number of fixed points in all 231-avoiding involutions in S_n." (A059570) with "1-n" (A024000), treating the result as if offset was 0. - _Graeme McRae_, Jul 12 2006
%F a(n) = A081254(n) - 2^n. - _Philippe Deléham_, Oct 15 2006
%F Starting (1, 2, 5, 10, 21, 42, ...), these are the row sums of triangle A135228. - _Gary W. Adamson_, Nov 23 2007
%F 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(n-1)]. - _Gary W. Adamson_, Dec 25 2007
%F 2^n = 2*A005578(n-1) + 2*A001045(n) + 2*a(n-2). - _Gary W. Adamson_, Dec 25 2007
%F If we define f(m,j,x) = Sum_{k=j..m} binomial(m,k)*stirling2(k,j)*x^(m-k) then a(n-3) = (-1)^(n-1)*f(n,3,-2), (n >= 3). - _Milan Janjic_, Apr 26 2009
%F a(n) + A001045(n) = A166920(n). a(n) + A001045(n+2) = A051049(n+1). - _Paul Curtz_, Oct 29 2009
%F a(n) = floor(A051049(n+1)/3). - _Gary Detlefs_, Dec 19 2010
%F a(n) = round((2^(n+2)-3)/6) = floor((2^(n+1)-1)/3) = round((2^(n+1)-2)/3); a(n) = a(n-2) + 2^(n-1), n > 1. - _Mircea Merca_, Dec 27 2010
%F a(n) = binary XOR of 2^k-1 for k=0..n. - _Paul D. Hanna_, Nov 05 2011
%F E.g.f.: 2/3*exp(2*x) - 1/2*exp(x) - 1/6*exp(-x) = 2/3*U(0); U(k) = 1 - 3/(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
%F Starting with "1" = triangle A059260 * [1, 2, 2, 2, ...] as a vector. - _Gary W. Adamson_, Mar 06 2012
%F 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
%F a(n) + a(n+1) = 2^(n+1) - 1. - _Arie Bos_, Apr 03 2013
%F G.f.: Q(0)/(3*(1-x)), 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
%F floor(a(n+2)*3/5) = A077854(n), for n >= 0. - _Armands Strazds_, Sep 21 2014
%F a(n) = (2^(n+1) - 2 + (n mod 2))/3. - _Paul Toms_, Mar 18 2015
%F a(0) = 0, a(n) = 2*(a(n-1)) + (n mod 2). - _Paul Toms_, Mar 18 2015
%F Binary: a(n) = (a(n-1) shift left 1) + (a(n-1)) NOR (...11110). - _Paul Toms_, Mar 18 2015
%F Binary: for n > 1, a(n) = 2*a(n-1) OR a(n-2). - _Stanislav Sykora_, Nov 12 2015
%F a(n) = A266613(n) - 20*2^(n-5), for n > 2. - _Andres Cicuttin_, Mar 31 2016
%F From _Michael Somos_, Jul 23 2017: (Start)
%F a(n) = -(2^n)*a(-n) for even n; a(n) = -(2^(n+1))*a(-n) + 1 for odd n.
%F 0 = +a(n)*(+2 +4*a(n) -4*a(n+1)) + a(n+1)*(-1 +a(n+1)) for all n in Z. (End)
%F G.f.: (x^1+x^3+x^5+x^7+...)/(1-2*x). - _Gregory L. Simay_, Sep 27 2017
%F a(n+1) = A051049(n) + A001045(n). - _Yuchun Ji_, Jul 12 2018
%F a(n) = A153772(n+3)/4. - _Markus Sigg_, Sep 14 2020
%F a(4*k+d) = 2^(d+1)*a(4*k-1) + a(d), a(n+4) = a(n) + 2^n*10, a(0..3) = [0,1,2,5]. So the last digit is always 0,1,2,5 repeated. - _Yuchun Ji_, May 22 2023
%e a(4)=10 since 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111 are the 10 binary strings switching 0000 to 1111.
%e 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".
%e 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".
%e a(n) = (2^0 - 1) XOR (2^1 - 1) XOR (2^2 - 1) XOR (2^3 - 1) XOR ... XOR (2^n - 1). - _Paul D. Hanna_, Nov 05 2011
%e G.f. = x + 2*x^2 + 5*x^3 + 10*x^4 + 21*x^5 + 42*x^6 + 85*x^7 + 170*x^8 + ...
%e a(9) = 341 = 2^8 + 2^6 + 2^4 + 2^2 + 2^0 = 4^4 + 4^3 + 4^2 + 4^1 + 4^0 = A002450(5). a(10) = 682 = 2*a(9) = 2*A002450(5). - _Gregory L. Simay_, Sep 27 2017
%p A000975 := proc(n) option remember; if n <= 1 then n else if n mod 2 = 0 then 2*A000975(n-1) else 2*A000975(n-1)+1 fi; fi; end;
%p seq(iquo(2^n,3),n=1..33); # _Zerinvary Lajos_, Apr 20 2008
%p f:=n-> if n mod 2 = 0 then (2^n-1)/3 else (2^n-2)/3; fi; [seq(f(n),n=0..40)]; # _N. J. A. Sloane_, Mar 21 2017
%t Array[Ceiling[2(2^# - 1)/3] &, 41, 0]
%t RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == a[n - 1] + 2a[n - 2] + 1}, a, {n, 40}] (* or *)
%t LinearRecurrence[{2, 1, -2}, {0, 1, 2}, 40] (* _Harvey P. Dale_, Aug 10 2013 *)
%t f[n_] := Block[{exp = n - 2}, Sum[2^i, {i, exp, 0, -2}]]; Array[f, 33] (* _Robert G. Wilson v_, Oct 30 2015 *)
%t 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 *)
%t NestList[2# + Boole[EvenQ[#]] &, 0, 39] (* _Alonso del Arte_, Sep 21 2018 *)
%o (PARI) {a(n) = if( n<0, 0, 2 * 2^n \ 3)}; /* _Michael Somos_, Sep 04 2006 */
%o (PARI) a(n)=if(n<=0,0,bitxor(a(n-1),2^n-1)) \\ _Paul D. Hanna_, Nov 05 2011
%o (PARI) concat(0, Vec(x/(1-2*x-x^2+2*x^3) + O(x^100))) \\ _Altug Alkan_, Oct 30 2015
%o (PARI) {a(n) = (4*2^n - 3 - (-1)^n) / 6}; /* _Michael Somos_, Jul 23 2017 */
%o (Haskell)
%o a000975 n = a000975_list !! n
%o a000975_list = 0 : 1 : map (+ 1)
%o (zipWith (+) (tail a000975_list) (map (* 2) a000975_list))
%o -- _Reinhard Zumkeller_, Mar 07 2012
%o (Magma) [(2^(n+1) - 2 + (n mod 2))/3: n in [0..40]]; // _Vincenzo Librandi_, Mar 18 2015
%o (GAP) List([0..35],n->(2^(n+1)-2+(n mod 2))/3); # _Muniru A Asiru_, Nov 01 2018
%o (Python)
%o def a(n): return (2**(n+1) - 2 + (n%2))//3
%o print([a(n) for n in range(35)]) # _Michael S. Branicky_, Dec 19 2021
%Y Partial sums of A001045.
%Y Row sums of triangle A013580.
%Y Equals A026644/2.
%Y Union of the bijections A002450 and A020988. - _Robert G. Wilson v_, Jun 09 2014
%Y Column k=3 of A261139.
%Y Cf. A000295, A005578, A015441, A043291, A053404, A059260, A077854, A119440, A127824, A130125, A135228, A155051, A179970, A264784.
%Y Complement of A107907.
%Y Row 3 of A300653.
%Y Other sequences that relate to the binary representation of the terms: A003714, A003754, A007088, A022290, A056830, A104161, A107909.
%Y Cf. A000120, A001511, A003242, A027383, A070939, A164707, A295235, A319416.
%Y Cf. A005186, A033491, A153772.
%Y Cf. A014550, A035263
%Y Cf. A051293, A067659, A079309, A231147, A325347, A359893, A359907, A361801.
%K nonn,easy,nice
%O 0,3
%A _Mira Bernstein_, _N. J. A. Sloane_, _Robert G. Wilson v_, Sep 13 1996
%E Additional comments from _Barry E. Williams_, Jan 10 2000