|
%I #24 Jul 27 2015 22:11:32
%S 1,4,2,8,11,5,3,14,31,17,47,9,13,6,7,21,61,42,185,24,87,62,319,15,37,
%T 20,59,10,19,12,25,29,109,78,425,54,283,222,1627,33,131,108,647,79,
%U 433,373,3053,22,67,49,229,28,103,76,415,16,41,27,97,18,55,34,137,39,167,134,859,98,563,494,4225,70,375,331,2705,264,2011,1832,19891,44
%N Permutation of natural numbers: a(1) = 1, a(2n) = A091242(a(n)), a(2n+1) = A014580(a(n)), where A091242(n) = binary code for n-th reducible polynomial over GF(2) and A014580(n) = binary code for n-th irreducible polynomial over GF(2).
%C This sequence can be represented as a binary tree. Each left hand child is produced as A091242(n), and each right hand child as A014580(n), when the parent contains n:
%C |
%C ...................1...................
%C 4 2
%C 8......../ \.......11 5......../ \........3
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C 14 31 17 47 9 13 6 7
%C 21 61 42 185 24 87 62 319 15 37 20 59 10 19 12 25
%C etc.
%C Because 2 is the only even term in A014580, it implies that, apart from a(3)=2, all other odd positions contain an odd number. There are also odd numbers in the even bisection, precisely all the terms of A246156 in some order, together with all even numbers larger than 2 that are also there. See also comments in A246201.
%H Antti Karttunen, <a href="/A246202/b246202.txt">Table of n, a(n) for n = 1..638</a>
%H <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F a(1) = 1, a(2n) = A091242(a(n)), a(2n+1) = A014580(a(n)).
%F As a composition of related permutations:
%F a(n) = A245702(A054429(n)).
%F a(n) = A246162(A003188(n)).
%F a(n) = A193231(A246204(n)).
%F a(n) = A246164(A193231(n)).
%F a(n) = A260426(A260422(n)).
%F Other identities:
%F For all n > 1, A091225(a(n)) = A000035(n). [After 1, maps even numbers to binary representations of reducible GF(2) polynomials and odd numbers to the corresponding representations of irreducible polynomials, in some order. A246204 has the same property].
%o (PARI)
%o allocatemem((2^31)+(2^30));
%o uplim = (2^25) + (2^24);
%o v014580 = vector(2^24);
%o v091242 = vector(uplim);
%o isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from _Charles R Greathouse IV_
%o i=0; j=0; n=2; while((n < uplim), if(isA014580(n), i++; v014580[i] = n, j++; v091242[j] = n); n++)
%o A246202(n) = if(1==n, 1, if(0==(n%2), v091242[A246202(n/2)], v014580[A246202((n-1)/2)]));
%o for(n=1, 638, write("b246202.txt", n, " ", A246202(n)));
%o \\ Works with PARI Version 2.7.4. - _Antti Karttunen_, Jul 25 2015
%o (Scheme, with memoization-macro definec)
%o (definec (A246202 n) (cond ((< n 2) n) ((odd? n) (A014580 (A246202 (/ (- n 1) 2)))) (else (A091242 (A246202 (/ n 2))))))
%Y Inverse: A246201.
%Y Similar or related permutations: A245702, A246162, A246164, A246204, A237126, A003188, A054429, A193231, A260422, A260426.
%Y Cf. A014580, A091242, A091225, A246156.
%K nonn,tabf
%O 1,2
%A _Antti Karttunen_, Aug 19 2014
|
