A305420 -id:A305420 - cp's OEIS frontend

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

Offset: 0

Antti Karttunen, Jan 03 2004

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

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

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

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)

A305419 Largest k < n whose binary expansion encodes an irreducible (0,1)-polynomial over GF(2)[X], with a(1) = a(2) = 1.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jun 07 2018

nonn

For n >= 3, a(n) is the largest term of A014580 less 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, A305420, A305422.

Cf. also A151799 (A136548), A305429.

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));

A305421 GF(2)[X] factorization prime shift towards larger terms.

Original entry on oeis.org

1, 3, 7, 5, 21, 9, 11, 15, 49, 63, 13, 27, 19, 29, 107, 17, 273, 83, 25, 65, 69, 23, 121, 45, 31, 53, 151, 39, 35, 189, 37, 51, 251, 819, 173, 245, 41, 43, 233, 195, 47, 207, 93, 57, 997, 139, 55, 119, 127, 33, 1911, 95, 79, 441, 59, 105, 367, 101, 61, 455, 67, 111, 475, 85, 1281, 269, 73, 1365, 81, 503, 457, 287, 87, 123, 1549, 125, 179, 315

Offset: 1

Antti Karttunen, Jun 07 2018

nonn

Permutation of the odd numbers, A005408.

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 A014580(i) x A014580(j) x ... x A014580(k), 1 <= i <= j <= ... <= k, a(n) = A014580(1+i) x A014580(1+j) x ... x A014580(1+k).

			For n = 12, which by its binary representation '1100' corresponds with (0,1)-polynomial x^3 + x^2, which over GF(2)[X] is factored as (x)(x)(x+1), i.e., 12 = A048720(2,A048720(2,3)) = A048720(A014580(1), A048720(A014580(1),A014580(2))), we then form a(12) as A048720(A014580(2), A048720(A014580(2),A014580(3))) = A048720(3,A048720(3,7)) = 27. Note that x, x+1 and x^2 + x + 1 are the three smallest irreducible (0,1)-polynomials when factored over GF(2)[X], and their binary representations 2, 3 and 7 are the three initial terms of A014580.

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

Cf. A305422 (a left inverse).
Cf. A001317, A014580, A091225, A193231, A268389, A305420, A305423.
Cf. also A003961, A300841.

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); };

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

A305417 Permutation of natural numbers: a(0) = 1, a(2n) = A305421(a(n)), a(2n+1) = 2*a(n).

Original entry on oeis.org

1, 2, 3, 4, 7, 6, 5, 8, 11, 14, 9, 12, 21, 10, 15, 16, 13, 22, 29, 28, 49, 18, 27, 24, 69, 42, 63, 20, 107, 30, 17, 32, 19, 26, 23, 44, 35, 58, 39, 56, 127, 98, 83, 36, 151, 54, 45, 48, 81, 138, 207, 84, 475, 126, 65, 40, 743, 214, 189, 60, 273, 34, 51, 64, 25, 38, 53, 52, 121, 46, 57, 88, 173, 70, 101, 116, 233, 78, 105, 112, 199, 254, 129

Offset: 0

Antti Karttunen, Jun 10 2018

This is GF(2)[X] analog of A005940, but note the indexing: here the domain starts from 0, although the range excludes zero.
This sequence can be represented as a binary tree. Each child to the left is obtained by applying A305421 to the parent, and each child to the right is obtained by doubling the parent:
                                     1
                                     |
                  ...................2...................
                 3                                       4
       7......../ \........6                   5......../ \........8
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  11       14          9       12         21       10         15       16
13  22   29  28      49 18   27  24     69  42   63  20    107  30   17  32
Sequence A305427 is obtained by scanning the same tree level by level from right to left.

Cf. A305418 (inverse), A305427 (mirror image).
Cf. A014580 (left edge from 2 onward), A305421.
Cf. also A005940, A052330, A091202.

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); };
A305417(n) = if(0==n,(1+n),if(!(n%2),A305421(A305417(n/2)),2*(A305417((n-1)/2))));

a(0) = 1, a(2n) = A305421(a(n)), a(2n+1) = 2*a(n).
a(n) = A305427(A054429(n)).
For all n >= 1, a(A000079(n-1)) = A014580(n).

A305427 Permutation of natural numbers: a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A305421(a(n)).

Original entry on oeis.org

1, 2, 4, 3, 8, 5, 6, 7, 16, 15, 10, 21, 12, 9, 14, 11, 32, 17, 30, 107, 20, 63, 42, 69, 24, 27, 18, 49, 28, 29, 22, 13, 64, 51, 34, 273, 60, 189, 214, 743, 40, 65, 126, 475, 84, 207, 138, 81, 48, 45, 54, 151, 36, 83, 98, 127, 56, 39, 58, 35, 44, 23, 26, 19, 128, 85, 102, 1911, 68, 819, 546, 4113, 120, 455, 378, 3253, 428, 1833, 1486, 925, 80

Offset: 0

Antti Karttunen, Jun 10 2018

Note the indexing: Domain starts from 0, while range starts from 1.
This is GF(2)[X] analog of A163511.
This sequence can be represented as a binary tree. Each child to the left is obtained by doubling the parent, and each child to the right is obtained by applying A305421 to the parent:
                                     1
                                     |
                  ...................2...................
                 4                                       3
       8......../ \........5                   6......../ \........7
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  16       15         10       21         12       9          14       11
32  17   30  107    20  63   42  69     24  27   18 49      28  29   22  13
etc.
Sequence A305417 is obtained by scanning the same tree level by level from right to left.

Cf. A305428 (inverse), A305417 (mirror image).
Cf. A305421.
Cf. also A091202, A163511.

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); };
A305427(n) = if(n<=1,(1+n),if(!(n%2),2*A305427(n/2),A305421(A305427((n-1)/2))));

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

a(n) = A305417(A054429(n)).

A305430 Smallest k > n whose binary expansion encodes an irreducible (0,1)-polynomial over Q.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jun 07 2018

nonn

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

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

Cf. A206074, A257000, A305429.

Cf. also A151800, A305420.

binPol[n_, x_] := With[{bb = IntegerDigits[n, 2]},bb.x^Range[Length[bb]-1, 0, -1]];
b[n_] := If[IrreduciblePolynomialQ[binPol[n, x]], 1, 0];
a[n_] := Module[{k = n+1}, While[b[k] == 0, k++]; k];
Array[a, 100] (* Jean-François Alcover, Dec 20 2021 *)

A257000(n) = polisirreducible(Pol(binary(n)));
A305430(n) = { my(k=1+n); while(!A257000(k),k++); (k); };

A305423 Permutation of natural numbers: a(n) = (A305421(n)+1)/2.

Original entry on oeis.org

1, 2, 4, 3, 11, 5, 6, 8, 25, 32, 7, 14, 10, 15, 54, 9, 137, 42, 13, 33, 35, 12, 61, 23, 16, 27, 76, 20, 18, 95, 19, 26, 126, 410, 87, 123, 21, 22, 117, 98, 24, 104, 47, 29, 499, 70, 28, 60, 64, 17, 956, 48, 40, 221, 30, 53, 184, 51, 31, 228, 34, 56, 238, 43, 641, 135, 37, 683, 41, 252, 229, 144, 44, 62, 775, 63, 90, 158, 109, 163, 131, 57

Offset: 1

Antti Karttunen, Jun 08 2018

nonn

Cf. A305424 (inverse).
Cf. A014580, A091225, A304521.
Cf. also A048673.

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); };
A305423(n) = ((1+A305421(n))/2);

a(n) = (A305421(n)+1)/2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305419 Largest k < n whose binary expansion encodes an irreducible (0,1)-polynomial over GF(2)[X], with a(1) = a(2) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A305421 GF(2)[X] factorization prime shift towards larger terms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A305417 Permutation of natural numbers: a(0) = 1, a(2n) = A305421(a(n)), a(2n+1) = 2*a(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305427 Permutation of natural numbers: a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A305421(a(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A305430 Smallest k > n whose binary expansion encodes an irreducible (0,1)-polynomial over Q.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A305423 Permutation of natural numbers: a(n) = (A305421(n)+1)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula