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

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, 20, 59, 10, 19, 12, 25, 29, 109, 78, 425, 54, 283, 222, 1627, 33, 131, 108, 647, 79, 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

Offset

1,2

Comments

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:

|

...................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 20 59 10 19 12 25

etc.

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.

Links

Antti Karttunen, Table of n, a(n) for n = 1..638

Index entries for sequences operating on GF(2)[X]-polynomials

Index entries for sequences that are permutations of the natural numbers

Formula

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

As a composition of related permutations:

a(n) = A245702(A054429(n)).

a(n) = A246162(A003188(n)).

a(n) = A193231(A246204(n)).

a(n) = A246164(A193231(n)).

a(n) = A260426(A260422(n)).

Other identities:

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

Prog

(PARI)
allocatemem((2^31)+(2^30));
uplim = (2^25) + (2^24);
v014580 = vector(2^24);
v091242 = vector(uplim);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; j=0; n=2; while((n < uplim), if(isA014580(n), i++; v014580[i] = n, j++; v091242[j] = n); n++)
A246202(n) = if(1==n, 1, if(0==(n%2), v091242[A246202(n/2)], v014580[A246202((n-1)/2)]));
for(n=1, 638, write("b246202.txt", n, " ", A246202(n)));
\\ Works with PARI Version 2.7.4. - Antti Karttunen, Jul 25 2015
(Scheme, with memoization-macro definec)
(definec (A246202 n) (cond ((< n 2) n) ((odd? n) (A014580 (A246202 (/ (- n 1) 2)))) (else (A091242 (A246202 (/ n 2))))))

Crossrefs

Inverse: A246201.

Similar or related permutations: A245702, A246162, A246164, A246204, A237126, A003188, A054429, A193231, A260422, A260426.

Cf. A014580, A091242, A091225, A246156.

Sequence in context: A292964 A050128 A321119 * A134042 A051239 A064821

Adjacent sequences: A246199 A246200 A246201 * A246203 A246204 A246205

Keyword

nonn,tabf

Author

Antti Karttunen, Aug 19 2014

Status

approved