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

Author

Rémy Sigrist, Mar 07 2021

Keywords

• nonn
• base
• easy

Comments

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

Examples

			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.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A003000, A070939, A091065, A342242.

Programs

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

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