A361942 For any number n >= 0 with binary expansion (b_1, ..., b_w), a(n) is the least p > 0 such that b_i = b_{p+i} for i = 1..w-p.

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

Offset: 0

Author

Rémy Sigrist, Mar 31 2023

Keywords

• nonn
• base

Comments

Leading zeros in binary expansions of positive integers are ignored.

This sequence is a variant of A302291 related to fractional powers of words.

For any k > 0, the value k appears A045690(k) times in a(2^(k-1)), ..., a(2^k-1).

Examples

			The first terms, alongside the binary expansion of n split into chunks of length a(n), are:
  n   a(n)  bin(n)
  --  ----  ------
   0     1  0
   1     1  1
   2     2  10
   3     1  1|1
   4     3  100
   5     2  10|1
   6     3  110
   7     1  1|1|1
   8     4  1000
   9     3  100|1
  10     2  10|10
  11     3  101|1
  12     4  1100
  13     3  110|1
  14     4  1110
  15     1  1|1|1|1
		

References

• Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 23.

Links

• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A045690, A070939, A091065, A302291.

Programs

PARI

a(n) = { my (b = if (n, binary(n), [0])); for (p = 1, oo, if (b[1..#b-p] == b[1+p..#b], return (p););); }

Formula

a(n) <= A302291(n).

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

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

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