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
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
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Apr 07 2018
STATUS
approved