A366027 Lexicographically earliest sequence of distinct positive integers such that for any n > 0, if 2^(d-1) appears in the binary expansion of a(n) then d divides n.

1, 2, 4, 3, 16, 5, 64, 8, 256, 17, 1024, 6, 4096, 65, 20, 9, 65536, 7, 262144, 10, 68, 1025, 4194304, 11, 16777216, 4097, 257, 66, 268435456, 18, 1073741824, 128, 1028, 65537, 80, 12, 68719476736, 262145, 4100, 19, 1099511627776, 32, 4398046511104, 1026, 21

Offset: 1

Author

Rémy Sigrist, Sep 26 2023

Keywords

• nonn
• base

Comments

In other words, the binary expansion of a(n) encodes a subset of the divisors of n.

This sequence is a permutation of the positive integers with inverse A366028.

Examples

			The first terms, alongside their binary expansion and the corresponding divisors d, are:
  n   a(n)    bin(a(n))            Corresponding divisors
  --  ------  -------------------  ----------------------
   1       1                    1  {1}
   2       2                   10  {2}
   3       4                  100  {3}
   4       3                   11  {2, 1}
   5      16                10000  {5}
   6       5                  101  {3, 1}
   7      64              1000000  {7}
   8       8                 1000  {4}
   9     256            100000000  {9}
  10      17                10001  {5, 1}
  11    1024          10000000000  {11}
  12       6                  110  {3, 2}
  13    4096        1000000000000  {13}
  14      65              1000001  {7, 1}
  15      20                10100  {5, 3}
  16       9                 1001  {4, 1}
  17   65536    10000000000000000  {17}
  18       7                  111  {3, 2, 1}
		

Links

• Rémy Sigrist, PARI program
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A048793, A271410, A366028 (inverse).

Programs

PARI

See Links section.

Formula

a(p) = 2^(p-1) for any prime number p.

a(2*p) = 2^(p-1) + 1 for any prime number p.