cp's OEIS Frontend

A302439 a(n) is the number of ways of writing the binary expansion of n as a concatenation of nonempty aperiodic substrings (i.e., substrings that are not the concatenation of 2 or more equal parts).

%I A302439 #19 Apr 15 2018 15:03:34
%S A302439 1,1,2,1,3,3,3,1,4,4,6,4,5,5,4,1,5,5,10,5,10,9,11,5,7,7,10,7,7,7,5,1,
%T A302439 6,6,14,6,16,15,16,6,14,14,19,13,18,17,16,6,9,9,17,9,16,15,17,9,10,10,
%U A302439 14,10,9,9,6,1,7,7,18,7,24,21,21,7,23,22,32,22
%N A302439 a(n) is the number of ways of writing the binary expansion of n as a concatenation of nonempty aperiodic substrings (i.e., substrings that are not the concatenation of 2 or more equal parts).
%C A302439 Leading zeros in the binary expansion of n are ignored.
%C A302439 The value a(0) = 1 corresponds to the empty concatenation.
%C A302439 See A301453 for similar sequences.
%C A302439 For some odd o = 2*k + 1, is there some k such that for all e > k, a(o * 2^e) = a(o + 2^(e - 1)) + c for some c? - _David A. Corneth_, Apr 15 2018
%H A302439 Rémy Sigrist, <a href="/A302439/b302439.txt">Table of n, a(n) for n = 0..10000</a>
%H A302439 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A302439 a(2^n - 1) = 1 for any n >= 0.
%F A302439 a(2^n) = n + 1 for any n >= 0.
%F A302439 From _David A. Corneth_, Apr 15 2018: (Start)
%F A302439 Is a(2^n + i) >= a(2^n) for 0 <= i <= 2^n - 2?
%F A302439 What is the least k(n) such that
%F A302439 a(2^n + i) <= a(2^n + k(n)) for 1 <= i <= 2^n - 2? (End)
%e A302439 For n = 20: the binary expansion of 20, "10100", can be split in 10 ways into aperiodic substrings:
%e A302439 - (10100),
%e A302439 - (101)(0)(0),
%e A302439 - (10)(100),
%e A302439 - (10)(10)(0),
%e A302439 - (10)(1)(0)(0),
%e A302439 - (1)(0100),
%e A302439 - (1)(010)(0),
%e A302439 - (1)(0)(100),
%e A302439 - (1)(0)(10)(0),
%e A302439 - (1)(0)(1)(0)(0).
%e A302439 Hence a(20) = 10.
%o A302439 (PARI) a(n) = if (n==0, return (1), my (v=0); for (w=1, #binary(n), my (ok=1); fordiv (w, d, if (d<w && #Set(digits(n % (2^w), 2^d))<=1, ok = 0; break)); if (ok, v += a(n \ (2^w)))); return (v))
%Y A302439 Cf. A301453.
%K A302439 nonn,base
%O A302439 0,3
%A A302439 _Rémy Sigrist_, Apr 08 2018