

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


279



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, 5726623061, 11453246122
(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).  Andreas M. Hinz, Feb 15 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)} 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 evenlength 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
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) is the minimal number of vertices to be selected in a vertexcover of the balanced tree B_n.  Senpeng Eu, Jun 15 2002
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
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
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
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
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
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)
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^(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.
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
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 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^(n1))*H(2), where * is the Kronecker product.  William P. Orrick, Jun 28 2015
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
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
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
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
Except for 0, these are the positive integers whose binary expansion has cutsresistance 1. For the operation of shortening all runs by 1, cutsresistance is the number of applications required to reach an empty word. Cutsresistance 2 is A329862.  Gus Wiseman, Nov 27 2019
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(n2)+1) = s(12*a(n2)+4)+1 = s(3*a(n2)+1)+3 = s(a(n2))+2 = (n2)+3+2 = n+3, and for even n >= 4 this gives s(a(n)) = s(2*a(n1)) = s(a(n1))+1 = (n1)+3+1 = n+3.
Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)
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:
..1 3 7 15...
..1 0 1 1 1 0 1 0 1 0 1 1 1 0 1...
..1.....2...........5......................10...; a(n) = Sum_(k=1..2n1)A035263(k)
.....1...........2.......................5...; as to zeros.
..1's in the Tower of Hanoi game represent CW moves On disks in the pattern:
..0, 1, 2, 0, 1, 2, ... whereas even numbered disks move in the pattern:
..0, 2, 1, 0, 2, 1, ... (End)
Except for 0, numbers that are repunits in Graycode representation (A014550).  Amiram Eldar, May 21 2021
Also the number of nonempty subsets of {1..n} with integer median, where the median of a multiset is the middle part in the oddlength case, and the average of the two middle parts in the evenlength case. For example, the a(1) = 1 through a(4) = 10 subsets are:
{1} {1} {1} {1}
{2} {2} {2}
{3} {3}
{1,3} {4}
{1,2,3} {1,3}
{2,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
The complement is counted by A005578.
For mean instead of median we have A051293, counting empty sets A327475.
(End)


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



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) = 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^(n2*k1)}; a(n+1) = Sum_{k = 0..floor(n/2)} 2^(n2*k).  Paul Barry, Nov 11 2003
a(n+1) = Sum_{k=0..floor(n/2)} 2^(n2*k); 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) = Sum_{k = 0..n} 2^(nk1)*(1(1)^k), row sums of A130125.  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 was 0.  Graeme McRae, Jul 12 2006
Starting (1, 2, 5, 10, 21, 42, ...), these are the 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) = 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) = 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
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
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
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)
a(4*k+d) = 2^(d+1)*a(4*k1) + 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


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^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
G.f. = x + 2*x^2 + 5*x^3 + 10*x^4 + 21*x^5 + 42*x^6 + 85*x^7 + 170*x^8 + ...
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


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;
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

Array[Ceiling[2(2^#  1)/3] &, 41, 0]
RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == a[n  1] + 2a[n  2] + 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))
(Magma) [(2^(n+1)  2 + (n mod 2))/3: n in [0..40]]; // Vincenzo Librandi, Mar 18 2015
(GAP) List([0..35], n>(2^(n+1)2+(n mod 2))/3); # Muniru A Asiru, Nov 01 2018
(Python)
def a(n): return (2**(n+1)  2 + (n%2))//3


CROSSREFS

Cf. A000295, A005578, A015441, A043291, A053404, A059260, A077854, A119440, A127824, A130125, A135228, A155051, A179970, A264784.


KEYWORD

nonn,easy,nice,changed


AUTHOR



EXTENSIONS



STATUS

approved



