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

Author

Peter Kagey, Mar 16 2019

Keywords

• nonn
• base

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A000120, A067824, A074206, A066099.

A321318 gives number of distinct sums of such partitions.

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)