A305419 -id:A305419 - cp's OEIS frontend

A091203 Factorization-preserving isomorphism from binary codes of GF(2) polynomials to integers.

0, 1, 2, 3, 4, 9, 6, 5, 8, 15, 18, 7, 12, 11, 10, 27, 16, 81, 30, 13, 36, 25, 14, 33, 24, 17, 22, 45, 20, 21, 54, 19, 32, 57, 162, 55, 60, 23, 26, 63, 72, 29, 50, 51, 28, 135, 66, 31, 48, 35, 34, 243, 44, 39, 90, 37, 40, 99, 42, 41, 108, 43, 38, 75, 64, 225, 114, 47, 324

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

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

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

Inverse: A091202.
Several variants exist: A235042, A091205, A106443, A106445, A106447.
Cf. also A000005, A000040, A001221, A001222, A004247, A008683, A010051, A014580, A048720, A049084, A066247, A091219, A091220, A091221, A091222, A091225, A091227, A091247, A234741, A234742, A245703, A245704, A278233.
Cf. also A302024, A302026, A305418, A305428 for other similar permutations.

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A091203(n) = if(n<=1,n,if(!(n%2),2*A091203(n/2),A003961(A091203(A305422(n))))); \\ Antti Karttunen, Jun 10 2018

a(0)=0, a(1)=1. For n's coding an irreducible polynomial ir_i, that is if n=A014580(i), we have a(n) = A000040(i) and for composite polynomials a(ir_i X ir_j X ...) = p_i * p_j * ..., where p_i = A000040(i) and X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).
Other identities. For all n >= 1, the following holds:
A010051(a(n)) = A091225(n). [After a(1)=1, maps binary representations of irreducible GF(2) polynomials, A014580, to primes and the binary representations of corresponding reducible polynomials, A091242, to composite numbers. The permutations A091205, A106443, A106445, A106447, A235042 and A245704 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) = A003961(a(A305422(n))).
a(n) = A005940(1+A305418(n)) = A163511(A305428(n)).
A046523(a(n)) = A278233(n).
(End)

A305422 GF(2)[X] factorization prime shift towards smaller terms.

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 7, 2, 11, 3, 8, 1, 16, 6, 13, 4, 5, 7, 22, 2, 19, 11, 12, 3, 14, 8, 25, 1, 50, 16, 29, 6, 31, 13, 28, 4, 37, 5, 38, 7, 24, 22, 41, 2, 9, 19, 32, 11, 26, 12, 47, 3, 44, 14, 55, 8, 59, 25, 10, 1, 20, 50, 61, 16, 21, 29, 118, 6, 67, 31, 88, 13, 110, 28, 53, 4, 69, 37, 18, 5, 64, 38, 73, 7, 94, 24, 87, 22, 43, 41, 52, 2, 91

Offset: 1

Antti Karttunen, Jun 07 2018

nonn

Let a x b stand for the carryless binary multiplication of positive integers a and b, that is, the result of operation A048720(a,b). With n having a unique factorization as f(i) x f(j) x ... x f(k), with 1 <= i <= j <= ... <= k, a(n) = f(i-1) x f(j-1) x ... x f(k-1), where f(0) = 1, and f(n) = A014580(n) for n >= 1.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to polynomials in ring GF(2)[X]

Cf. A000079 (positions of ones), A014580, A091225, A268389, A305419, A305421, A305424 (odd bisection), A305425.

Cf. also A064989, A300840.

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };

For all n >= 1:
a(A305421(n)) = n.
a(A001317(n)) = A000079(n).
A007814(a(n)) = A268389(n).

A305420 Smallest k > n whose binary expansion encodes an irreducible (0,1)-polynomial over GF(2)[X].

Original entry on oeis.org

2, 3, 7, 7, 7, 7, 11, 11, 11, 11, 13, 13, 19, 19, 19, 19, 19, 19, 25, 25, 25, 25, 25, 25, 31, 31, 31, 31, 31, 31, 37, 37, 37, 37, 37, 37, 41, 41, 41, 41, 47, 47, 47, 47, 47, 47, 55, 55, 55, 55, 55, 55, 55, 55, 59, 59, 59, 59, 61, 61, 67, 67, 67, 67, 67, 67, 73, 73, 73, 73, 73, 73, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 91

Offset: 1

Antti Karttunen, Jun 07 2018

nonn

a(n) is the smallest term of A014580 greater than n.

Antti Karttunen, Table of n, a(n) for n = 1..21845
Index entries for sequences related to polynomials in ring GF(2)[X]

Cf. A014580, A091225, A091228, A305419, A305421.

Cf. also A151800, A305430.

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };

For n >= 1, a(n) = A091228(1+n).

A305418 Permutation of nonnegative integers: a(1) = 0, a(2n) = 1 + 2a(n), a(2n+1) = 2a(A305422(2n+1)).

Original entry on oeis.org

0, 1, 2, 3, 6, 5, 4, 7, 10, 13, 8, 11, 16, 9, 14, 15, 30, 21, 32, 27, 12, 17, 34, 23, 64, 33, 22, 19, 18, 29, 128, 31, 258, 61, 36, 43, 256, 65, 38, 55, 512, 25, 130, 35, 46, 69, 1024, 47, 20, 129, 62, 67, 66, 45, 2048, 39, 70, 37, 4096, 59, 8192, 257, 26, 63, 54, 517, 16384, 123, 24, 73, 16386, 87, 32768, 513, 142, 131, 8194, 77, 132, 111, 48, 1025, 42, 51

Offset: 1

Antti Karttunen, Jun 10 2018

nonn

This is GF(2)[X] analog of A156552. Note the indexing: the domain starts from 1, while the range includes also zero.

Cf. A305417 (inverse).
Cf. A305422.
Cf. also A091203, A156552, A052331, A305428.

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A305418(n) = if(1==n,(n-1),if(!(n%2),1+(2*(A305418(n/2))),2*A305418(A305422(n))));

a(1) = 0, a(2n) = 1 + 2*a(n), a(2n+1) = 2*a(A305422(2n+1)).
a(n) = A054429(A305428(n)).
For all n >= 1:
A000120(a(n)) = A091222(n).
A069010(a(n)) = A091221(n).
A106737(a(n)) = A091220(n).
A132971(a(n)) = A091219(n).
A085357(a(n)) = A304109(n).

A304529 a(1) = 0, a(2n) = n, a(2n+1) = a(A305422(2n+1)).

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 1, 4, 3, 5, 1, 6, 1, 7, 4, 8, 8, 9, 1, 10, 2, 11, 11, 12, 1, 13, 6, 14, 7, 15, 1, 16, 25, 17, 7, 18, 1, 19, 14, 20, 1, 21, 19, 22, 12, 23, 1, 24, 3, 25, 16, 26, 13, 27, 1, 28, 22, 29, 1, 30, 1, 31, 5, 32, 10, 33, 1, 34, 2, 35, 59, 36, 1, 37, 44, 38, 55, 39, 13, 40, 2, 41, 9, 42, 32, 43, 1, 44, 47, 45, 1, 46, 19, 47, 26, 48, 1, 49, 50, 50

Offset: 1

Antti Karttunen, Jun 10 2018

nonn

This is GF(2)[X] analog of A246277.
For all i, j: a(i) = a(j) => A278233(i) = A278233(j).
For all i, j: a(i) = a(j) => A305788(i) = A305788(j).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A305422, A305425.
Cf. A014580 (positions of 1's), A278233, A305788.
Cf. also A246277.

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A304529(n) = if(1==n,0,while(n%2, n = A305422(n)); n/2);

a(1) = 0, a(2n) = n, a(2n+1) = a(A305422(2n+1)).

A305425 a(n) = n/2 for even n, a(n) = A305422(n) for odd n.

Original entry on oeis.org

1, 1, 2, 2, 4, 3, 3, 4, 6, 5, 7, 6, 11, 7, 8, 8, 16, 9, 13, 10, 5, 11, 22, 12, 19, 13, 12, 14, 14, 15, 25, 16, 50, 17, 29, 18, 31, 19, 28, 20, 37, 21, 38, 22, 24, 23, 41, 24, 9, 25, 32, 26, 26, 27, 47, 28, 44, 29, 55, 30, 59, 31, 10, 32, 20, 33, 61, 34, 21, 35, 118, 36, 67, 37, 88, 38, 110, 39, 53, 40, 69, 41, 18, 42, 64, 43, 73, 44, 94, 45, 87, 46, 43, 47

Offset: 1

Antti Karttunen, Jun 08 2018

nonn

Each k occurs exactly twice, at 2k and at A305421(k).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to polynomials in ring GF(2)[X]

Bisections: A000027 and A305422.

Cf. also A252463.

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A305425(n) = if(n%2,A305422(n),n/2);

a(n) = n/2 if n is even, a(n) = A305422(n) if n is odd.

A305428 Permutation of nonnegative integers: a(1) = 0, a(2) = 1, a(2n) = 2a(n), a(2n+1) = 1 + 2a(A305422(2n+1)).

Original entry on oeis.org

0, 1, 3, 2, 5, 6, 7, 4, 13, 10, 15, 12, 31, 14, 9, 8, 17, 26, 63, 20, 11, 30, 61, 24, 127, 62, 25, 28, 29, 18, 255, 16, 509, 34, 59, 52, 511, 126, 57, 40, 1023, 22, 253, 60, 49, 122, 2047, 48, 27, 254, 33, 124, 125, 50, 4095, 56, 121, 58, 8191, 36, 16383, 510, 21, 32, 41, 1018, 32767, 68, 23, 118, 32765, 104, 65535, 1022, 241, 252, 16381, 114, 251, 80, 47

Offset: 1

Antti Karttunen, Jun 10 2018

nonn

Note the indexing: the domain starts from 1, while the range includes also zero.

This is GF(2)[X] analog of A243071.

Cf. A305427 (inverse).
Cf. A305422.
Cf. also A243071, A305418.

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A305428(n) = if(n<=2,(n-1),if(!(n%2),2*A305428(n/2),1+(2*(A305428(A305422(n))))));

a(1) = 0, a(2) = 1, a(2n) = 2*a(n), a(2n+1) = 1 + 2*a(A305422(2n+1)).

a(n) = A054429(A305418(n)).

A305429 Largest k < n whose binary expansion encodes an irreducible (0,1)-polynomial over Q, with a(1) = a(2) = 1.

Original entry on oeis.org

1, 1, 2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11, 13, 13, 13, 13, 17, 17, 19, 19, 19, 19, 23, 23, 25, 25, 25, 25, 29, 29, 31, 31, 31, 31, 31, 31, 37, 37, 37, 37, 41, 41, 43, 43, 43, 43, 47, 47, 47, 47, 47, 47, 53, 53, 55, 55, 55, 55, 59, 59, 61, 61, 61, 61, 61, 61, 67, 67, 69, 69, 71, 71, 73, 73, 73, 73, 77, 77, 79, 79, 81, 81, 83, 83, 83, 83, 87, 87

Offset: 1

Antti Karttunen, Jun 07 2018

nonn

For n >= 3, a(n) is the largest term of A206074 less than n.

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

Cf. A206074, A257000, A305430.

Cf. also A151799 (A136548), A305419.

A257000(n) = polisirreducible(Pol(binary(n)));
A305429(n) = if(n<3,1, my(k=n-1); while(k>1 && !A257000(k),k--); (k));

A305424 Permutation of natural numbers: a(n) = A305422(2*n-1).

Original entry on oeis.org

1, 2, 4, 3, 6, 7, 11, 8, 16, 13, 5, 22, 19, 12, 14, 25, 50, 29, 31, 28, 37, 38, 24, 41, 9, 32, 26, 47, 44, 55, 59, 10, 20, 61, 21, 118, 67, 88, 110, 53, 69, 18, 64, 73, 94, 87, 43, 52, 91, 100, 58, 97, 56, 15, 103, 62, 82, 109, 115, 48, 23, 74, 76, 49, 98, 117, 113, 152, 131, 46, 148, 137, 143, 164, 218, 27, 96, 227, 145, 230, 89, 182, 200

Offset: 1

Antti Karttunen, Jun 08 2018

nonn

Odd bisection of A305422 and A305425.

Cf. A305423 (inverse).
Cf. A014580, A091225, A304522, A305425.
Cf. also A064216.

A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A305424(n) = A305422(n+n-1);

a(n) = A305422(2*n-1).

cp's OEIS Frontend

A091203 Factorization-preserving isomorphism from binary codes of GF(2) polynomials to integers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305422 GF(2)[X] factorization prime shift towards smaller terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305420 Smallest k > n whose binary expansion encodes an irreducible (0,1)-polynomial over GF(2)[X].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305418 Permutation of nonnegative integers: a(1) = 0, a(2n) = 1 + 2*a(n), a(2n+1) = 2*a(A305422(2n+1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A304529 a(1) = 0, a(2n) = n, a(2n+1) = a(A305422(2n+1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305425 a(n) = n/2 for even n, a(n) = A305422(n) for odd n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305428 Permutation of nonnegative integers: a(1) = 0, a(2) = 1, a(2n) = 2*a(n), a(2n+1) = 1 + 2*a(A305422(2n+1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305429 Largest k < n whose binary expansion encodes an irreducible (0,1)-polynomial over Q, with a(1) = a(2) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A305418 Permutation of nonnegative integers: a(1) = 0, a(2n) = 1 + 2a(n), a(2n+1) = 2a(A305422(2n+1)).

A305428 Permutation of nonnegative integers: a(1) = 0, a(2) = 1, a(2n) = 2a(n), a(2n+1) = 1 + 2a(A305422(2n+1)).