|
|
A301453
|
|
a(n) is the number of ways of writing the binary expansion of n as a concatenation of nonempty substrings with no two consecutive equal substrings.
|
|
6
|
|
|
1, 1, 2, 1, 3, 4, 3, 3, 6, 7, 7, 6, 5, 6, 6, 4, 10, 13, 14, 11, 11, 14, 14, 12, 9, 11, 11, 9, 9, 12, 10, 7, 17, 23, 26, 20, 20, 26, 25, 21, 23, 26, 28, 22, 22, 27, 26, 20, 16, 20, 22, 17, 17, 22, 20, 18, 18, 21, 23, 18, 16, 20, 17, 14, 31, 40, 46, 36, 39, 49
(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.
The following sequences f correspond to the numbers of ways of writing the binary expansion of a number as a concatenation of substrings with some specific features:
f f(2^n-1) Features
------- -------- --------
For any such sequence f, the function n -> f(2^n-1) corresponds to a composition of n.
|
|
LINKS
|
|
|
FORMULA
|
a(2^n - 1) = A003242(n) for any n >= 0.
|
|
EXAMPLE
|
For n = 19: the binary expansion of 19, "10011", can be split in 11 ways into nonempty substrings with no two consecutive equal substrings:
- (10011),
- (1001)(1),
- (100)(11),
- (10)(011),
- (10)(01)(1),
- (10)(0)(11),
- (1)(0011),
- (1)(001)(1),
- (1)(00)(11),
- (1)(0)(011),
- (1)(0)(01)(1).
Hence a(19) = 11.
|
|
PROG
|
(PARI) a(n{, pp=0}) = if (n==0, return (1), my (v=0, p=1); while (n, p=(p*2) + (n%2); n\=2; if (p!=pp, v+=a(n, p))); return (v))
|
|
CROSSREFS
|
Cf. A000012, A000045, A003242, A011782, A032020, A215244, A301453, A302395, A302436, A302437, A302439.
|
|
KEYWORD
|
nonn,base
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|