login
Permutation of natural numbers: a(1) = 1, a(2n) = A014580(a(n)), a(2n+1) = A091242(a(n)), where A014580(n) = binary code for n-th irreducible polynomial over GF(2) and A091242(n) = binary code for n-th reducible polynomial over GF(2).
9

%I #15 Aug 10 2014 06:20:26

%S 1,2,4,3,5,11,8,7,6,13,9,47,17,31,14,25,12,19,10,59,20,37,15,319,62,

%T 87,24,185,42,61,21,137,34,55,18,97,27,41,16,415,76,103,28,229,49,67,

%U 22,3053,373,433,79,647,108,131,33,1627,222,283,54,425,78,109,29,1123,166,203,45,379,71,91,26,731,121,145,36,253,53,73,23

%N Permutation of natural numbers: a(1) = 1, a(2n) = A014580(a(n)), a(2n+1) = A091242(a(n)), where A014580(n) = binary code for n-th irreducible polynomial over GF(2) and A091242(n) = binary code for n-th reducible polynomial over GF(2).

%H Antti Karttunen, <a href="/A245702/b245702.txt">Table of n, a(n) for n = 1..383</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) = A014580(a(n)), a(2n+1) = A091242(a(n)).

%F As a composition of related permutations:

%F a(n) = A245703(A227413(n)).

%F Other identities:

%F For all n >= 1, 1 - A091225(a(n)) = A000035(n). [Maps even numbers to binary representations of irreducible GF(2) polynomials (= A014580) and odd numbers to the corresponding representations of reducible polynomials].

%o (PARI)

%o allocatemem(123456789);

%o a014580 = vector(2^18);

%o a091242 = vector(2^22);

%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 < 2^22), if(isA014580(n), i++; a014580[i] = n, j++; a091242[j] = n); n++)

%o A245702(n) = if(1==n, 1, if(0==(n%2), a014580[A245702(n/2)], a091242[A245702((n-1)/2)]));

%o for(n=1, 383, write("b245702.txt", n, " ", A245702(n)));

%o (Scheme, with memoizing definec-macro)

%o (definec (A245702 n) (cond ((< n 2) n) ((even? n) (A014580 (A245702 (/ n 2)))) (else (A091242 (A245702 (/ (- n 1) 2))))))

%Y Inverse: A245701.

%Y Cf. A000035, A014580, A091242, A091225.

%Y Similar entanglement permutations: A193231, A227413, A237126, A243288, A245703, A245704.

%K nonn

%O 1,2

%A _Antti Karttunen_, Aug 02 2014