A245702 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).

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, 87, 24, 185, 42, 61, 21, 137, 34, 55, 18, 97, 27, 41, 16, 415, 76, 103, 28, 229, 49, 67, 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

Offset: 1

Author

Antti Karttunen, Aug 02 2014

Keywords

• nonn

Links

• Antti Karttunen, Table of n, a(n) for n = 1..383
• Index entries for sequences operating on GF(2)[X]-polynomials
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A245701.

Cf. A000035, A014580, A091242, A091225.

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

Programs

PARI

allocatemem(123456789);
a014580 = vector(2^18);
a091242 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; j=0; n=2; while((n < 2^22), if(isA014580(n), i++; a014580[i] = n, j++; a091242[j] = n); n++)
A245702(n) = if(1==n, 1, if(0==(n%2), a014580[A245702(n/2)], a091242[A245702((n-1)/2)]));
for(n=1, 383, write("b245702.txt", n, " ", A245702(n)));

Scheme

;; With memoizing definec-macro.
(definec (A245702 n) (cond ((< n 2) n) ((even? n) (A014580 (A245702 (/ n 2)))) (else (A091242 (A245702 (/ (- n 1) 2))))))

Formula

a(1) = 1, a(2n) = A014580(a(n)), a(2n+1) = A091242(a(n)).

As a composition of related permutations:

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

Other identities:

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].