A357961 a(1) = 1, and for any n > 0, a(n+1) is the k-th positive number not yet in the sequence, where k is the Hamming weight of a(n).

1, 2, 3, 5, 6, 7, 9, 8, 4, 10, 12, 13, 15, 17, 14, 18, 16, 11, 21, 22, 23, 25, 24, 20, 26, 28, 29, 31, 33, 27, 34, 30, 36, 32, 19, 38, 39, 41, 40, 37, 43, 45, 46, 47, 49, 44, 48, 42, 51, 53, 54, 55, 57, 56, 52, 58, 60, 61, 63, 65, 50, 62, 67, 64, 35, 68, 66

Offset

1,2

Comments

This sequence is a permutation of the positive integers:

- Let e = A000523 and w = A000120.

- Lemma: a(n) <= n + e(n)

- This property is true for n = 1.

- Assume that a(n) <= n + e(n) for some n >= 1.

- Then a(n+1) <= n + w(a(n))

<= n + e(a(n))

<= n + e(n + e(n))

<= n + e(2*n)

<= n + 1 + e(n)

<= n + 1 + e(n + 1) - QED.

- If this sequence is not a permutation, then some number is missing.

- Let v be the least number that does not appear in the sequence.

- At some point, v is the least number not yet in the sequence.

- From now on, powers of 2 can no longer appear in the sequence.

- So there are infinitely many numbers that do not appear in the sequence.

- Let w be the least number > v that does not appear in the sequence.

- At some point, v and w are the two least numbers not yet in the sequence.

- Say this happens after m terms and max(a(1), ..., a(m)) < 2^k (with k > 0).

- From now on, powers of 2 and sums of two powers of 2 can no longer appear.

- So the numbers 2^k, 2^k + 2^i where i = 0..k-1 won't appear,

and the numbers 2^(k+1), 2^(k+1) + 2^i where i = 0..k won't appear.

- So among the first 2^(k+2) terms, by the pigeonhole principle,

we necessarily have a term a(n) >= 2^(k+2) + 2*k + 3.

- But we also know that a(n) <= 2^(k+2) + e(2^(k+2)) = 2^(k+2) + k + 2.

- This is a contradiction - QED.

Conjecture: this permutation has only finite cycles because it appears that for each interval a(1..2^m) the maximal observed displacement is smaller than 2^m and this maximal displacement is realized by only one element in this interval for m > 3. - Thomas Scheuerle, Oct 22 2022

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Thomas Scheuerle, Scatter plot of log_2(2^4 + n - a(n)) for n = 1..10000

Rémy Sigrist, PARI program

Index entries for sequences that are permutations of the natural numbers

Formula

a(n) <= n + A000523(n).

Empirically: a(n) = n + A000523(n) iff n = 1 or n belong to A132753 \ {3, 4}.

Example

The first terms, alongside their Hamming weight and the values not yet in the sequence so far, are:
  n   a(n)  A000120(a(n))  values not yet in the sequence
  --  ----  -------------  ---------------------------------------------
   1     1              1  { 2,  3,  4,  5,  6,  7,  8,  9, 10, 11, ...}
   2     2              1  { 3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...}
   3     3              2  { 4,  5,  6,  7,  8,  9, 10, 11, 12, 13, ...}
   4     5              2  { 4,  6,  7,  8,  9, 10, 11, 12, 13, 14, ...}
   5     6              2  { 4,  7,  8,  9, 10, 11, 12, 13, 14, 15, ...}
   6     7              3  { 4,  8,  9, 10, 11, 12, 13, 14, 15, 16, ...}
   7     9              2  { 4,  8, 10, 11, 12, 13, 14, 15, 16, 17, ...}
   8     8              1  { 4, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...}
   9     4              1  {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...}
  10    10              2  {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...}
  11    12              2  {11, 13, 14, 15, 16, 17, 18, 19, 20, 21, ...}
  12    13              3  {11, 14, 15, 16, 17, 18, 19, 20, 21, 22, ...}
  13    15              4  {11, 14, 16, 17, 18, 19, 20, 21, 22, 23, ...}
  14    17              2  {11, 14, 16, 18, 19, 20, 21, 22, 23, 24, ...}
  15    14              3  {11, 16, 18, 19, 20, 21, 22, 23, 24, 25, ...}
  16    18              2  {11, 16, 19, 20, 21, 22, 23, 24, 25, 26, ...}

Prog

(PARI) See Links section.
(MATLAB)
function a = A357961( max_n )
    a = 1;
    num = [2:max_n*floor(log2(max_n))];
    for n = 2:max_n
        k = num(length(find(bitget(a(n-1), 1:64)==1)));
        a(n) = k; num(num == k) = [];
    end
end % Thomas Scheuerle, Oct 22 2022

Crossrefs

Cf. A000120, A000523, A132753, A217122, A357993, A358057 (inverse).

Sequence in context: A255430 A074492 A059307 * A159635 A068938 A166937

Adjacent sequences: A357958 A357959 A357960 * A357962 A357963 A357964

Keyword

nonn,base

Author

Rémy Sigrist, Oct 22 2022

Status

approved