|
%I #47 Apr 15 2018 15:03:06
%S 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,
%T 12,10,7,17,23,26,20,20,26,25,21,23,26,28,22,22,27,26,20,16,20,22,17,
%U 17,22,20,18,18,21,23,18,16,20,17,14,31,40,46,36,39,49
%N 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.
%C Leading zeros in the binary expansion of n are ignored.
%C The value a(0) = 1 corresponds to the empty concatenation.
%C 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:
%C f f(2^n-1) Features
%C ------- -------- --------
%C A215244 A011782 Substrings are palindromes.
%C A301453 A003242 This sequence; no two consecutive equal substrings.
%C A302395 A032020 All substrings are distinct.
%C A302436 A000012 Substrings with Hamming weight at most 1.
%C A302437 A000045 Substrings with Hamming weight at most 2.
%C A302439 A000012 Substrings are aperiodic.
%C For any such sequence f, the function n -> f(2^n-1) corresponds to a composition of n.
%H Rémy Sigrist, <a href="/A301453/b301453.txt">Table of n, a(n) for n = 0..10000</a>
%H Rémy Sigrist, <a href="/A301453/a301453.png">Scatterplot of the second ordinal transform of the first 1000000 terms</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F a(2^n - 1) = A003242(n) for any n >= 0.
%e For n = 19: the binary expansion of 19, "10011", can be split in 11 ways into nonempty substrings with no two consecutive equal substrings:
%e - (10011),
%e - (1001)(1),
%e - (100)(11),
%e - (10)(011),
%e - (10)(01)(1),
%e - (10)(0)(11),
%e - (1)(0011),
%e - (1)(001)(1),
%e - (1)(00)(11),
%e - (1)(0)(011),
%e - (1)(0)(01)(1).
%e Hence a(19) = 11.
%o (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))
%Y Cf. A000012, A000045, A003242, A011782, A032020, A215244, A301453, A302395, A302436, A302437, A302439.
%K nonn,base
%O 0,3
%A _Rémy Sigrist_, Apr 08 2018
|
