A218252 Start with 1. For each term m, the next term is the smallest positive integer k such that k - (sum of base 2 digits of k) = m. If no such k exists, use the smallest natural number not already in the sequence.

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

Offset

1,2

Comments

The sequence is a permutation of the positive integers.

Links

Antti Karttunen, Table of n, a(n) for n = 1..8192

Index entries for sequences that are permutations of the natural numbers

Example

To obtain the 2nd term, take the first, 1.  What is the smallest integer k so that k - the number of 1's in k's binary representation is 1? The answer, obviously, is 2. [A213723(1) = 2.]
There is no number that is 2 more than its binary weight [as A213723(2) = 0], therefore we just take 3 as the next term.
Following 3 we can choose either 4 or 5, but 4 is smaller, and is thus the next term of the sequence. [A213723(3) = 4.]

Prog

(Scheme) ;; With defineperm1-macro from Antti Karttunen's IntSeq-library.
(defineperm1 (A218252 n) (cond ((<= n 1) n) ((A213723 (A218252 (- n 1))) => (lambda (next_maybe) (if (not (zero? next_maybe)) next_maybe (let loop ((i (A000012 (- n 1)))) (if (not-lte? (A257683 i) n) i (loop (+ i 1)))))))))
;; We consider a > b (i.e. not less than b) also in case a is nil.
;; (Because of the stateful caching system used by defineperm1-macro):
(define (not-lte? a b) (cond ((not (number? a)) #t) (else (> a b))))
;; Antti Karttunen, May 04 2015

Crossrefs

Inverse permutation: A257683.

Cf. A000120, A005187, A011371, A213723, A218253, A218254.

Cf. also A257676.

Sequence in context: A373038 A267106 A275119 * A080541 A330081 A072759

Adjacent sequences: A218249 A218250 A218251 * A218253 A218254 A218255

Keyword

nonn

Author

Nico Brown, Oct 24 2012

Extensions

Name slightly edited and links to A213723 in examples added by Antti Karttunen, May 04 2015

Status

approved