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

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000975 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). 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 Spin-Out 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 even-length 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 vertex-cover of the balanced tree B_n. - Sen-peng 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/(1-x), 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(n-1) + 2*A001045(n) + 2*a(n-2). - Gary W. Adamson, Dec 25 2007

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

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

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 up-down 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(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)

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

(End)

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

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^(n-1))*H(2), where * is the Kronecker product. - William P. Orrick, Jun 28 2015

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

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

For n > 4, a(n-2) is the second-largest 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 n-cube layout on a rectangular grid, Discrete Mathematics 213.1-3 (2000): 13-19. 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 [quant-ph], 2011.

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

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 Up-Down Structure, arXiv:0801.0072 [math.CO], 2007-2010. See Example 3.

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 - 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^n-1)/3).

Alternating sum transform (PSumSIGN) of {2^n - 1} (A000225).

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

G.f.: x/((1+x)*(1-x)*(1-2*x)) = x/(1-2*x-x^2+2*x^3). - Paul Barry, Feb 11 2003

a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3). - Paul Barry, Feb 11 2003

a(n) = Sum_{k=0..floor((n-1)/2)} 2^(n-2k-1)}; a(n+1) = Sum_{k=0..floor(n/2)} 2^(n-2k). - Paul Barry, Nov 11 2003

a(n+1) = Sum_{k=0..floor(n/2)} 2^(n-2k); 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)^(k-1) = (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^(n-k-1)*(1-(-1)^k). - Paul Barry, Jul 28 2004

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

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 231-avoiding involutions in S_n." (A059570) with "1-n" (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(n-1)]. - Gary W. Adamson, Dec 25 2007

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

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(n-2) + 2^(n-1), n>1. - Mircea Merca, Dec 27 2010

a(n) = binary XOR of 2^k-1 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

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

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(n-1)) + (n mod 2). - Paul Toms, Mar 18 2015

Binary: a(n) = (a(n-1) shift left 1) + (a(n-1))NOR(...11110). - Paul Toms, Mar 18 2015

Binary: for n>1, a(n) = 2*a(n-1) OR a(n-2). - Stanislav Sykora, Nov 12 2015

a(n) = A266613(n) - 20*2^(n-5), 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^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 + ...

MAPLE

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;

seq(iquo(2^n, 3), n=1..33); # Zerinvary Lajos, Apr 20 2008

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

MATHEMATICA

f[n_] := Ceiling[2(2^n-1)/3]; Array[f, 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(n-1), 2^n-1))} /* Paul D. Hanna, Nov 05 2011 */

(PARI) concat(0, Vec(x/(1-2*x-x^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

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 August 19 13:00 EDT 2017. Contains 290807 sequences.