A306921 Number of ways of breaking the binary expansion of n into consecutive blocks with no leading zeros.

1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 6, 6, 6, 6, 8, 8, 5, 5, 8, 8, 9, 9, 12, 12, 8, 8, 12, 12, 12, 12, 16, 16, 6, 6, 10, 10, 12, 12, 16, 16, 12, 12, 18, 18, 18, 18, 24, 24, 10, 10, 16, 16, 18, 18, 24, 24, 16, 16, 24, 24, 24, 24, 32, 32, 7, 7, 12, 12, 15, 15, 20, 20, 16

Offset

0,3

Comments

The number 0 is not considered to have a leading zero.

a(n) >= 2^(A000120(n) - 1).

a(2^n - 1) = 2^(n-1) for n > 0.

a(2^n) = n+1.

Conjecture: n appears A067824(n) times for n > 1.

Links

Peter Kagey, Table of n, a(n) for n = 0..8192

Formula

From Charlie Neder, May 08 2019: (Start)

If n = k*2^e + {0,1} with k odd and e > 0, then a(n) = a(k)*(e+1).

Proof: Each partition of n is uniquely determined by a partition of k (call it K) and a choice of some number, from 0 to e, of trailing digits to append to the final part in K, since any remaining digits must appear as singletons. The conjecture follows, since each ordered factorization of a number m produces two numbers n such that a(n) = m, one of each parity, and A067824(n) = 2*A074206(n).

Corollary: For n >= 1, a(2n) = a(2n+1) = Product{k+1 | k in row n of A066099}. (End)

Example

For n = 13 the a(13) = 6 partitions are [1101], [1, 101], [110, 1], [1, 10, 1], [11, 0, 1], and [1, 1, 0, 1].
Notice that [1, 1, 01] and [11, 01] are not valid partitions because the last part has a leading zero.

Crossrefs

Cf. A000120, A067824, A074206, A066099.

A321318 gives number of distinct sums of such partitions.

Sequence in context: A117695 A074794 A234309 * A048686 A278959 A090501

Adjacent sequences: A306918 A306919 A306920 * A306922 A306923 A306924

Keyword

nonn,base

Author

Peter Kagey, Mar 16 2019

Status

approved