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

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, 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, 3, 3, 3, 4, 4, 4, 3, 3, 3, 2, 3, 5, 5, 3, 3, 3, 4, 4, 3

Offset: 0

Author

Rémy Sigrist, Mar 08 2020

Keywords

• nonn
• base

Comments

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

This sequence is a binary variant of A088950.

Square-subwords are counted with multiplicity.

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).

Examples

			For n = 43:
- the binary representation of 43 is "101011",
- we have the following square-subwords: "1010", "0101", "11",
- hence a(43) = 3.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..16384
• Eric Weisstein's World of Mathematics, Squarefree Word
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A002620, A088950.

Programs

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) }

Formula

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