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,8

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

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

Formula

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

Example

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

Prog

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

Crossrefs

Cf. A002620, A088950.

Sequence in context: A366134 A064892 A236344 * A274109 A083019 A137865

Adjacent sequences: A333121 A333122 A333123 * A333125 A333126 A333127

Keyword

nonn,base

Author

Rémy Sigrist, Mar 08 2020

Status

approved