A333124 - OEIS

%I #10 Mar 10 2020 15:02:22

%S 0,0,0,1,1,0,1,2,2,1,1,1,2,1,2,4,4,2,1,2,2,2,1,2,3,2,2,2,3,2,4,6,6,4,

%T 2,3,3,2,2,3,3,2,3,3,2,2,2,4,5,3,2,3,3,3,3,3,4,3,3,3,5,4,6,9,9,6,4,5,

%U 3,3,3,4,4,4,3,3,3,2,3,5,5,3,3,3,4,4,3

%N a(n) is the number of square-subwords in the binary representation of n.

%C A square-(sub)word consists of two nonempty identical adjacent subwords.

%C This sequence is a binary variant of A088950.

%C Square-subwords are counted with multiplicity.

%C A binary word of length 4 contains necessarily a square-subword, hence a(n) tends to infinity as n tends to infinity (a number whose binary representation has >= 4*k digits has >= k square-subwords).

%H Rémy Sigrist, <a href="/A333124/b333124.txt">Table of n, a(n) for n = 0..16384</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SquarefreeWord.html">Squarefree Word</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(2^k) = a(2^k-1) = A002620(k) for any k >= 0.

%e For n = 43:

%e - the binary representation of 43 is "101011",

%e - we have the following square-subwords: "1010", "0101", "11",

%e - hence a(43) = 3.

%o (PARI) a(n, base=2) = { my (b=digits(n, base), v); for (w=1, #b\2, for (i=1, #b-2*w+1, if (b[i..i+w-1]==b[i+w..i+2*w-1], v++))); return (v) }

%Y Cf. A002620, A088950.

%K nonn,base

%O 0,8

%A _Rémy Sigrist_, Mar 08 2020