cp's OEIS Frontend

This sequence is different from A055944. For example, A055944(5) = 10 and a(5) = 9.

More precisely, a(n)=sum(iA159913(i)), since we want the sequence to start with a(0)=0 and not with A159913(0)=1.

a(n) is also the total number of ON cells after n generations in the outward corner version of the Ulam-Warburton cellular automaton of A147562, and a(n) is also the total number of Y-toothpicks after n generations in the outward corner version of the Y-toothpick structure of A160120. - David Applegate and Omar E. Pol, Jan 24 2016

Contains m*(2^k-1) for 1 <= m <= 2^k + 2 and any k >= 1. - Robert Israel, Aug 04 2016

Row sums of number the number triangle (A106522 mod 2).

The plot of the sequence has a blancmange appearance. The discontinuities in the curve are at a(n) = k^2 + 1.

The bit length of a(n+1) appears to be A000267(n)+1.

The number of 0-bits in the binary expansion of a(n+1) appears to be A082375(n).

Also called Dress's sequence.

This sequence might be better called Glaisher's sequence, since James Glaisher showed that odd binomial coefficients are counted by 2^A000120(n) in 1899. - Eric Rowland, Mar 17 2017 [However, the name "Gould's sequence" is deeply entrenched in the literature. - N. J. A. Sloane, Mar 17 2017] [Named after the American mathematician Henry Wadsworth Gould (b. 1928). - Amiram Eldar, Jun 19 2021]

All terms are powers of 2. The first occurrence of 2^k is at n = 2^k - 1; e.g., the first occurrence of 16 is at n = 15. - Robert G. Wilson v, Dec 06 2000

a(n) is the highest power of 2 dividing binomial(2n,n) = A000984(n). - Benoit Cloitre, Jan 23 2002

Also number of 1's in n-th row of triangle in A070886. - Hans Havermann, May 26 2002. Equivalently, number of live cells in generation n of a one-dimensional cellular automaton, Rule 90, starting with a single live cell. - Ben Branman, Feb 28 2009. Ditto for Rule 18. - N. J. A. Sloane, Aug 09 2014. This is also the odd-rule cellular automaton defined by OddRule 003 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015

Also number of numbers k, 0<=k<=n, such that (k OR n) = n (bitwise logical OR): a(n) = #{k : T(n,k)=n, 0<=k<=n}, where T is defined as in A080098. - Reinhard Zumkeller, Jan 28 2003

To construct the sequence, start with 1 and use the rule: If k >= 0 and a(0),a(1),...,a(2^k-1) are the first 2^k terms, then the next 2^k terms are 2*a(0),2*a(1),...,2*a(2^k-1). - Benoit Cloitre, Jan 30 2003

Also, numerator((2^k)/k!). - Mohammed Bouayoun (mohammed.bouayoun(AT)sanef.com), Mar 03 2004

The odd entries in Pascal's triangle form the Sierpiński Gasket (a fractal). - Amarnath Murthy, Nov 20 2004

Row sums of Sierpiński's Gasket A047999. - Johannes W. Meijer, Jun 05 2011

Fixed point of the morphism "1" -> "1,2", "2" -> "2,4", "4" -> "4,8", ..., "2^k" -> "2^k,2^(k+1)", ... starting with a(0) = 1; 1 -> 12 -> 1224 -> = 12242448 -> 122424482448488(16) -> ... . - Philippe Deléham, Jun 18 2005

a(n) = number of 1's of stage n of the one-dimensional cellular automaton with Rule 90. - Andras Erszegi (erszegi.andras(AT)chello.hu), Apr 01 2006

a(33)..a(63) = A117973(1)..A117973(31). - Stephen Crowley, Mar 21 2007

Or the number of solutions of the equation: A000120(x) + A000120(n-x) = A000120(n). - Vladimir Shevelev, Jul 19 2009

For positive n, a(n) equals the denominator of the permanent of the n X n matrix consisting entirely of (1/2)'s. - John M. Campbell, May 26 2011

Companions to A001316 are A048896, A105321, A117973, A151930 and A191488. They all have the same structure. We observe that for all these sequences a((2*n+1)*2^p-1) = C(p)*A001316(n), p >= 0. If C(p) = 2^p then a(n) = A001316(n), if C(p) = 1 then a(n) = A048896(n), if C(p) = 2^p+2 then a(n) = A105321(n+1), if C(p) = 2^(p+1) then a(n) = A117973(n), if C(p) = 2^p-2 then a(n) = (-1)*A151930(n) and if C(p) = 2^(p+1)+2 then a(n) = A191488(n). Furthermore for all a(2^p - 1) = C(p). - Johannes W. Meijer, Jun 05 2011

a(n) = number of zeros in n-th row of A219463 = number of ones in n-th row of A047999. - Reinhard Zumkeller, Nov 30 2012

This is the Run Length Transform of S(n) = {1,2,4,8,16,...} (cf. A000079). The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - N. J. A. Sloane, Sep 05 2014

A105321(n+1) = a(n+1) + a(n). - Reinhard Zumkeller, Nov 14 2014

a(n) = A261363(n,n) = number of distinct terms in row n of A261363 = number of odd terms in row n+1 of A261363. - Reinhard Zumkeller, Aug 16 2015

From Gary W. Adamson, Aug 26 2016: (Start)

A production matrix for the sequence is lim_{k->infinity} M^k, the left-shifted vector of M:

1, 0, 0, 0, 0, ...

2, 0, 0, 0, 0, ...

0, 1, 0, 0, 0, ...

0, 2, 0, 0, 0, ...

0, 0, 1, 0, 0, ...

0, 0, 2, 0, 0, ...

0, 0, 0, 1, 0, ...

...

The result is equivalent to the g.f. of Apr 06 2003: Product_{k>=0} (1 + 2*z^(2^k)). (End)

Number of binary palindromes of length n for which the first floor(n/2) symbols are themselves a palindrome (Ji and Wilf 2008). - Jeffrey Shallit, Jun 15 2017

Poly-Bernoulli numbers B_n^(k) with k=-2.

Binomial transform of A007051, if both sequences start at 0. Binomial transform of A000225(n+1). - Paul Barry, Mar 24 2003

Euler expands (1-z)/(1-5z+6z^2) and finds the general term. Section 226 of the Introductio indicates that he could have written down the recursion relation: a(n) = 5 a(n-1)-6 a(n-2). - V. Frederick Rickey (fred-rickey(AT)usma.edu), Feb 10 2006

Let R be a binary relation on the power set P(A) of a set A having n = |A| elements such that for every element x, y of P(A), xRy if x is a subset of y or y is a subset of x. Then a(n) = |R|. - Ross La Haye, Dec 22 2006

With regard to the comment by Ross La Haye: For proper subsets see A056182. - For nonempty subsets see A091344. - For nonempty proper subsets see a(n+1) in A260217. - Manfred Boergens, Aug 02 2023

If x, y are two n-bit binary strings then a(n) gives the number of pairs (x,y) such that XOR(x, y) = ABS(x - y). - Ramasamy Chandramouli, Feb 15 2009

Equals row sums of the triangular version of A038573. - Gary W. Adamson, Jun 04 2009

Inverse binomial transform of A085350. - Paul Curtz, Nov 14 2009

Related to the number of even a's in a nontrivial cycle (should one exist) in the 3x+1 Problem, where a <= floor(log_2(2*(3^n) - 2^n)). The value n correlates to the number of odds in such a nontrivial cycle. See page 1288 of Crandall's paper. Also, this relation gives another proof that the number of odds divided by the number of evens in a nontrivial cycle is bounded by log 2 / log 3 (this observation does not resolve the finite cycles conjecture as the value could be arbitrarily close to this bound). However, the same argument gives that log 2 / log 3 is less than or equal to the number of odds divided by the number of evens in a divergent sequence (should one exist), as log 2 / log 3 is the limit value for a cycle of an arbitrarily large length, where the length is given by the value n. - Jeffrey R. Goodwin, Aug 04 2011

Row sums of Riordan triangle A106516. - Wolfdieter Lang, Jan 09 2015

Number of restricted barred preferential arrangements having 3 bars in which the sections are all restricted sections such that (for fixed sections i and j) section i or section j is empty. - Sithembele Nkonkobe, Oct 12 2015

This is also row 2 of A281891: for n >= 1, when consecutive positive integers are written as a product of primes in nondecreasing order, a factor of 2 or 3 occurs in n-th position a(n) times out of every 6^n. - Peter Munn, May 18 2017

Also row sums of A124929. - Omar E. Pol, Jun 15 2017

This is the sum of A318921(n) for n in the range 2^(k+1) to 2^(k+2)-1. See A318921 for proof. - N. J. A. Sloane, Sep 25 2018

a(n) is also the number of acyclic orientations of the complete bipartite graph K_{2,n}. - Vincent Pilaud, Sep 15 2020

a(n-1) is also the number of n-digit numbers whose largest decimal digit is 2. - Stefano Spezia, Nov 15 2023

Guy Steele defines a family of 36 integer sequences, denoted here by GS(i,j) for 1 <= i, j <= 6, as follows. a[1]=1; a[2n] = i-th term of {0,1,a[n],a[n]+1,2a[n],2a[n]+1}; a[2n+1] = j-th term of {0,1,a[n],a[n]+1,2a[n],2a[n]+1}. The present sequence is GS(1,5).

The full list of 36 sequences:

GS(1,1) = A000007

GS(1,2) = A000035

GS(1,3) = A036987

GS(1,4) = A007814

GS(1,5) = A135416 (the present sequence)

GS(1,6) = A135481

GS(2,1) = A135528

GS(2,2) = A000012

GS(2,3) = A000012

GS(2,4) = A091090

GS(2,5) = A135517

GS(2,6) = A135521

GS(3,1) = A036987

GS(3,2) = A000012

GS(3,3) = A000012

GS(3,4) = A000120

GS(3,5) = A048896

GS(3,6) = A038573

GS(4,1) = A135523

GS(4,2) = A001511

GS(4,3) = A008687

GS(4,4) = A070939

GS(4,5) = A135529

GS(4,6) = A135533

GS(5,1) = A048298

GS(5,2) = A006519

GS(5,3) = A080100

GS(5,4) = A087808

GS(5,5) = A053644

GS(5,6) = A000027

GS(6,1) = A135534

GS(6,2) = A038712

GS(6,3) = A135540

GS(6,4) = A135542

GS(6,5) = A054429

GS(6,6) = A003817

(with a(0)=1): Moebius transform of A038712.

From Trevor Green (green(AT)snoopy.usask.ca), Nov 26 2003: (Start)

a(n)/n has an accumulation point at x exactly when x is in the interval [1, 2]. Proof: Clearly n <= a(n) < 2n. Let b(n) = a(n)/n, then b(n) must always lie in [1,2) and all the accumulation points of the sequence must lie in [1,2]. We shall show that every such number is an accumulation point.

First, consider any d-bit integer n. Suppose that z of these bits are 0. Let n' be the (d+z)-bit integer whose first d bits are the same as those of n and whose remaining bits are all 1. Then a(n') will have to be the (d+z)-bit integer whose first d bits are all 1 and whose last z bits are all 0.

Thus n' = (n+1)*2^z-1; a(n') = (2^d-1)2^z; and b(n') = (2^d-1)/(n+1) + epsilon, where 0 < epsilon < 2^(1-d). So to get an accumulation point x, we just choose n(d) to be the d-bit integer such that (2^d-1)/(n(d)+1) < x <= (2^d-1)/n(d), or equivalently, n(d) = floor((2^d-1)/x). If x lies in [1,2), then n(d) will always be a d-bit number for sufficiently large d.

Then n'(d) yields an increasing subsequence of the integers for which b(n'(d)) converges to x. For x = 2, choose n(d) = 2^(d-1), which is always a d-bit number; then b(n'(d)) = (2^d-1)/(2^(d-1)+1) + epsilon = 2 + epsilon', where epsilon' also heads for 0 as d blows up. This proves the claim.

(End)

Conjecture: this is also the "tree" sequence in a 120-degree sector of the cellular automaton of A266532.

It appears that this is also the partial sums of A038573.

a(n) is also the total number of ON cells after n-th stage in the tree that arises from one of the four spokes in a 90-degree sector of the cellular automaton A160720 on the square grid.

Note that the structure of A160720 is also the "outward" version of the Ulam-Warburton cellular automaton of A147562.

It appears that A038573 gives the number of cells turned ON at n-th stage.

Conjecture: a(n) is also the total number of Y-toothpicks after n-th stage in the tree that arises from one of the three spokes in a 120-degree sector of the cellular automaton of A266532 on the triangular grid.

Note that the structure of A266532 is also the "outward" version of the Y-toothpick cellular automaton of A160120.

It appears that A038573 also gives the number of Y-toothpicks added at n-th stage.

Comment from N. J. A. Sloane, Jan 23 2016: All the above conjectures are true!

From Gus Wiseman, Mar 31 2019: (Start)

a(n) is also the number of nondecreasing binary-containment pairs of positive integers up to n. A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second. For example, the a(1) = 1 through a(6) = 12 pairs are:

(1,1) (1,1) (1,1) (1,1) (1,1) (1,1)

(2,2) (1,3) (1,3) (1,3) (1,3)

(2,2) (2,2) (1,5) (1,5)

(2,3) (2,3) (2,2) (2,2)

(3,3) (3,3) (2,3) (2,3)

(4,4) (3,3) (2,6)

(4,4) (3,3)

(4,5) (4,4)

(5,5) (4,5)

(4,6)

(5,5)

(6,6)

(End)