login
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).
3
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
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
Sequence in context: A255430 A074492 A059307 * A159635 A068938 A166937
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Oct 22 2022
STATUS
approved