

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Leading zeros in the binary expansion of n are ignored.
The value a(0) = 1 corresponds to the empty concatenation.


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



STATUS

approved



