cp's OEIS Frontend

A302395 a(n) is the number of ways of writing the binary expansion of n as a concatenation of distinct nonempty substrings.

%I A302395 #13 Apr 15 2018 15:03:13
%S A302395 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,
%T A302395 14,19,19,17,17,16,18,17,19,16,17,16,17,16,19,13,15,17,17,14,15,16,17,
%U A302395 12,18,17,19,12,15,13,14,11,25,31,30,29,27,29,31,30
%N A302395 a(n) is the number of ways of writing the binary expansion of n as a concatenation of distinct nonempty substrings.
%C A302395 Leading zeros in the binary expansion of n are ignored.
%C A302395 The value a(0) = 1 corresponds to the empty concatenation.
%C A302395 See A301453 for similar sequences.
%H A302395 Rémy Sigrist, <a href="/A302395/b302395.txt">Table of n, a(n) for n = 0..10000</a>
%H A302395 Rémy Sigrist, <a href="/A302395/a302395.png">Scatterplot of the second ordinal transform of the first 750000 terms</a>
%H A302395 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A302395 a(2^n - 1) = A032020(n) for any n >= 0.
%e A302395 For n = 7: the binary expansion of 7, "111", can be split in 3 ways into distinct nonempty substrings:
%e A302395 - (111),
%e A302395 - (11)(1),
%e A302395 - (1)(11).
%e A302395 Hence a(7) = 3.
%e A302395 For n = 42: the binary expansion of 42, "101010", can be split in 17 ways into distinct nonempty substrings:
%e A302395 - (101010),
%e A302395 - (10101)(0),
%e A302395 - (1010)(10),
%e A302395 - (1010)(1)(0),
%e A302395 - (101)(010),
%e A302395 - (101)(01)(0),
%e A302395 - (101)(0)(10),
%e A302395 - (10)(1010),
%e A302395 - (10)(101)(0),
%e A302395 - (10)(1)(010),
%e A302395 - (10)(1)(01)(0),
%e A302395 - (1)(01010),
%e A302395 - (1)(0101)(0),
%e A302395 - (1)(010)(10),
%e A302395 - (1)(01)(010),
%e A302395 - (1)(01)(0)(10),
%e A302395 - (1)(0)(1010).
%e A302395 Hence a(42) = 17.
%o A302395 (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))
%Y A302395 Cf. A032020, A301453.
%K A302395 nonn,base
%O A302395 0,3
%A A302395 _Rémy Sigrist_, Apr 07 2018