cp's OEIS Frontend

A246161 Permutation of positive integers: a(1) = 1, a(A014580(n)) = A000069(1+a(n)), a(A091242(n)) = A001969(1+a(n)), where A000069 and A001969 are the odious and evil numbers, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

%I A246161 #29 Sep 09 2017 23:24:52
%S A246161 1,2,4,3,5,9,8,6,10,18,7,17,11,12,20,36,15,34,19,23,24,40,72,30,16,68,
%T A246161 39,46,48,80,13,144,60,33,136,78,21,92,96,160,37,27,288,120,66,272,14,
%U A246161 156,43,184,192,320,75,54,35,576,240,132,22,544,25,29,312,86,368,384,41
%N A246161 Permutation of positive integers: a(1) = 1, a(A014580(n)) = A000069(1+a(n)), a(A091242(n)) = A001969(1+a(n)), where A000069 and A001969 are the odious and evil numbers, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).
%C A246161 This is an instance of entanglement permutation, where the two complementary pairs to be entangled with each other are A014580/A091242 (binary codes for irreducible and reducible polynomials over GF(2)) and A000069/A001969 (odious and evil numbers).
%C A246161 Because 3 is the only evil number in A014580, it implies that, apart from a(3)=4, odious numbers occur in odious positions only (along with many evil numbers that also occur in odious positions).
%C A246161 Note that the two values n=21 and n=35 given in the Example section both encode polynomials reducible over GF(2) and have an odd number of 1-bits in their binary representation (that is, they are both terms of A246158). As this permutation maps all terms of A091242 to the terms of A001969, and apart from a single exception 3 (which here is in a closed cycle: a(3) = 4, a(4) = 3), no term of A001969 is a member of A014580, so they must be members of A091242, thus successive iterations a(21), a(a(21)), a(a(a(21))), etc. always yield some evil number (A001969), so the cycle can never come back to 21 as it is an odious number, so that cycle must be infinite.
%C A246161 On the other hand, when we iterate with the inverse of this permutation, A246162, starting from 21, we see that its successive pre-images 37, 41, 67, 203, 5079 [e.g., 21 = a(a(a(a(a(5079)))))] are all irreducible and thus also odious.
%C A246161 In each such infinite cycle, there can be at most one term which is both reducible (in A091242) and odious (in A000069), i.e. in A246158, thus 21 and 35 must reside in different infinite cycles.
%C A246161 The sequence of fixed points begin as: 1, 2, 5, 19, 54, 71, 73, 865.
%C A246161 Question: apart from them and transposition (3 4) are there any more instances of finite cycles?
%H A246161 Antti Karttunen, <a href="/A246161/b246161.txt">Table of n, a(n) for n = 1..10001</a>
%H A246161 <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%H A246161 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A246161 a(1) = 1, and for n > 1, if n is in A014580, a(n) = A000069(1+a(A091226(n))), otherwise a(n) = A001969(1+a(A091245(n))).
%F A246161 As a composition of related permutations:
%F A246161 a(n) = A233280(A245701(n)).
%F A246161 a(n) = A003188(A246201(n)).
%F A246161 a(n) = A234612(A246163(n)).
%F A246161 Other identities:
%F A246161 For all n > 1, A010060(a(n)) = A091225(n). [Maps binary representations of irreducible GF(2) polynomials (A014580) to odious numbers and the corresponding representations of reducible polynomials (A091242) to evil numbers, in some order].
%e A246161 Consider n=21. In binary it is 10101, encoding for polynomial x^4 + x^2 + 1, which factorizes as (x^2 + x + 1)(x^2 + x + 1) over GF(2), in other words, 21 = A048720(7,7). As such, it occurs as the 14th term in A091242, reducible polynomials over GF(2), coded in binary.
%e A246161 By definition of this permutation, a(21) is thus obtained as A001969(1+a(14)). 14 in turn is 8th term in A091242, thus a(14) = A001969(1+a(8)). In turn, 8 = A091242(4), thus a(8) = A001969(1+a(4)), and 4 = A091242(1).
%e A246161 By working the recursion back towards the toplevel, the result is a(21) = A001969(1+A001969(1+A001969(1+A001969(1+1)))) = 24.
%e A246161 Consider n=35. In binary it is 100011, encoding for polynomial x^5 + x + 1, which factorizes as (x^2 + x + 1)(x^3 + x^2 + 1) over GF(2), in other words, 35 = A048720(7,13). As such, it occurs as the 26th term in A091242, thus a(35) = A001969(1+a(26)), and as 26 = A091242(18) and 18 = A091242(12) and 12 = A091242(7) and 7 = A014580(3) [the polynomial x^2 + x + 1 is irreducible over GF(2)], and 3 = A014580(2) and 2 = A014580(1), we obtain the result as a(35) = A001969(1+A001969(1+A001969(1+A001969(1+A000069(1+A000069(1+A000069(2))))))) = 136.
%o A246161 (Scheme, with memoizing definec-macro from _Antti Karttunen_'s IntSeq-library)
%o A246161 (definec (A246161 n) (cond ((= 1 n) n) ((= 1 (A091225 n)) (A000069 (+ 1 (A246161 (A091226 n))))) (else (A001969 (+ 1 (A246161 (A091245 n)))))))
%o A246161 (define (A246161 n) (A233280 (A245701 n))) ;; Alternative implementation.
%Y A246161 Inverse: A246162.
%Y A246161 Related permutations: A003188, A234612, A245701, A233280, A246163, A246201.
%Y A246161 Cf. A000069, A001969, A010060, A014580, A091225, A091226, A091242, A091245, A246158.
%K A246161 nonn
%O A246161 1,2
%A A246161 _Antti Karttunen_, Aug 17 2014