A302436 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 1.

1, 1, 2, 1, 4, 3, 2, 1, 8, 7, 6, 3, 4, 3, 2, 1, 16, 15, 14, 7, 12, 9, 6, 3, 8, 7, 6, 3, 4, 3, 2, 1, 32, 31, 30, 15, 28, 21, 14, 7, 24, 21, 18, 9, 12, 9, 6, 3, 16, 15, 14, 7, 12, 9, 6, 3, 8, 7, 6, 3, 4, 3, 2, 1, 64, 63, 62, 31, 60, 45, 30, 15, 56, 49, 42, 21

Offset: 0

Author

Rémy Sigrist, Apr 08 2018

Keywords

• nonn
• base

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.

Examples

			For n = 9: the binary expansion of 9, "1001", can be split in 7 ways into nonempty substrings with Hamming weight at most 1:
- (100)(1),
- (10)(01),
- (10)(0)(1),
- (1)(001),
- (1)(00)(1),
- (1)(0)(01),
- (1)(0)(0)(1).
Hence a(9) = 7.
		

Links

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

Crossrefs

Cf. A301453.

Programs

PARI

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

Formula

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

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

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