A302395 a(n) is the number of ways of writing the binary expansion of n as a concatenation of distinct nonempty substrings.

1, 1, 2, 1, 3, 3, 3, 3, 6, 6, 6, 5, 5, 5, 6, 3, 9, 10, 10, 9, 9, 8, 10, 9, 9, 9, 9, 7, 9, 9, 9, 5, 14, 19, 19, 17, 17, 16, 18, 17, 19, 16, 17, 16, 17, 16, 19, 13, 15, 17, 17, 14, 15, 16, 17, 12, 18, 17, 19, 12, 15, 13, 14, 11, 25, 31, 30, 29, 27, 29, 31, 30

Offset: 0

Author

Rémy Sigrist, Apr 07 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 = 7: the binary expansion of 7, "111", can be split in 3 ways into distinct nonempty substrings:
- (111),
- (11)(1),
- (1)(11).
Hence a(7) = 3.
For n = 42: the binary expansion of 42, "101010", can be split in 17 ways into distinct nonempty substrings:
- (101010),
- (10101)(0),
- (1010)(10),
- (1010)(1)(0),
- (101)(010),
- (101)(01)(0),
- (101)(0)(10),
- (10)(1010),
- (10)(101)(0),
- (10)(1)(010),
- (10)(1)(01)(0),
- (1)(01010),
- (1)(0101)(0),
- (1)(010)(10),
- (1)(01)(010),
- (1)(01)(0)(10),
- (1)(0)(1010).
Hence a(42) = 17.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..10000
• Rémy Sigrist, Scatterplot of the second ordinal transform of the first 750000 terms
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A032020, A301453.

Programs

PARI

a(n{, s=Set()}) = if (n==0, return (1), my (v=0, p=1); while (n, p=(p*2) + (n%2); n\=2; if (!setsearch(s, p), v+=a(n, setunion(s, Set(p))))); return (v))

Formula

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