cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 19 results. Next

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

Original entry on oeis.org

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
Offset: 0

Views

Author

Keywords

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 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)} 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
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 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 A107907. - Reinhard Zumkeller, May 28 2005
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/(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
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
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^(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 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)
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 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
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
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(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
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 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
From Markus Sigg, Sep 14 2020: (Start)
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.
Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)
From Gary W. Adamson, May 14 2021: (Start)
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..2n-1)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 Gray-code representation (A014550). - Amiram Eldar, May 21 2021
From Gus Wiseman, Apr 20 2023: (Start)
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:
{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.
For normal multisets we have A056450, strongly normal A361202.
For partitions we have A325347, strict A359907, complement A307683.
(End)

Examples

			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
		

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.

Crossrefs

Partial sums of A001045.
Row sums of triangle A013580.
Equals A026644/2.
Union of the bijections A002450 and A020988. - Robert G. Wilson v, Jun 09 2014
Column k=3 of A261139.
Complement of A107907.
Row 3 of A300653.
Other sequences that relate to the binary representation of the terms: A003714, A003754, A007088, A022290, A056830, A104161, A107909.

Programs

  • GAP
    List([0..35],n->(2^(n+1)-2+(n mod 2))/3); # Muniru A Asiru, Nov 01 2018
    
  • 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
    
  • 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
    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 *)
    NestList[2# + Boole[EvenQ[#]] &, 0, 39] (* Alonso del Arte, Sep 21 2018 *)
  • 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 */
    
  • Python
    def a(n): return (2**(n+1) - 2 + (n%2))//3
    print([a(n) for n in range(35)]) # Michael S. Branicky, Dec 19 2021

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-2*k-1). - Paul Barry, Nov 11 2003
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
(-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), row sums of A130125. - 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) = A107909(A104161(n)); A007088(a(n)) = A056830(n). - Reinhard Zumkeller, May 28 2005
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 was 0. - Graeme McRae, Jul 12 2006
a(n) = A081254(n) - 2^n. - Philippe Deléham, Oct 15 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(n-1)]. - Gary W. Adamson, Dec 25 2007
2^n = 2*A005578(n-1) + 2*A001045(n) + 2*a(n-2). - 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) + A001045(n) = A166920(n). a(n) + A001045(n+2) = A051049(n+1). - Paul Curtz, Oct 29 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)
G.f.: (x^1+x^3+x^5+x^7+...)/(1-2*x). - Gregory L. Simay, Sep 27 2017
a(n+1) = A051049(n) + A001045(n). - Yuchun Ji, Jul 12 2018
a(n) = A153772(n+3)/4. - Markus Sigg, Sep 14 2020
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

Extensions

Additional comments from Barry E. Williams, Jan 10 2000

A318928 Runs-resistance of binary representation of n.

Original entry on oeis.org

1, 2, 1, 3, 2, 3, 1, 3, 3, 2, 4, 2, 4, 3, 1, 3, 3, 5, 4, 4, 2, 5, 4, 3, 4, 4, 3, 3, 4, 3, 1, 3, 3, 5, 3, 3, 5, 4, 3, 4, 5, 2, 4, 3, 4, 5, 4, 3, 3, 3, 2, 4, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 1, 3, 3, 5, 3, 3, 5, 3, 4, 3, 3, 5, 6, 4, 5, 3, 3, 4, 5, 4, 4, 4, 2, 5, 4, 5, 5, 4, 5, 5, 4, 5, 4
Offset: 1

Views

Author

N. J. A. Sloane, Sep 09 2018

Keywords

Comments

Following Lenormand (2003), we define the "runs-resistance" of a finite list L to be the number of times the RUNS transformation must be applied to L in order to reduce L to a list with a single element.
Here it is immaterial whether we read the binary representation of n from left to right or right to left.
The RUNS transformation must be applied at least once, in order to obtain a list, so a(n) >= 1.

Examples

			11 in binary is [1, 0, 1, 1],
which has runs of lengths [1, 1, 2],
which has runs of lengths [2, 1],
which has runs of lengths [1, 1],
which has a single run of length [2].
This took four steps, so a(11) = 4.
		

Crossrefs

See A319103 for an inverse, and A319417 and A319418 for records.
Ignoring the first digit gives A329870.
Cuts-resistance is A319416.
Compositions counted by runs-resistance are A329744.
Binary words counted by runs-resistance are A319411 and A329767.

Programs

  • Maple
    with(transforms);
    # compute Lenormand's "resistance" of a list
    resist:=proc(a) local ct,i,b;
    if whattype(a) <> list then ERROR("input must be a list"); fi:
    ct:=0; b:=a; for i from 1 to 100 do
    if nops(b)=1 then return(ct); fi;
    b:=RUNS(b); ct:=ct+1; od; end;
    a:=[1];
    for n from 2 to 100 do
    b:=convert(n,base,2);
    r:=resist(b);
    a:=[op(a),r];
    od:
  • Mathematica
    Table[If[n == 1, 1, Length[NestWhileList[Length/@Split[#] &, IntegerDigits[n, 2], Length[#] > 1 &]] - 1], {n, 50}] (* Gus Wiseman, Nov 25 2019 *)

Extensions

a(1) corrected by N. J. A. Sloane, Sep 20 2018

A318921 In binary expansion of n, delete one symbol from each run. Set a(n)=0 if the result is the empty string.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 0, 1, 2, 1, 3, 7, 0, 0, 0, 1, 0, 0, 1, 3, 4, 2, 1, 3, 6, 3, 7, 15, 0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 0, 1, 2, 1, 3, 7, 8, 4, 2, 5, 2, 1, 3, 7, 12, 6, 3, 7, 14, 7, 15, 31, 0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 0, 1, 2, 1, 3, 7, 0, 0, 0, 1, 0, 0, 1, 3, 4, 2, 1, 3, 6, 3, 7, 15, 16
Offset: 0

Views

Author

N. J. A. Sloane, Sep 08 2018

Keywords

Comments

If the binary expansion of n is 1^b 0^c 1^d 0^e ..., then a(n) is the number whose binary expansion is 1^(b-1) 0^(c-1) 1^(d-1) 0^(e-1) .... Leading 0's are omitted, and if the result is the empty string, here we set a(n) = 0. See A319419 for a version which represents the empty string by -1.
Lenormand refers to this operation as planing ("raboter") the runs (or blocks) of the binary expansion.
A175046 expands the runs in a similar way, and a(A175046(n)) = A001477(n). - Andrew Weimholt, Sep 08 2018. In other words, this is a left inverse to A175046: A318921 o A175046 = A001477 = id on [0..oo). - M. F. Hasler, Sep 10 2018
Conjecture: For n in the range 2^k, ..., 2^(k+1)-1, the total value of a(n) appears to be 2*3^(k-1) - 2^(k-1) (see A027649), and so the average value of a(n) appears to be (3/2)^(k-1) - 1/2. - N. J. A. Sloane, Sep 25 2018
The above conjecture was proved by Doron Zeilberger on Nov 16 2018 (see link) and independently by Chai Wah Wu on Nov 18 2018 (see below). - N. J. A. Sloane, Nov 20 2018
From Chai Wah Wu, Nov 18 2018: (Start)
Conjecture is correct for k > 0. Proof: looking at the least significant 2 bits of n, it is easy to see that a(4n) = 2a(2n), a(4n+1) = a(2n), a(4n+2) = a(2n+1) and a(4n+3) = 2a(2n+1)+1. Define f(k) = Sum_{i=2^k..2^(k+1)-1} a(i), i.e. the sum ranges over all numbers with a (k+1)-bit binary expansion. Thus f(0) = a(1) = 0 and f(1) = a(2)+a(3) = 1. By summing over the recurrence relations for a(n), we get f(k+2) = Sum_{i=2^k..2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) = Sum_{i=2^k..2^(k+1)-1} (3a(2i) + 3a(2i+1) + 1) = 3*f(k+1) + 2^k. Solving this first order recurrence relation with the initial condition f(1) = 1 shows that f(k) = 2*3^(k-1)-2^(k-1) for k > 0.
(End)

Examples

			      n / "planed" string / a(n)
      0   e 0 (e = empty string)
      1   e 0
     10   e 0
     11   1 1
    100   0 0
    101   e 0
    110   1 1
    111  11 3
   1000  00 0
   1001   0 0
   1010   e 0
   1011   1 1
   1100  10 2
   1101   1 1
   1110  11 3
   1111 111 7
  10000 000 0
  ...
		

Crossrefs

Cf. A027649 (average value), A175046, A319419 (a version where a(n)=-1 if the result is the empty string).
See also A319416.

Programs

  • Maple
    r:=proc(n) local t1,t2,L1,len,i,j,k,b1;
    if n <= 2 then return(0); fi;
    b1:=[]; t1:=convert(n,base,2); L1:=nops(t1); p:=1; len:=1;
    for i from 2 to L1 do
    t2:=t1[L1+1-i];
    if (t2=p) and (i1 then for j from 1 to len-1 do b1:=[op(b1),p]; od: fi;
       p:=t2; len:=1;
    fi;               od;
    if nops(b1)=0 then return(0);
    else k:=b1[1];
    for i from 2 to nops(b1) do k:=2*k+b1[i]; od;
    return(k);
    fi;
    end;
    [seq(r(n),n=0..120)];
  • Mathematica
    a[n_] := FromDigits[Flatten[Rest /@ Split[IntegerDigits[n, 2]]], 2];
    Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 10 2018 *)
  • PARI
    a(n) = if (n==0, 0, n%2==0, my (z=valuation(n,2)); a(n/2^z) * 2^(z-1), my (o=valuation(n+1,2)); (a(n\2^o)+1) * 2^(o-1)-1) \\ Rémy Sigrist, Sep 09 2018
    
  • PARI
    a(n)={forstep(i=#n=binary(n+!n),2,-1,n[i-1]!=n[i] && n=n[^i]); fromdigits(n[^1],2)} \\ For illustration purpose. - M. F. Hasler, Sep 10 2018
    
  • PARI
    A318921(n)=if(n<3, 0, bittest(n, 0), (A318921(n>>n=valuation(n+1, 2))+1)<<(n-1)-1, A318921(n>>n=valuation(n, 2))<<(n-1)) \\ M. F. Hasler, Sep 11 2018
    
  • Python
    from itertools import groupby
    def a(n):
        s = "".join(k*(len(list(g))-1) for k, g in groupby(bin(n)[2:]))
        return int(s, 2) if s != "" else 0
    print([a(n) for n in range(82)]) # Michael S. Branicky, Jun 01 2025

Formula

a(4n) = 2a(2n), a(4n+1) = a(2n), a(4n+2) = a(2n+1) and a(4n+3) = 2a(2n+1)+1. - Chai Wah Wu, Nov 18 2018

A329860 Triangle read by rows where T(n,k) is the number of binary words of length n with cuts-resistance k.

Original entry on oeis.org

1, 0, 2, 0, 2, 2, 0, 2, 4, 2, 0, 2, 8, 4, 2, 0, 2, 12, 12, 4, 2, 0, 2, 20, 22, 14, 4, 2, 0, 2, 28, 48, 28, 16, 4, 2, 0, 2, 44, 84, 70, 32, 18, 4, 2, 0, 2, 60, 162, 136, 90, 36, 20, 4, 2, 0, 2, 92, 276, 298, 178, 110, 40, 22, 4, 2, 0, 2, 124, 500, 564, 432, 220, 132, 44, 24, 4, 2
Offset: 0

Views

Author

Gus Wiseman, Nov 23 2019

Keywords

Comments

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

Examples

			Triangle begins:
   1
   0   2
   0   2   2
   0   2   4   2
   0   2   8   4   2
   0   2  12  12   4   2
   0   2  20  22  14   4   2
   0   2  28  48  28  16   4   2
   0   2  44  84  70  32  18   4   2
   0   2  60 162 136  90  36  20   4   2
   0   2  92 276 298 178 110  40  22   4   2
   0   2 124 500 564 432 220 132  44  24   4   2
Row n = 4 counts the following words:
  0101  0010  0001  0000
  1010  0011  0111  1111
        0100  1000
        0110  1110
        1001
        1011
        1100
        1101
		

Crossrefs

Column k = 2 appears to be 2 * A027383.
The version for runs-resistance is A319411 or A329767.
The cuts-resistance of the binary expansion of n is A319416(n).
The version for compositions is A329861.

Programs

  • Mathematica
    degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
    Table[Length[Select[Tuples[{0,1},n],degdep[#]==k&]],{n,0,10},{k,0,n}]

Formula

For positive indices, T(n,k) = 2 * A319421(n,k).

A329861 Triangle read by rows where T(n,k) is the number of compositions of n with cuts-resistance k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 4, 3, 0, 1, 0, 7, 6, 2, 0, 1, 0, 14, 9, 6, 2, 0, 1, 0, 23, 22, 10, 6, 2, 0, 1, 0, 39, 47, 22, 10, 7, 2, 0, 1, 0, 71, 88, 52, 24, 10, 8, 2, 0, 1, 0, 124, 179, 101, 59, 26, 11, 9, 2, 0, 1, 0, 214, 354, 220, 112, 71, 28, 12, 10, 2, 0, 1
Offset: 0

Views

Author

Gus Wiseman, Nov 23 2019

Keywords

Comments

A composition of n is a finite sequence of positive integers summing to n.
For the operation of shortening all runs by 1, cuts-resistance is defined as the number of applications required to reach an empty word.

Examples

			Triangle begins:
  1
  0  1
  0  1  1
  0  3  0  1
  0  4  3  0  1
  0  7  6  2  0  1
  0 14  9  6  2  0  1
  0 23 22 10  6  2  0  1
  0 39 47 22 10  7  2  0  1
  0 71 88 52 24 10  8  2  0  1
Row n = 6 counts the following compositions (empty columns not shown):
  (6)     (33)    (222)    (11112)  (111111)
  (15)    (114)   (1113)   (21111)
  (24)    (411)   (3111)
  (42)    (1122)  (11121)
  (51)    (1131)  (11211)
  (123)   (1221)  (12111)
  (132)   (1311)
  (141)   (2112)
  (213)   (2211)
  (231)
  (312)
  (321)
  (1212)
  (2121)
		

Crossrefs

Row sums are A000079.
Column k = 1 is A003242 (for n > 0).
Column k = 2 is A329863.
Row sums without the k = 1 column are A261983.
The version for runs-resistance is A329744.
The version for binary vectors is A329860.
The cuts-resistance of the binary expansion of n is A319416.

Programs

  • Mathematica
    degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
    Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],degdep[#]==k&]],{n,0,10},{k,0,n}]

A319421 Triangle read by rows: T(n,k) (1 <= k <= n) = one-half of the number of binary vectors of length n and cuts-resistance k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 6, 6, 2, 1, 1, 10, 11, 7, 2, 1, 1, 14, 24, 14, 8, 2, 1, 1, 22, 42, 35, 16, 9, 2, 1, 1, 30, 81, 68, 45, 18, 10, 2, 1, 1, 46, 138, 149, 89, 55, 20, 11, 2, 1, 1, 62, 250, 282, 216, 110, 66, 22, 12, 2, 1, 1, 94, 419, 577, 422, 285, 132, 78, 24, 13, 2, 1
Offset: 1

Views

Author

N. J. A. Sloane, Sep 23 2018

Keywords

Comments

Cuts-resistance is defined in A319416.
This triangle summarizes the data shown in A319420.
Conjecture (Sloane): Sum_{i = 1..n} i * T(n,i) = A189391(n).

Examples

			Triangle begins:
   1
   1   1
   1   2   1
   1   4   2   1
   1   6   6   2   1
   1  10  11   7   2   1
   1  14  24  14   8   2   1
   1  22  42  35  16   9   2   1
   1  30  81  68  45  18  10   2   1
   1  46 138 149  89  55  20  11   2   1
   1  62 250 282 216 110  66  22  12   2   1
   1  94 419 577 422 285 132  78  24  13   2   1
Lenormand gives first 15 rows.
For example, the "1,2,1" row here refers to the 8 vectors of length 3. There are 2 vectors of cuts-resistance 1, namely 010 and 101 (see A319416), 4 vectors of cuts-resistance 2 (100,011,001,110), and 2 of cuts-resistance 3 (000 and 111). Halving these counts we get 1,2,1
		

Crossrefs

Row sums are A000079.
Column k = 2 appears to be A027383.
The version for runs-resistance is A319411 or A329767.
The version for compositions is A329861.
The cuts-resistance of the binary expansion of n is A319416(n).

Programs

  • Mathematica
    degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
    Table[Length[Select[Tuples[{0,1},n],First[#]==1&°dep[#]==k&]],{n,8},{k,n}] (* Gus Wiseman, Nov 25 2019 *)

Formula

T(n,k) = A329860(n,k)/2. - Gus Wiseman, Nov 25 2019

A189391 The minimum possible value for the apex of a triangle of numbers whose base consists of a permutation of the numbers 0 to n, and each number in a higher row is the sum of the two numbers directly below it.

Original entry on oeis.org

0, 1, 3, 8, 19, 44, 98, 216, 467, 1004, 2134, 4520, 9502, 19928, 41572, 86576, 179587, 372044, 768398, 1585416, 3263210, 6711176, 13775068, 28255568, 57863214, 118430584, 242061468, 494523536, 1009105372, 2058327344, 4194213448
Offset: 0

Views

Author

Nathaniel Johnston, Apr 20 2011

Keywords

Comments

This is the Riordan transform of A000217 (triangular numbers) with the Riordan matrix (of the Bell type) A053121 (inverse of the Chebyshev S Bell matrix). See the resulting formulae below. - Wolfdieter Lang, Feb 18 2017.
Conjecture: a(n) is also half the sum of the "cuts-resistance" (see A319416, A319420, A319421) of all binary vectors of length n (see Lenormand, page 4). - N. J. A. Sloane, Sep 20 2018

Examples

			For n = 4 consider the triangle:
....19
...8  11
..5  3  8
.4  1 2  6
3  1 0 2  4
This triangle has 19 at its apex and no other such triangle with the numbers 0 - 4 on its base has a smaller apex value, so a(4) = 19.
		

Crossrefs

Programs

  • Magma
    m:=30; R:=PowerSeriesRing(Rationals(), m); [0] cat Coefficients(R!((2*x+Sqrt(1-4*x^2)-1)/(2*(2*x-1)^2))); // G. C. Greubel, Aug 24 2018
  • Maple
    a:=proc(n)return add((2*n-4*k-1)*binomial(n,k),k=0..floor((n-1)/2)): end:
    seq(a(n),n=0..50);
  • Mathematica
    CoefficientList[Series[(2*x+Sqrt[1-4*x^2]-1) / (2*(2*x-1)^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 16 2014 *)
  • PARI
    A189391(n)=sum(i=0,(n-1)\2,(2*n-4*i-1)*binomial(n,i))  \\ M. F. Hasler, Jan 24 2012
    

Formula

If n even, a(n) = (n+1/2)*binomial(n,n/2) - 2^(n-1); if n odd, a(n) = ((n+1)/2)*binomial(n+1,(n+1)/2) - 2^(n-1). - N. J. A. Sloane, Nov 01 2018
a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-4*k-1)*binomial(n,k).
G.f.: (2*x+sqrt(1-4*x^2)-1) / (2*(2*x-1)^2). - Alois P. Heinz, Feb 09 2012
a(n) ~ 2^n * (sqrt(2n/Pi)- 1/2). - Vaclav Kotesovec, Mar 16 2014 (formula simplified by Lewis Chen, May 25 2017)
D-finite with recurrence n*a(n) + (n-5)*a(n-1) + 2*(-5*n+6)*a(n-2) + 4*(-n+8)*a(n-3) + 24*(n-3)*a(n-4) = 0. - R. J. Mathar, Jan 04 2017
From Wolfdieter Lang, Feb 18 2017:(Start)
a(n) = Sum_{m=0..n} A053121(n, m)*A000217(m), n >= 0.
G.f.: c(x^2)*Tri(x*c(x^2)), with c and Tri the g.f. of A000108 and A000217, respectively. See the explicit form of the g.f. given above by Alois P. Heinz.
(End)
2*a(n) = A152548(n)-2^n. - R. J. Mathar, Jun 17 2021

A329865 Numbers whose binary expansion has the same runs-resistance as cuts-resistance.

Original entry on oeis.org

0, 8, 12, 14, 17, 24, 27, 28, 35, 36, 39, 47, 49, 51, 54, 57, 61, 70, 73, 78, 80, 99, 122, 130, 156, 175, 184, 189, 190, 198, 204, 207, 208, 215, 216, 226, 228, 235, 243, 244, 245, 261, 271, 283, 295, 304, 313, 321, 322, 336, 352, 367, 375, 378, 379, 380, 386
Offset: 1

Views

Author

Gus Wiseman, Nov 23 2019

Keywords

Comments

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined to be the number of applications required to reach a singleton.
For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

Examples

			The sequence of terms together with their binary expansions begins:
    0:
    8:      1000
   12:      1100
   14:      1110
   17:     10001
   24:     11000
   27:     11011
   28:     11100
   35:    100011
   36:    100100
   39:    100111
   47:    101111
   49:    110001
   51:    110011
   54:    110110
   57:    111001
   61:    111101
   70:   1000110
   73:   1001001
   78:   1001110
   80:   1010000
For example, 36 has runs-resistance 3 because we have (100100) -> (1212) -> (1111) -> (4), while the cuts-resistance is also 3 because we have (100100) -> (00) -> (0) -> ().
Similarly, 57 has runs-resistance 3 because we have (111001) -> (321) -> (111) -> (3), while the cuts-resistance is also 3 because we have (111001) -> (110) -> (1) -> ().
		

Crossrefs

Positions of 0's in A329867.
The version for runs-resistance equal to cuts-resistance minus 1 is A329866.
Compositions with runs-resistance equal to cuts-resistance are A329864.
Runs-resistance of binary expansion is A318928.
Cuts-resistance of binary expansion is A319416.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Binary words counted by runs-resistance are A319411 and A329767.
Binary words counted by cuts-resistance are A319421 and A329860.

Programs

  • Mathematica
    runsres[q_]:=Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1;
    degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
    Select[Range[0,100],#==0||runsres[IntegerDigits[#,2]]==degdep[IntegerDigits[#,2]]&]

A319420 Irregular triangle read by rows: row n lists the cuts-resistances of the 2^n binary vectors of length n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 2, 3, 2, 1, 2, 2, 1, 2, 3, 4, 3, 2, 2, 2, 1, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 5, 4, 3, 3, 3, 2, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 1, 2, 3, 3, 2, 2, 2, 3, 3, 3, 4, 5
Offset: 0

Views

Author

N. J. A. Sloane, Sep 22 2018

Keywords

Comments

The cuts-resistance of a vector is defined in A319416. The 2^n vectors of length n are taken in lexicographic order.
Note that here the vectors can begin with either 0 or 1, whereas in A319416 only vectors beginning with 1 are considered (since there we are considering binary representations of numbers).
Conjecture: The row sums, halved, appear to match A189391.

Examples

			Triangle begins:
0,
1,1,
2,1,1,2,
3,2,1,2,2,1,2,3,
4,3,2,2,2,1,2,3,3,2,1,2,2,2,3,4,
5,4,3,3,3,2,2,3,3,2,1,2,2,2,3,4,4,3,2,2,2,1,2,3,3,2,2,2,3,3,3,4,5,
...
		

Crossrefs

Keeping the first digit gives A319416.
Positions of 1's are the terms > 1 of A061547 and A086893, all minus 1.
The version for runs-resistance is A329870.
Compositions counted by cuts-resistance are A329861.
Binary words counted by cuts-resistance are A319421 or A329860.

Programs

  • Mathematica
    degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
    Table[degdep[Rest[IntegerDigits[n,2]]],{n,0,50}] (* Gus Wiseman, Nov 25 2019 *)

A329862 Positive integers whose binary expansion has cuts-resistance 2.

Original entry on oeis.org

3, 4, 6, 9, 11, 12, 13, 18, 19, 20, 22, 25, 26, 37, 38, 41, 43, 44, 45, 50, 51, 52, 53, 74, 75, 76, 77, 82, 83, 84, 86, 89, 90, 101, 102, 105, 106, 149, 150, 153, 154, 165, 166, 169, 171, 172, 173, 178, 179, 180, 181, 202, 203, 204, 205, 210, 211, 212, 213
Offset: 1

Views

Author

Gus Wiseman, Nov 23 2019

Keywords

Comments

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

Examples

			The sequence of terms together with their binary expansions begins:
   3:      11
   4:     100
   6:     110
   9:    1001
  11:    1011
  12:    1100
  13:    1101
  18:   10010
  19:   10011
  20:   10100
  22:   10110
  25:   11001
  26:   11010
  37:  100101
  38:  100110
  41:  101001
  43:  101011
  44:  101100
  45:  101101
  50:  110010
		

Crossrefs

Positions of 2's in A319416.
Numbers whose binary expansion has cuts-resistance 1 are A000975.
Binary words with cuts-resistance 2 are conjectured to be A027383.
Compositions with cuts-resistance 2 are A329863.
Cuts-resistance of binary expansion without first digit is A319420.
Binary words counted by cuts-resistance are A319421 and A329860.
Compositions counted by cuts-resistance are A329861.

Programs

  • Mathematica
    degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
    Select[Range[100],degdep[IntegerDigits[#,2]]==2&]
Showing 1-10 of 19 results. Next