|
%I #19 Apr 15 2018 15:03:34
%S 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 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 14,10,9,9,6,1,7,7,18,7,24,21,21,7,23,22,32,22
%N 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 Leading zeros in the binary expansion of n are ignored.
%C The value a(0) = 1 corresponds to the empty concatenation.
%C See A301453 for similar sequences.
%C 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 Rémy Sigrist, <a href="/A302439/b302439.txt">Table of n, a(n) for n = 0..10000</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F a(2^n - 1) = 1 for any n >= 0.
%F a(2^n) = n + 1 for any n >= 0.
%F From _David A. Corneth_, Apr 15 2018: (Start)
%F Is a(2^n + i) >= a(2^n) for 0 <= i <= 2^n - 2?
%F What is the least k(n) such that
%F a(2^n + i) <= a(2^n + k(n)) for 1 <= i <= 2^n - 2? (End)
%e For n = 20: the binary expansion of 20, "10100", can be split in 10 ways into aperiodic substrings:
%e - (10100),
%e - (101)(0)(0),
%e - (10)(100),
%e - (10)(10)(0),
%e - (10)(1)(0)(0),
%e - (1)(0100),
%e - (1)(010)(0),
%e - (1)(0)(100),
%e - (1)(0)(10)(0),
%e - (1)(0)(1)(0)(0).
%e Hence a(20) = 10.
%o (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 Cf. A301453.
%K nonn,base
%O 0,3
%A _Rémy Sigrist_, Apr 08 2018
|
