A266121 Lexicographically first injection of natural numbers beginning with a(1)=1 such that 1+(a(n)*a(n+1)) is a fibbinary number (A003714), i.e., has no adjacent 1's in its base-2 representation.

1, 3, 5, 4, 2, 8, 9, 7, 12, 6, 14, 24, 11, 13, 20, 16, 10, 26, 40, 17, 15, 39, 28, 19, 27, 25, 23, 48, 22, 30, 44, 31, 33, 32, 18, 36, 29, 47, 45, 52, 21, 55, 49, 84, 61, 43, 51, 53, 80, 34, 64, 37, 35, 59, 75, 117, 93, 91, 57, 41, 100, 82, 50, 104, 42, 98, 106, 90, 114, 72, 58, 144, 65, 63, 151, 56, 38, 54, 76, 71, 60

Offset

1,2

Comments

It is conjectured that this sequence is not only injective, but also surjective on N, i.e., that it is a true permutation of natural numbers.

A similar sequence, but with condition that "(a(n)*a(n+1)) must be a member of A003714" yields a sequence: 1, 2, 4, 5, 8, 9, 16, 10, 13, 20, ... (A269361) which certainly is not a bijection, because it contains only terms of A091072.

Also, with above condition and the initial value a(1) = 3 the algorithm generates A269363 which contains only terms of A091067. See also A266191.

Links

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

Index entries for sequences that are permutations of the natural numbers

Example

After the initial a(1) = 1, for obtaining the value of a(2) we try the first unused number, which is 2, but (1*2)+1 = 3, which in binary is "11", thus 2 is not qualified at this point of time. So next we try 3, and (1*3)+1 = 4, which in binary is "100", and that satisfies our criterion (no adjacent 1-bits), thus we set a(2) = 3.
For a(3), we test with the least unused numbers 2, 4, 5, etc., yielding products (3*2)+1 = 7 = "111", (3*4)+1 = 13 = "1101" and (3*5)+1 = 16 = "10000" in binary, and only 5 satisfies the criterion, thus we set a(3) = 5.

Prog

(Scheme, with defineperm1-macro from Antti Karttunen's IntSeq-library)
(defineperm1 (A266121 n) (cond ((= 1 n) n) (else (let ((prev (A266121 (- n 1)))) (let loop ((k 1)) (cond ((and (not-lte? (A266122 k) (- n 1)) (isa003714? (+ 1 (* k prev)))) k) (else (loop (+ 1 k)))))))))
(define (isA003714? n) (= (* 3 n) (A003987bi n (* 2 n)))) ;; Where A003987bi implements bitwise-XOR (see A003987).
;; We consider a > b (i.e. not less than b) also in case a is #f.
;; (Because of the stateful caching system used by defineperm1-macro):
(define (not-lte? a b) (cond ((not (number? a)) #t) (else (> a b))))

Crossrefs

Left inverse: A266122 (also the right inverse if this sequence is a permutation of natural numbers).

Cf. A003714, A003987, A091067, A091072, A269361, A269363, A269365, A269366, A269367.

Cf. also A266191 and A266117 for similar permutations.

Sequence in context: A338843 A075077 A196771 * A340255 A340256 A354247

Adjacent sequences: A266118 A266119 A266120 * A266122 A266123 A266124

Keyword

nonn,base

Author

Antti Karttunen, Dec 23 2015

Extensions

Minor typo in the description corrected by Antti Karttunen, Feb 25 2016

Status

approved