A091202 - OEIS

A091202

Factorization-preserving isomorphism from nonnegative integers to binary codes for polynomials over GF(2).

0, 1, 2, 3, 4, 7, 6, 11, 8, 5, 14, 13, 12, 19, 22, 9, 16, 25, 10, 31, 28, 29, 26, 37, 24, 21, 38, 15, 44, 41, 18, 47, 32, 23, 50, 49, 20, 55, 62, 53, 56, 59, 58, 61, 52, 27, 74, 67, 48, 69, 42, 43, 76, 73, 30, 35, 88, 33, 82, 87, 36, 91, 94, 39, 64, 121, 46, 97, 100, 111, 98

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

E.g. we have the following identities: A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)), A008683(n) = A091219(a(n)), A014580(n) = a(A000040(n)), A049084(n) = A091227(a(n)).

LINKS

Antti Karttunen, Table of n, a(n) for n = 0..8192

A. Karttunen, Scheme-program for computing this sequence.

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

Index entries for sequences that are permutations of the natural numbers

FORMULA

a(0)=0, a(1)=1, a(p_i) = A014580(i) for primes p_i with index i and for composites a(p_i * p_j * ...) = a(p_i) X a(p_j) X ..., where X stands for carryless multiplication of GF(2)[X] polynomials (A048720).

Other identities. For all n >= 1, the following holds:

A091225(a(n)) = A010051(n). [Maps primes to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242. The permutations A091204, A106442, A106444, A106446, A235041 and A245703 have the same property.]

From Antti Karttunen, Jun 10 2018: (Start)

For n <= 1, a(n) = n, for n > 1, a(n) = 2*a(n/2) if n is even, and if n is odd, then a(n) = A305421(a(A064989(n))).

a(n) = A305417(A156552(n)) = A305427(A243071(n)).

(End)

PROG

(PARI)

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1, 1]==2), f[1, 2] = 0); for (i=1, #f~, f[i, 1] = precprime(f[i, 1]-1)); factorback(f)};

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));

A305420(n) = { my(k=1+n); while(!A091225(k), k++); (k); };

A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))), x, 2)); for(i=1, #f~, f[i, 1] = Pol(binary(A305420(f[i, 1])))); fromdigits(Vec(factorback(f))%2, 2); };

A091202(n) = if(n<=1, n, if(!(n%2), 2*A091202(n/2), A305421(A091202(A064989(n))))); \\ Antti Karttunen, Jun 10 2018

CROSSREFS

Inverse: A091203.

Several variants exist: A235041, A091204, A106442, A106444, A106446.

Cf. also A000005, A091220, A001221, A091221, A001222, A091222, A008683, A091219, A000040, A014580, A048720, A049084, A091227, A245703, A234741.

Cf. also A302023, A302025, A305417, A305427 for other similar permutations.

Sequence in context: A328877 A125595 A374991 * A106444 A106442 A091204

Adjacent sequences: A091199 A091200 A091201 * A091203 A091204 A091205

KEYWORD

nonn,look

AUTHOR

Antti Karttunen, Jan 03 2004

STATUS

approved