A356354 a(n) is the least k such that the sets of positions of 1's in the binary expansions of n and k are similar.

0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 11, 3, 11, 7, 15, 1, 3, 3, 19, 3, 7, 11, 23, 3, 19, 11, 27, 7, 23, 15, 31, 1, 3, 3, 35, 3, 37, 19, 39, 3, 37, 7, 43, 11, 45, 23, 47, 3, 35, 19, 51, 11, 43, 27, 55, 7, 39, 23, 55, 15, 47, 31, 63, 1, 3, 3, 67, 3, 11, 35, 71, 3, 7

Offset: 0

Author

Rémy Sigrist, Oct 15 2022

Keywords

• nonn
• base

Comments

Let s(n) be the set of terms in the n-th row of A133457 (with s(0) = {}).

a(n) is the least k such that s(n) is the image of s(k) under some nonconstant linear function.

Examples

			The first terms, alongside their binary expansions, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     1       1          1
   2     1      10          1
   3     3      11         11
   4     1     100          1
   5     3     101         11
   6     3     110         11
   7     7     111        111
   8     1    1000          1
   9     3    1001         11
  10     3    1010         11
  11    11    1011       1011
  12     3    1100         11
  13    11    1101       1011
  14     7    1110        111
  15    15    1111       1111
  16     1   10000          1
		

Links

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

Crossrefs

Cf. A000120, A000265, A018900, A030101, A064895, A133457.

Programs

PARI

See Links section.

Formula

A000120(a(n)) = A000120(n).

a(a(n)) = a(n).

a(2*n) = a(n).

a(A030101(n)) = a(n).

a(n) = 1 iff n is a power of 2.

a(n) = 3 iff n belongs to A018900.

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