cp's OEIS Frontend

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.

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