cp's OEIS Frontend

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)

In binary form, because the sequence 10101_2... keeps repeating, one can represent a(n) = floor(0.(10)2 * 2^n). Because 0.(10)_2 = 0.(10)_2 * 4 - 2, then 0.(10)_2 = 2/3. Substituting this value in the first expression, we obtain a(n) = floor(2^(n+1)/3). This also agrees with the formula of Paul Barry, Oct 08 2005. - _Giovanni Ciriani, Mar 31 2025

The length of each row is A005186(n). The largest number in row n is 2^n. The second-largest number in row n is A000975(n-2) for n>4. The smallest number in row n is A033491(n). The Collatz conjecture asserts that every positive integer occurs in some row of this triangle.

n is an element of row number A006577(n). - Reinhard Zumkeller, Oct 03 2012

Conjecture: The numbers T(n, 1),...,T(n, k_n) of row n are arranged in non-overlapping clusters of numbers which have the same order of magnitude and whose Collatz trajectories to 1 have the same numbers of ups and downs. The highest cluster of row n is just the number 2^n, the trajectory to 1 of which has n-1 downs and no ups. The second highest cluster of row n consists of the numbers T(n, k_n - r) = 4^(r - 1) * t(n - 2*r + 2) for 1 <= r <= (n - 3) / 2, where t(k) = (2^k - (-1)^k - 3) / 6. These have n-2 downs and one up. The largest and second largest number of this latter cluster are given by A000975 and A153772. - Markus Sigg, Sep 25 2020

From Wolfdieter Lang, Nov 26 2013: (Start)

The length of row (level) l of this table is A005186(l).

The (incomplete) ternary subtree starting with the vertex labeled 8 at level l=3 obeys the rules: (i) The three possible edge (branch) labels are L, V, R (for left, vertical and right). (ii) If the vertex label m is congruent to 4 modulo 6 then the out-degree is 2 and the edge labeled L ends in a vertex with label (m-1)/3 and the edge labeled R ends in a vertex with label 2*m. Otherwise (if the vertex label m is congruent to 0, 1, 2, 3, 5 (mod 6)) the out-degree is 1 with the edge labeled V ending in a vertex with label 2*m. See the Python program.

On top of this tree starting with node label 8 one puts the unary tree (out-degree 1) with vertex labels 1, 2, and 4, where each edge label is V. The 1, at level l=0, labels the root of the Collatz tree CT. Note that 4 at level l=2 has out-degree 1 and not 2 even though 4 == 4 (mod 6). This exception is needed because otherwise the L branch would result in a repetition of the whole CT tree.

Alternatively one could start a Collatz tree with vertex label 4 at level 0, using the above given rules, but cut off the L branch originating from 4 after level 2 (out-degree of vertex labeled 2 is 0). Without this cut 4 would appear again and the whole tree would be repeated.

The number of vertex labels with CT(l,k) == 4 (mod 6) with l >= 3 is A176866(l+1).

From level l=16 on the left-right symmetry in the branch structure (forgetting about the vertex labels) of the subtree starting with label 16 at level l=4 is no longer present because the row length A005186(16) = 29, which is odd. (End)

Decimal expansion of the solution to n/x = x-n for n-3. n/x = x-n with n=1 gives the Golden Ratio = 1.6180339887...

n/x = x-n ==> x^2 - n*x - n = 0 ==> x = (n + sqrt(n^2 + 4*n)) / 2 (Positive Root) n = 3: x = (3 + sqrt(21))/2 = 3.79128784747792...

x=3.7912878474... is the shape of a rectangle whose geometric partition (as at A188635) consists of 3 squares, then 1 square, then 3 squares, etc., matching the continued fraction of x, which is [3,1,3,1,3,1,3,1,3,1,...]. (See the Mathematica program below.) - Clark Kimberling, May 05 2011

x appears to be the limit for n to infinity of the ratio of the number of even numbers that take n steps to reach 1 to the number of odd numbers that take n steps to reach 1 in the Collatz iteration. As A005186(n-1) is the number of even numbers that take n steps to reach 1, this means x = lim A005186(n-1)/A176866(n). - Markus Sigg, Oct 20 2020

From Wolfdieter Lang, Sep 02 2022: (Start)

This integer in the quadratic number field Q(sqrt(21)) equals the (real) cube root of 27 + 6*sqrt(21) = 54.4954541... . See Euler, Elements of Algebra, Article 748 or Algebra (in German) p. 306, Kapitel 12, 187.

Subtracting 3 from the present number gives the (real) cube root of

-27 + 6*sqrt(21) = 0.4954541... . (End)

Both the 3x+1 steps and the halving steps are counted. The asymptotic growth rate appears to be the same as A005186, about 1.26 (A176014).

a(n) is, for n >= 4, the number of 4 (mod 6) nodes (vertices) of row n-1 of the Collatz tree A127824. The node 4 has in A127824 outdegree 1 in order to avoid a repetition of the whole tree. - Wolfdieter Lang, Mar 26 2014

The heuristic arguments given in the LINKS of A005186 suggest that this sequence has the same asymptotic growth rate (3+sqrt(21))/6. - Markus Sigg, Sep 07 2024

The array of T(n,k) with T(0,k) = A141325(k) and successive differences T(n,k) = T(n-1,k+1) - T(n-1,k) in further rows is

1, 1, 1, 1, 3, 5, 9, 13, 21, 33, 55,..

0, 0, 0, 2, 2, 4, 4, 8, 12, 22,..

0, 0, 2, 0, 2, 0, 4, 4, 10,...

0, 2, -2, 2, -2, 4, 0, 6,..

2, -4, 4, -4, 6, -4, 6,..

-6, 8, -8, 10, -10, 10,...

with T(n,n) = A078008(n), T(n,n+1) = -A167030(n), T(n,n+2) = A128209(n), T(n,n+3) = -a(n). All these sequences along the diagonals obey the recurrences a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) and a(n) = 5*a(n-2) - 4*a(n-4).

Conjecture: For n >= 6, a(n) is the third largest natural number whose Collatz orbit has length n+2. - Markus Sigg, Sep 14 2020

Continued fraction expansion of (3+sqrt(21))/6 is A010684.

Also greatest eigenvalue of the 6 X 6 matrix [[3 0 0 3 0 0][0 0 0 0 1 0][0 3 0 0 3 0][0 0 0 0 1 0][0 0 3 0 0 3][0 0 0 0 1 0]]/3. It is conjectured that this is lim_{k->infinity} A005186(k+1)/A005186(k), i.e., the asymptotic growth rate of the number of numbers with the same total stopping time in the Collatz iteration. - Hugo Pfoertner, Sep 28 2020

It is conjectured that no further terms exist.

Michael S. Branicky checked this up to 2*10^9 and found no starting values other than the 74 terms given in A355239 and also in the attached file.

The terms of this sequence are expected to be close to the sum of numerators and denominators in a rational approximation of log(2)/log(3). See A355514, which shares terms 3, 8, 13, 44, 75.

Anderson (1987) reformulates the 3x+1 conjecture using this function.