CINXE.COM
A000975 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A000975 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A000975" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA000975">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A000975 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A000975 </div> <div class=seqname> 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). </div> </div> <div class=scorerefs> 294 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>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</div> <div class=seqdatalinks> (<a href="/A000975/list">list</a>; <a href="/A000975/graph">graph</a>; <a href="/search?q=A000975+-id:A000975">refs</a>; <a href="/A000975/listen">listen</a>; <a href="/history?seq=A000975">history</a>; <a href="/search?q=id:A000975&fmt=text">text</a>; <a href="/A000975/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,3</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>Might be called the "Lichtenberg sequence" after Georg Christoph Lichtenberg, who discussed it in 1769 in connection with the Chinese Rings puzzle (baguenaudier). - <a href="/wiki/User:Andreas_M._Hinz">Andreas M. Hinz</a>, Feb 15 2017</div> <div class=sectline>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)</div> <div class=sectline>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.</div> <div class=sectline>Conjecture: {a(n)} also gives all j for which <a href="/A048702" title="Binary palindromes of even length divided by 3.">A048702</a>(j) = <a href="/A000217" title="Triangular numbers: a(n) = binomial(n+1,2) = n*(n+1)/2 = 0 + 1 + 2 + ... + n.">A000217</a>(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 <a href="/A048701" title="List of binary palindromes of even length (written in base 10).">A048701</a>(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. - <a href="/wiki/User:Antti_Karttunen">Antti Karttunen</a>, circa 1999. (This has been now proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - <a href="/wiki/User:Antti_Karttunen">Antti Karttunen</a>, Aug 31 2016</div> <div class=sectline>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. - <a href="/wiki/User:Bill_Blewett">Bill Blewett</a>, Dec 21 2000</div> <div class=sectline>a(n) is the minimal number of vertices to be selected in a vertex-cover of the balanced tree B_n. - <a href="/wiki/User:Sen-peng_Eu">Sen-peng Eu</a>, Jun 15 2002</div> <div class=sectline><a href="/A087117" title="Number of zeros in the longest string of consecutive zeros in the binary representation of n.">A087117</a>(a(n)) = <a href="/A038374" title="Length of longest contiguous block of 1's in binary expansion of n.">A038374</a>(a(n)) = 1 for n > 1; see also <a href="/A090050" title="Numbers having equal length of longest contiguous block of zeros and ones in binary expansion.">A090050</a>. - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Nov 20 2003</div> <div class=sectline>Intersection of <a href="/A003754" title="Numbers with no adjacent 0's in binary expansion.">A003754</a> and <a href="/A003714" title="Fibbinary numbers: if n = F(i1) + F(i2) + ... + F(ik) is the Zeckendorf representation of n (i.e., write n in Fibonacci numb...">A003714</a>; complement of <a href="/A107907" title="Numbers having consecutive zeros or consecutive ones in binary representation.">A107907</a>. - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, May 28 2005</div> <div class=sectline>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 = <a href="/A022290" title="Replace 2^k in binary expansion of n with Fibonacci(k+2).">A022290</a>(m)). - <a href="/wiki/User:Peter_Munn">Peter Munn</a>, Oct 06 2022</div> <div class=sectline>a(n+1) gives row sums of Riordan array (1/(1-x), x(1+2x)). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Jul 18 2005</div> <div class=sectline>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*<a href="/A119440" title="Triangle read by rows: T(n,k) is the number of binary sequences of length n that start with exactly k 01's (0 <= k <= floor(...">A119440</a>(n+1, k). - <a href="/wiki/User:Emeric_Deutsch">Emeric Deutsch</a>, May 19 2006</div> <div class=sectline>In Norway we call the 10-ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts. - <a href="/wiki/User:Hans_Isdahl">Hans Isdahl</a>, Jan 07 2008</div> <div class=sectline>Equals <a href="/A002450" title="a(n) = (4^n - 1)/3.">A002450</a> and <a href="/A020988" title="a(n) = (2/3)*(4^n-1).">A020988</a> interlaced. - <a href="/wiki/User:Zak_Seidov">Zak Seidov</a>, Feb 10 2008</div> <div class=sectline>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|. - <a href="/wiki/User:K.V.Iyer">K.V.Iyer</a>, Apr 13 2009</div> <div class=sectline>Starting with 1 and convolved with [1, 2, 2, 2, ...] = <a href="/A000295" title="Eulerian numbers (Euler's triangle: column k=2 of A008292, column k=1 of A173018).">A000295</a>. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Jun 02 2009</div> <div class=sectline>a(n) written in base 2 is sequence <a href="/A056830" title="Alternate digits 1 and 0.">A056830</a>(n). - <a href="/wiki/User:Jaroslav_Krizek">Jaroslav Krizek</a>, Aug 05 2009</div> <div class=sectline>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. - <a href="/wiki/User:Wolfdieter_Lang">Wolfdieter Lang</a>, Oct 18 2010</div> <div class=sectline>From <a href="/wiki/User:Vladimir_Shevelev">Vladimir Shevelev</a>, Jan 30 2012, Feb 13 2012: (Start)</div> <div class=sectline>1) Denote by {n, k} the number of permutations of 1, ..., n with the up-down index k (for definition, see comment in <a href="/A203827" title="Table of coefficients of up-down polynomials P_n(m) = Sum_{i=0..floor(log_2(2n))} binomial(m,i).">A203827</a>). Then max_k{n, k} = {n, a(n)} = <a href="/A000111" title="Euler or up/down numbers: e.g.f. sec(x) + tan(x). Also for n >= 2, half the number of alternating permutations on n letters ...">A000111</a>(n).</div> <div class=sectline>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)</div> <div class=sectline>From <a href="/wiki/User:Hieronymus_Fischer">Hieronymus Fischer</a>, Nov 22 2012: (Start)</div> <div class=sectline>Represented in binary form each term after the second one contains every previous term as a substring.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>(End)</div> <div class=sectline>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. - <a href="/wiki/User:Patrick_Labarque">Patrick Labarque</a>, Feb 09 2013</div> <div class=sectline><a href="/A090079" title="In binary expansion of n: reduce contiguous blocks of 0's to 0 and contiguous blocks of 1's to 1.">A090079</a>(a(n)) = a(n) and <a href="/A090079" title="In binary expansion of n: reduce contiguous blocks of 0's to 0 and contiguous blocks of 1's to 1.">A090079</a>(m) <> a(n) for m < a(n). - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Feb 16 2013</div> <div class=sectline>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. - <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Dec 15 2013</div> <div class=sectline>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. - <a href="/wiki/User:Ran_Pan">Ran Pan</a>, Apr 18 2015</div> <div class=sectline>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. - <a href="/wiki/User:William_P._Orrick">William P. Orrick</a>, Jun 28 2015</div> <div class=sectline>Conjectured record values of <a href="/A264784" title="Run lengths of zeros in A265158.">A264784</a>: a(n) = <a href="/A264784" title="Run lengths of zeros in A265158.">A264784</a>(<a href="/A155051" title="Expansion of c(x^2)*(1+x)/(1-x), c(x) the g.f. of A000108.">A155051</a>(n-1)). - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Dec 04 2015. (This is proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - <a href="/wiki/User:Antti_Karttunen">Antti Karttunen</a>, Aug 31 2016</div> <div class=sectline>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 <a href="/A279053" title="Binary representation of the x-axis, from the left edge to the origin, of the n-th stage of growth of the two-dimensional ce...">A279053</a> for references and links. - <a href="/wiki/User:Robert_Price">Robert Price</a>, Dec 05 2016</div> <div class=sectline>For n > 4, a(n-2) is the second-largest number in row n of <a href="/A127824" title="Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.">A127824</a>. - <a href="/wiki/User:Dmitry_Kamenetsky">Dmitry Kamenetsky</a>, Feb 11 2017</div> <div class=sectline>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'. - <a href="/wiki/User:Gregory_L._Simay">Gregory L. Simay</a>, Sep 02 2017</div> <div class=sectline>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). - <a href="/wiki/User:Gregory_L._Simay">Gregory L. Simay</a>, Sep 10 2017</div> <div class=sectline>a(n) = 2^(n-1) + 2^(n-3) + 2^(n-5) + ... a(2*k -1) = <a href="/A002450" title="a(n) = (4^n - 1)/3.">A002450</a>(k) is the sum of the powers of 4. a(2*k) = 2*<a href="/A002450" title="a(n) = (4^n - 1)/3.">A002450</a>(k). - <a href="/wiki/User:Gregory_L._Simay">Gregory L. Simay</a>, Sep 27 2017</div> <div class=sectline>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. - <a href="/wiki/User:Ctibor_O._Zizka">Ctibor O. Zizka</a>, Nov 06 2018</div> <div class=sectline>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 <a href="/A329862" title="Positive integers whose binary expansion has cuts-resistance 2.">A329862</a>. - <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Nov 27 2019</div> <div class=sectline>From <a href="/wiki/User:Markus_Sigg">Markus Sigg</a>, Sep 14 2020: (Start)</div> <div class=sectline>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.</div> <div class=sectline>Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)</div> <div class=sectline>From <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, May 14 2021: (Start)</div> <div class=sectline>With offset 1 the sequence equals the numbers of 1's from n = 1 to 3, 3 to 7, 7 to 15, ...; of <a href="/A035263" title="Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).">A035263</a>; as shown below:</div> <div class=sectline>..1 3 7 15...</div> <div class=sectline>..1 0 1 1 1 0 1 0 1 0 1 1 1 0 1...</div> <div class=sectline>..1.....2...........5......................10...; a(n) = Sum_(k=1..2n-1)<a href="/A035263" title="Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).">A035263</a>(k)</div> <div class=sectline>.....1...........2.......................5...; as to zeros.</div> <div class=sectline>..1's in the Tower of Hanoi game represent CW moves On disks in the pattern:</div> <div class=sectline>..0, 1, 2, 0, 1, 2, ... whereas even numbered disks move in the pattern:</div> <div class=sectline>..0, 2, 1, 0, 2, 1, ... (End)</div> <div class=sectline>Except for 0, numbers that are repunits in Gray-code representation (<a href="/A014550" title="Binary reflected Gray code.">A014550</a>). - <a href="/wiki/User:Amiram_Eldar">Amiram Eldar</a>, May 21 2021</div> <div class=sectline>From <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Apr 20 2023: (Start)</div> <div class=sectline>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:</div> <div class=sectline> {1} {1} {1} {1}</div> <div class=sectline> {2} {2} {2}</div> <div class=sectline> {3} {3}</div> <div class=sectline> {1,3} {4}</div> <div class=sectline> {1,2,3} {1,3}</div> <div class=sectline> {2,4}</div> <div class=sectline> {1,2,3}</div> <div class=sectline> {1,2,4}</div> <div class=sectline> {1,3,4}</div> <div class=sectline> {2,3,4}</div> <div class=sectline>The complement is counted by <a href="/A005578" title="a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.">A005578</a>.</div> <div class=sectline>For mean instead of median we have <a href="/A051293" title="Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.">A051293</a>, counting empty sets <a href="/A327475" title="Number of subsets of {1..n} whose mean is an integer, where {} has mean 0.">A327475</a>.</div> <div class=sectline>For normal multisets we have <a href="/A056450" title="a(n) = (3*2^n - (-2)^n)/2.">A056450</a>, strongly normal <a href="/A361202" title="Maximum product of the vertex arboricities of a graph of order n and its complement.">A361202</a>.</div> <div class=sectline>For partitions we have <a href="/A325347" title="Number of partitions of n having an integer median.">A325347</a>, strict <a href="/A359907" title="Number of strict integer partitions of n with integer median.">A359907</a>, complement <a href="/A307683" title="Number of partitions of n having a non-integer median.">A307683</a>.</div> <div class=sectline>(End)</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.</div> <div class=sectline>Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>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)</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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? - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Jan 04 2014. (Yes, it is. See Stockmeyer's arXiv:1608.08245 2016 paper for the proof.)</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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></div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=394">Encyclopedia of Combinatorial Structures 394</a></div> <div class=sectline>Hans Isdahl, <a href="/A000975/a000975.jpg">"Knitwear" puzzle</a></div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Wolfdieter Lang, <a href="/A000975/a000975.pdf">Notes on certain inhomogeneous three term recurrences.</a></div> <div class=sectline>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>.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Kival Ngaokrajang, <a href="/A000975/a000975_1.pdf">Illustration of initial terms</a></div> <div class=sectline>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).</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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 - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Sep 21 2012</div> <div class=sectline>N. J. A. Sloane, <a href="/transforms.txt">Transforms</a></div> <div class=sectline>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>.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Baguenaudier.html">Baguenaudier</a></div> <div class=sectline>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.</div> <div class=sectline><a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a></div> <div class=sectline><a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2).</div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>a(n) = ceiling(2*(2^n-1)/3).</div> <div class=sectline>Alternating sum transform (PSumSIGN) of {2^n - 1} (<a href="/A000225" title="a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)">A000225</a>).</div> <div class=sectline>a(n) = a(n-1) + 2*a(n-2) + 1.</div> <div class=sectline>a(n) = 2*2^n/3 - 1/2 - (-1)^n/6.</div> <div class=sectline>a(n) = Sum_{i = 0..n} <a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>(i), partial sums of <a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>. - <a href="/wiki/User:Bill_Blewett">Bill Blewett</a></div> <div class=sectline>a(n) = n + 2*Sum_{k = 1..n-2} a(k).</div> <div class=sectline>G.f.: x/((1+x)*(1-x)*(1-2*x)) = x/(1-2*x-x^2+2*x^3). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Feb 11 2003</div> <div class=sectline>a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Feb 11 2003</div> <div class=sectline>a(n) = Sum_{k = 0..floor((n-1)/2)} 2^(n-2*k-1). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Nov 11 2003</div> <div class=sectline>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. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Nov 12 2003</div> <div class=sectline>(-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</div> <div class=sectline>a(n+1) = (n!/3)*Sum_{i - (-1)^i + j = n, i = 0..n, j = 0..n} 1/(i - (-1)^i)!/j!. - <a href="/wiki/User:Benoit_Cloitre">Benoit Cloitre</a>, May 24 2004</div> <div class=sectline>a(n) = <a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>(n+1) - <a href="/A059841" title="Period 2: Repeat [1,0]. a(n) = 1 - (n mod 2); Characteristic function of even numbers.">A059841</a>(n). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Jul 22 2004</div> <div class=sectline>a(n) = Sum_{k = 0..n} 2^(n-k-1)*(1-(-1)^k), row sums of <a href="/A130125" title="Triangle defined by A128174 * A130123, read by rows.">A130125</a>. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Jul 28 2004</div> <div class=sectline>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. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Oct 07 2004</div> <div class=sectline>a(n) = <a href="/A107909" title="Numbers having no consecutive zeros or no consecutive ones in binary representation.">A107909</a>(<a href="/A104161" title="G.f.: x*(1 - x + x^2)/((1-x)^2 * (1 - x - x^2)).">A104161</a>(n)); <a href="/A007088" title="The binary numbers (or binary words, or binary vectors, or binary expansion of n): numbers written in base 2.">A007088</a>(a(n)) = <a href="/A056830" title="Alternate digits 1 and 0.">A056830</a>(n). - <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, May 28 2005</div> <div class=sectline>a(n) = floor(2^(n+1)/3) = ceiling(2^(n+1)/3) - 1 = <a href="/A005578" title="a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.">A005578</a>(n+1) - 1. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Oct 08 2005</div> <div class=sectline>Convolution of "Number of fixed points in all 231-avoiding involutions in S_n." (<a href="/A059570" title="Number of fixed points in all 231-avoiding involutions in S_n.">A059570</a>) with "1-n" (<a href="/A024000" title="a(n) = 1 - n.">A024000</a>), treating the result as if offset was 0. - <a href="/wiki/User:Graeme_McRae">Graeme McRae</a>, Jul 12 2006</div> <div class=sectline>a(n) = <a href="/A081254" title="Numbers k such that A081252(m)/m^2 has a local maximum for m = k.">A081254</a>(n) - 2^n. - <a href="/wiki/User:Philippe_Del茅ham">Philippe Del茅ham</a>, Oct 15 2006</div> <div class=sectline>Starting (1, 2, 5, 10, 21, 42, ...), these are the row sums of triangle <a href="/A135228" title="Triangle A000012(signed) * A007318 * A103451, read by rows.">A135228</a>. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Nov 23 2007</div> <div class=sectline>Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0] = [<a href="/A005578" title="a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.">A005578</a>(n), <a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>(n), a(n-1)]. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Dec 25 2007</div> <div class=sectline>2^n = 2*<a href="/A005578" title="a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.">A005578</a>(n-1) + 2*<a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>(n) + 2*a(n-2). - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Dec 25 2007</div> <div class=sectline>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). - <a href="/wiki/User:Milan_Janjic">Milan Janjic</a>, Apr 26 2009</div> <div class=sectline>a(n) + <a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>(n) = <a href="/A166920" title="a(n) = 2^n - (1 + (-1)^n)/2.">A166920</a>(n). a(n) + <a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>(n+2) = <a href="/A051049" title="Number of moves needed to solve an (n+1)-ring baguenaudier if two simultaneous moves of the two end rings are counted as one.">A051049</a>(n+1). - <a href="/wiki/User:Paul_Curtz">Paul Curtz</a>, Oct 29 2009</div> <div class=sectline>a(n) = floor(<a href="/A051049" title="Number of moves needed to solve an (n+1)-ring baguenaudier if two simultaneous moves of the two end rings are counted as one.">A051049</a>(n+1)/3). - <a href="/wiki/User:Gary_Detlefs">Gary Detlefs</a>, Dec 19 2010</div> <div class=sectline>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. - <a href="/wiki/User:Mircea_Merca">Mircea Merca</a>, Dec 27 2010</div> <div class=sectline>a(n) = binary XOR of 2^k-1 for k=0..n. - <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Nov 05 2011</div> <div class=sectline>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). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, Nov 21 2011</div> <div class=sectline>Starting with "1" = triangle <a href="/A059260" title="Triangle read by rows giving coefficient T(i,j) of x^i y^j in 1/(1-y-x*y-x^2) = 1/((1+x)(1-x-y)) for (i,j) = (0,0), (1,0), (...">A059260</a> * [1, 2, 2, 2, ...] as a vector. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Mar 06 2012</div> <div class=sectline>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. - <a href="/wiki/User:Hieronymus_Fischer">Hieronymus Fischer</a>, Nov 22 2012</div> <div class=sectline>a(n) + a(n+1) = 2^(n+1) - 1. - <a href="/wiki/User:Arie_Bos">Arie Bos</a>, Apr 03 2013</div> <div class=sectline>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). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, May 21 2013</div> <div class=sectline>floor(a(n+2)*3/5) = <a href="/A077854" title="Expansion of 1/((1-x)*(1-2*x)*(1+x^2)).">A077854</a>(n), for n >= 0. - <a href="/wiki/User:Armands_Strazds">Armands Strazds</a>, Sep 21 2014</div> <div class=sectline>a(n) = (2^(n+1) - 2 + (n mod 2))/3. - <a href="/wiki/User:Paul_Toms">Paul Toms</a>, Mar 18 2015</div> <div class=sectline>a(0) = 0, a(n) = 2*(a(n-1)) + (n mod 2). - <a href="/wiki/User:Paul_Toms">Paul Toms</a>, Mar 18 2015</div> <div class=sectline>Binary: a(n) = (a(n-1) shift left 1) + (a(n-1)) NOR (...11110). - <a href="/wiki/User:Paul_Toms">Paul Toms</a>, Mar 18 2015</div> <div class=sectline>Binary: for n > 1, a(n) = 2*a(n-1) OR a(n-2). - <a href="/wiki/User:Stanislav_Sykora">Stanislav Sykora</a>, Nov 12 2015</div> <div class=sectline>a(n) = <a href="/A266613" title="Decimal representation of the middle column of the "Rule 41" elementary cellular automaton starting with a single ON (black)...">A266613</a>(n) - 20*2^(n-5), for n > 2. - <a href="/wiki/User:Andres_Cicuttin">Andres Cicuttin</a>, Mar 31 2016</div> <div class=sectline>From <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Jul 23 2017: (Start)</div> <div class=sectline>a(n) = -(2^n)*a(-n) for even n; a(n) = -(2^(n+1))*a(-n) + 1 for odd n.</div> <div class=sectline>0 = +a(n)*(+2 +4*a(n) -4*a(n+1)) + a(n+1)*(-1 +a(n+1)) for all n in Z. (End)</div> <div class=sectline>G.f.: (x^1+x^3+x^5+x^7+...)/(1-2*x). - <a href="/wiki/User:Gregory_L._Simay">Gregory L. Simay</a>, Sep 27 2017</div> <div class=sectline>a(n+1) = <a href="/A051049" title="Number of moves needed to solve an (n+1)-ring baguenaudier if two simultaneous moves of the two end rings are counted as one.">A051049</a>(n) + <a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>(n). - <a href="/wiki/User:Yuchun_Ji">Yuchun Ji</a>, Jul 12 2018</div> <div class=sectline>a(n) = <a href="/A153772" title="a(n) = (2^n + 2*(-1)^n - 6)/3.">A153772</a>(n+3)/4. - <a href="/wiki/User:Markus_Sigg">Markus Sigg</a>, Sep 14 2020</div> <div class=sectline>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. - <a href="/wiki/User:Yuchun_Ji">Yuchun Ji</a>, May 22 2023</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>a(4)=10 since 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111 are the 10 binary strings switching 0000 to 1111.</div> <div class=sectline>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".</div> <div class=sectline>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".</div> <div class=sectline>a(n) = (2^0 - 1) XOR (2^1 - 1) XOR (2^2 - 1) XOR (2^3 - 1) XOR ... XOR (2^n - 1). - <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Nov 05 2011</div> <div class=sectline>G.f. = x + 2*x^2 + 5*x^3 + 10*x^4 + 21*x^5 + 42*x^6 + 85*x^7 + 170*x^8 + ...</div> <div class=sectline>a(9) = 341 = 2^8 + 2^6 + 2^4 + 2^2 + 2^0 = 4^4 + 4^3 + 4^2 + 4^1 + 4^0 = <a href="/A002450" title="a(n) = (4^n - 1)/3.">A002450</a>(5). a(10) = 682 = 2*a(9) = 2*<a href="/A002450" title="a(n) = (4^n - 1)/3.">A002450</a>(5). - <a href="/wiki/User:Gregory_L._Simay">Gregory L. Simay</a>, Sep 27 2017</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline><a href="/A000975" title="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).">A000975</a> := proc(n) option remember; if n <= 1 then n else if n mod 2 = 0 then 2*<a href="/A000975" title="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).">A000975</a>(n-1) else 2*<a href="/A000975" title="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).">A000975</a>(n-1)+1 fi; fi; end;</div> <div class=sectline>seq(iquo(2^n, 3), n=1..33); # <a href="/wiki/User:Zerinvary_Lajos">Zerinvary Lajos</a>, Apr 20 2008</div> <div class=sectline>f:=n-> if n mod 2 = 0 then (2^n-1)/3 else (2^n-2)/3; fi; [seq(f(n), n=0..40)]; # <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Mar 21 2017</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>Array[Ceiling[2(2^# - 1)/3] &, 41, 0]</div> <div class=sectline>RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == a[n - 1] + 2a[n - 2] + 1}, a, {n, 40}] (* or *)</div> <div class=sectline>LinearRecurrence[{2, 1, -2}, {0, 1, 2}, 40] (* <a href="/wiki/User:Harvey_P._Dale">Harvey P. Dale</a>, Aug 10 2013 *)</div> <div class=sectline>f[n_] := Block[{exp = n - 2}, Sum[2^i, {i, exp, 0, -2}]]; Array[f, 33] (* <a href="/wiki/User:Robert_G._Wilson_v">Robert G. Wilson v</a>, Oct 30 2015 *)</div> <div class=sectline>f[s_List] := Block[{a = s[[-1]]}, Append[s, If[OddQ@ Length@ s, 2a + 1, 2a]]]; Nest[f, {0}, 32] (* <a href="/wiki/User:Robert_G._Wilson_v">Robert G. Wilson v</a>, Jul 20 2017 *)</div> <div class=sectline>NestList[2# + Boole[EvenQ[#]] &, 0, 39] (* <a href="/wiki/User:Alonso_del_Arte">Alonso del Arte</a>, Sep 21 2018 *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(PARI) {a(n) = if( n<0, 0, 2 * 2^n \ 3)}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Sep 04 2006 */</div> <div class=sectline>(PARI) a(n)=if(n<=0, 0, bitxor(a(n-1), 2^n-1)) \\ <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Nov 05 2011</div> <div class=sectline>(PARI) concat(0, Vec(x/(1-2*x-x^2+2*x^3) + O(x^100))) \\ <a href="/wiki/User:Altug_Alkan">Altug Alkan</a>, Oct 30 2015</div> <div class=sectline>(PARI) {a(n) = (4*2^n - 3 - (-1)^n) / 6}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Jul 23 2017 */</div> <div class=sectline>(Haskell)</div> <div class=sectline>a000975 n = a000975_list !! n</div> <div class=sectline>a000975_list = 0 : 1 : map (+ 1)</div> <div class=sectline> (zipWith (+) (tail a000975_list) (map (* 2) a000975_list))</div> <div class=sectline>-- <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Mar 07 2012</div> <div class=sectline>(Magma) [(2^(n+1) - 2 + (n mod 2))/3: n in [0..40]]; // <a href="/wiki/User:Vincenzo_Librandi">Vincenzo Librandi</a>, Mar 18 2015</div> <div class=sectline>(GAP) List([0..35], n->(2^(n+1)-2+(n mod 2))/3); # <a href="/wiki/User:Muniru_A_Asiru">Muniru A Asiru</a>, Nov 01 2018</div> <div class=sectline>(Python)</div> <div class=sectline>def a(n): return (2**(n+1) - 2 + (n%2))//3</div> <div class=sectline>print([a(n) for n in range(35)]) # <a href="/wiki/User:Michael_S._Branicky">Michael S. Branicky</a>, Dec 19 2021</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Partial sums of <a href="/A001045" title="Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1; also a(n) = nearest integer ...">A001045</a>.</div> <div class=sectline>Row sums of triangle <a href="/A013580" title="Triangle formed in same way as Pascal's triangle (A007318) except 1 is added to central element in even-numbered rows.">A013580</a>.</div> <div class=sectline>Equals <a href="/A026644" title="a(n) = a(n-1) + 2*a(n-2) + 2, for n>=3, where a(0)= 1, a(1)= 2, a(2)= 4.">A026644</a>/2.</div> <div class=sectline>Union of the bijections <a href="/A002450" title="a(n) = (4^n - 1)/3.">A002450</a> and <a href="/A020988" title="a(n) = (2/3)*(4^n-1).">A020988</a>. - <a href="/wiki/User:Robert_G._Wilson_v">Robert G. Wilson v</a>, Jun 09 2014</div> <div class=sectline>Column k=3 of <a href="/A261139" title="S'_t(n) is the number of set partitions of {1,2,...,t} into exactly n parts such that no part contains both 1 and t or both ...">A261139</a>.</div> <div class=sectline>Cf. <a href="/A000295" title="Eulerian numbers (Euler's triangle: column k=2 of A008292, column k=1 of A173018).">A000295</a>, <a href="/A005578" title="a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.">A005578</a>, <a href="/A015441" title="Generalized Fibonacci numbers.">A015441</a>, <a href="/A043291" title="Every run length in base 2 is 2.">A043291</a>, <a href="/A053404" title="Expansion of 1/((1+3*x)*(1-4*x)).">A053404</a>, <a href="/A059260" title="Triangle read by rows giving coefficient T(i,j) of x^i y^j in 1/(1-y-x*y-x^2) = 1/((1+x)(1-x-y)) for (i,j) = (0,0), (1,0), (...">A059260</a>, <a href="/A077854" title="Expansion of 1/((1-x)*(1-2*x)*(1+x^2)).">A077854</a>, <a href="/A119440" title="Triangle read by rows: T(n,k) is the number of binary sequences of length n that start with exactly k 01's (0 <= k <= floor(...">A119440</a>, <a href="/A127824" title="Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.">A127824</a>, <a href="/A130125" title="Triangle defined by A128174 * A130123, read by rows.">A130125</a>, <a href="/A135228" title="Triangle A000012(signed) * A007318 * A103451, read by rows.">A135228</a>, <a href="/A155051" title="Expansion of c(x^2)*(1+x)/(1-x), c(x) the g.f. of A000108.">A155051</a>, <a href="/A179970" title="Numbers such that in base-4 representation all sums of two adjacent digits are odd.">A179970</a>, <a href="/A264784" title="Run lengths of zeros in A265158.">A264784</a>.</div> <div class=sectline>Complement of <a href="/A107907" title="Numbers having consecutive zeros or consecutive ones in binary representation.">A107907</a>.</div> <div class=sectline>Row 3 of <a href="/A300653" title="Square array T(n, k) (n >= 1, k >= 1) read by antidiagonals upwards: T(n, k) is the k-th positive number whose binary repres...">A300653</a>.</div> <div class=sectline>Other sequences that relate to the binary representation of the terms: <a href="/A003714" title="Fibbinary numbers: if n = F(i1) + F(i2) + ... + F(ik) is the Zeckendorf representation of n (i.e., write n in Fibonacci numb...">A003714</a>, <a href="/A003754" title="Numbers with no adjacent 0's in binary expansion.">A003754</a>, <a href="/A007088" title="The binary numbers (or binary words, or binary vectors, or binary expansion of n): numbers written in base 2.">A007088</a>, <a href="/A022290" title="Replace 2^k in binary expansion of n with Fibonacci(k+2).">A022290</a>, <a href="/A056830" title="Alternate digits 1 and 0.">A056830</a>, <a href="/A104161" title="G.f.: x*(1 - x + x^2)/((1-x)^2 * (1 - x - x^2)).">A104161</a>, <a href="/A107909" title="Numbers having no consecutive zeros or no consecutive ones in binary representation.">A107909</a>.</div> <div class=sectline>Cf. <a href="/A000120" title="1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).">A000120</a>, <a href="/A001511" title="The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.">A001511</a>, <a href="/A003242" title="Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).">A003242</a>, <a href="/A027383" title="a(2*n) = 3*2^n - 2; a(2*n+1) = 2^(n+2) - 2.">A027383</a>, <a href="/A070939" title="Length of binary representation of n.">A070939</a>, <a href="/A164707" title="A positive integer n is included if all runs of 1's in binary n are of the same length.">A164707</a>, <a href="/A295235" title="Numbers k such that the positions of the ones in the binary representation of k are in arithmetic progression.">A295235</a>, <a href="/A319416" title="Cuts-resistance of n: number of applications of Lernormand's "raboter" map needed to transform the binary expansion of n to ...">A319416</a>.</div> <div class=sectline>Cf. <a href="/A005186" title="a(n) is the number of integers m which take n steps to reach 1 in '3x+1' problem.">A005186</a>, <a href="/A033491" title="a(n) is the smallest integer that takes n halving and tripling steps to reach 1 in the 3x+1 problem.">A033491</a>, <a href="/A153772" title="a(n) = (2^n + 2*(-1)^n - 6)/3.">A153772</a>.</div> <div class=sectline>Cf. <a href="/A014550" title="Binary reflected Gray code.">A014550</a>, <a href="/A035263" title="Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).">A035263</a></div> <div class=sectline>Cf. <a href="/A051293" title="Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.">A051293</a>, <a href="/A067659" title="Number of partitions of n into distinct parts such that number of parts is odd.">A067659</a>, <a href="/A079309" title="a(n) = C(1,1) + C(3,2) + C(5,3) + ... + C(2*n-1,n).">A079309</a>, <a href="/A231147" title="Array of coefficients of numerator polynomials of the rational function p(n, x + 1/x), where p(n,x) = (x^n - 1)/(x - 1).">A231147</a>, <a href="/A325347" title="Number of partitions of n having an integer median.">A325347</a>, <a href="/A359893" title="Triangle read by rows where T(n,k) is the number of integer partitions of n with median k, where k ranges from 1 to n in ste...">A359893</a>, <a href="/A359907" title="Number of strict integer partitions of n with integer median.">A359907</a>, <a href="/A361801" title="Number of nonempty subsets of {1..n} with median n/2.">A361801</a>.</div> <div class=sectline>Sequence in context: <a href="/A243988" title="G.f.: Sum_{n>=0} (1 + x^n)^n * x^n / (1-x)^(n+1).">A243988</a> <a href="/A279811" title="Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional ...">A279811</a> <a href="/A279751" title="Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional ...">A279751</a> * <a href="/A280148" title="Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional ...">A280148</a> <a href="/A215410" title="a(0) = 0; a(n+1) = 2*a(n) + k where k = 0 if prime(n+2)/prime(n+1) < prime(n+1)/prime(n), otherwise k = 1.">A215410</a> <a href="/A279668" title="Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional ...">A279668</a></div> <div class=sectline>Adjacent sequences: <a href="/A000972" title="Fermat coefficients.">A000972</a> <a href="/A000973" title="Fermat coefficients.">A000973</a> <a href="/A000974" title="Conjecturally the number of even integers the sum of two primes in exactly n ways.">A000974</a> * <a href="/A000976" title="Period of 1/n! in base 10.">A000976</a> <a href="/A000977" title="Numbers that are divisible by at least three different primes.">A000977</a> <a href="/A000978" title="Wagstaff numbers: numbers k such that (2^k + 1)/3 is prime.">A000978</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span>,<span title="it is very easy to produce terms of sequence">easy</span>,<span title="an exceptionally nice sequence">nice</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:Mira_Bernstein">Mira Bernstein</a>, <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, <a href="/wiki/User:Robert_G._Wilson_v">Robert G. Wilson v</a>, Sep 13 1996</div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>Additional comments from <a href="/wiki/User:Barry_E._Williams">Barry E. Williams</a>, Jan 10 2000</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified November 28 14:19 EST 2024. Contains 378204 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>