A302437 a(n) is the number of ways of writing the binary expansion of n as a concatenation of nonempty substrings with Hamming weight at most 2.

1, 1, 2, 2, 4, 4, 4, 3, 8, 8, 8, 7, 8, 7, 6, 5, 16, 16, 16, 15, 16, 15, 14, 11, 16, 15, 14, 13, 12, 11, 10, 8, 32, 32, 32, 31, 32, 31, 30, 23, 32, 31, 30, 27, 28, 25, 22, 18, 32, 31, 30, 29, 28, 27, 26, 20, 24, 23, 22, 20, 20, 18, 16, 13, 64, 64, 64, 63, 64

Offset

0,3

Comments

Leading zeros in the binary expansion of n are ignored.

The value a(0) = 1 corresponds to the empty concatenation.

See A301453 for similar sequences.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..10000

Formula

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

a(2^n) = 2^n for any n >= 0.

a(2*n) = 2*a(n) for any n > 0.

If 1 <= A000120(n) <= 2 then a(n) = A053644(n).

Example

For n = 14: the binary expansion of 14, "1110", can be split in 6 ways into substrings with Hamming weight at most 2:
- (11)(10),
- (11)(1)(0),
- (1)(110),
- (1)(11)(0),
- (1)(1)(10),
- (1)(1)(1)(0).
Hence a(14) = 6.

Prog

(PARI) a(n) = if (n==0, return (1), my (v=0, h=0); while (n, h += n%2; n\=2; if (h>2, break, v += a(n))); return (v))

Crossrefs

Cf. A000045, A000120, A053644, A301453.

Sequence in context: A165956 A263991 A065285 * A179932 A267649 A071805

Adjacent sequences: A302434 A302435 A302436 * A302438 A302439 A302440

Keyword

nonn,base

Author

Rémy Sigrist, Apr 08 2018

Status

approved