|
%I #25 Aug 06 2017 03:10:26
%S 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,
%T 23,48,22,30,44,31,33,32,18,36,29,47,45,52,21,55,49,84,61,43,51,53,80,
%U 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
%N 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.
%C 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.
%C 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.
%C Also, with above condition and the initial value a(1) = 3 the algorithm generates A269363 which contains only terms of A091067. See also A266191.
%H Antti Karttunen, <a href="/A266121/b266121.txt">Table of n, a(n) for n = 1..16384</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e 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.
%e 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.
%o (Scheme, with defineperm1-macro from _Antti Karttunen_'s IntSeq-library)
%o (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)))))))))
%o (define (isA003714? n) (= (* 3 n) (A003987bi n (* 2 n)))) ;; Where A003987bi implements bitwise-XOR (see A003987).
%o ;; We consider a > b (i.e. not less than b) also in case a is #f.
%o ;; (Because of the stateful caching system used by defineperm1-macro):
%o (define (not-lte? a b) (cond ((not (number? a)) #t) (else (> a b))))
%Y Left inverse: A266122 (also the right inverse if this sequence is a permutation of natural numbers).
%Y Cf. A003714, A003987, A091067, A091072, A269361, A269363, A269365, A269366, A269367.
%Y Cf. also A266191 and A266117 for similar permutations.
%K nonn,base
%O 1,2
%A _Antti Karttunen_, Dec 23 2015
%E Minor typo in the description corrected by _Antti Karttunen_, Feb 25 2016
|
