A342241 a(n) is the least k > 0 such that the first k bits and the last k bits in the binary expansion of n are the same.

1, 1, 2, 1, 3, 1, 3, 1, 4, 1, 2, 1, 4, 1, 4, 1, 5, 1, 2, 1, 5, 1, 2, 1, 5, 1, 5, 1, 5, 1, 5, 1, 6, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 6, 1, 2, 1, 6, 1, 6, 1, 6, 1, 3, 1, 6, 1, 6, 1, 6, 1, 6, 1, 7, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 7, 1, 2

Offset

0,3

Comments

This sequence gives the length of the least nonempty prefix that is also a suffix of the binary expansion of a number.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..8192

Index entries for sequences related to binary expansion of n

Formula

a(n) = 1 iff n = 0 or n is odd.

a(n) <= A070939(n) with equality iff n belongs to A091065.

a(n) = A070939(A342242(n)).

Example

For n = 42:
- the binary representation of 42 is "101010",
- the first bit ("1") and the last bit ("0") do not match,
- the first 2 bits ("10") and the last 2 bits ("10") match,
- so a(42) = 2.

Prog

(PARI) a(n) = { my (b=if (n, binary(n), [0])); for (w=1, oo, if (b[1..w]==b[#b+1-w..#b], return (w))) }
(Python)
def a(n):
  b = bin(n)[2:]
  for i in range(1, len(b)+1):
    if b[:i] == b[-i:]: return i
print([a(n) for n in range(87)]) # Michael S. Branicky, Mar 07 2021

Crossrefs

Cf. A003000, A070939, A091065, A342242.

Sequence in context: A073407 A049994 A135732 * A322584 A356224 A364767

Adjacent sequences: A342238 A342239 A342240 * A342242 A342243 A342244

Keyword

nonn,base,easy

Author

Rémy Sigrist, Mar 07 2021

Status

approved