login
A302395
a(n) is the number of ways of writing the binary expansion of n as a concatenation of distinct nonempty substrings.
2
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,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.
FORMULA
a(2^n - 1) = A032020(n) for any n >= 0.
EXAMPLE
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.
PROG
(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))
CROSSREFS
Sequence in context: A239619 A085599 A299966 * A110425 A174257 A105637
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Apr 07 2018
STATUS
approved