login
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
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
------- -------- --------
A215244 A011782 Substrings are palindromes.
A301453 A003242 This sequence; no two consecutive equal substrings.
A302395 A032020 All substrings are distinct.
A302436 A000012 Substrings with Hamming weight at most 1.
A302437 A000045 Substrings with Hamming weight at most 2.
A302439 A000012 Substrings are aperiodic.
For any such sequence f, the function n -> f(2^n-1) corresponds to a composition of n.
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))
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Apr 08 2018
STATUS
approved