A357993 -id:A357993 - cp's OEIS frontend

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

Rémy Sigrist, Oct 22 2022

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

			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, ...}

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

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

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

PARI
```
See Links section.
```

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

PARI

Formula