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

1, 2, 4, 3, 5, 9, 8, 7, 11, 19, 6, 17, 10, 15, 23, 39, 13, 35, 18, 21, 31, 47, 79, 27, 16, 71, 37, 43, 63, 95, 14, 159, 55, 33, 143, 75, 22, 87, 127, 191, 38, 29, 319, 111, 67, 287, 12, 151, 45, 175, 255, 383, 77, 59, 34, 639, 223, 135, 20, 575, 30, 25, 303, 91, 351, 511, 46, 767, 155, 119, 69, 1279, 78, 447, 271, 41, 1151, 61, 51

Offset: 1

Author

Antti Karttunen, Aug 02 2014

Keywords

• nonn
• look
• hear

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10001
• Antti Karttunen, Entanglement Permutations, 2016-2017
• Index entries for sequences related to polynomials in ring GF(2)[X]
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse: A245702.

Cf. A000035, A014580, A091242, A091225, A091226, A091245.

Similar entanglement permutations: A135141, A193231, A237427, A243287, A245703, A245704.

Programs

PARI

allocatemem(123456789);
A091226 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
n=2; while((n < 2^22), if(isA014580(n), A091226[n] = A091226[n-1]+1, A091226[n] = A091226[n-1]); n++)
A091245(n) = ((n-A091226[n])-1);
A245701(n) = if(1==n, 1, if(isA014580(n), 2*(A245701(A091226[n])), 1 + 2*(A245701(A091245(n)))));
for(n=1, 10001, write("b245701.txt", n, " ", A245701(n)));

Scheme

;; With memoizing definec-macro.
(definec (A245701 n) (cond ((= 1 n) n) ((= 1 (A091225 n)) (* 2 (A245701 (A091226 n)))) (else (+ 1 (* 2 (A245701 (A091245 n)))))))

Formula

a(1) = 1, and for n > 1, if n is in A014580, a(n) = 2*a(A091226(n)), otherwise a(n) = 1 + 2*a(A091245(n)).

As a composition of related permutations:

a(n) = A135141(A245704(n)).

Other identities:

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