A091222 -id:A091222 - cp's OEIS frontend

A235032 Numbers which are factored to the same set of primes in Z as to the binary codes of irreducible polynomials in GF(2)[X].

0, 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 19, 22, 24, 26, 28, 31, 32, 37, 38, 41, 44, 47, 48, 52, 56, 59, 61, 62, 64, 67, 73, 74, 76, 82, 88, 94, 96, 97, 103, 104, 109, 111, 112, 118, 122, 123, 124, 128, 131, 134, 137, 146, 148, 152, 157, 164, 167, 176, 188

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

This is a subsequence of the sequence which gives all such n that A001222(n) = A091222(n).

			2, 3 and 11 are included in this sequence, because they occur in A091206. That is, they are all primes, and encode irreducible polynomials in ring GF(2)[X] via their binary representations: For 2, '10' in binary, corresponds to polynomial x, and for 3, '11' in binary, corresponds to polynomial x+1, and for 11, '1011' in binary, corresponds to polynomial x^3+x+1, which are all irreducible in GF(2)[X].
4 is included in this sequence, because it factors as 2*2, but also because the corresponding GF(2)[X] polynomial x^2 factors as x*x (with the polynomial x encoded by the number 2).
5 is NOT included in this sequence, because, although it is prime, the corresponding polynomial (5 in binary is '101'): x^2 + 1 is not irreducible in GF(2)[X], but factors as (x+1)(x+1), i.e., we have 5 = A048720(3,3).
111 is included, as it is a product of two primes, 3*37, and these primes encode via their binary representations, '11' and '100101', two polynomials irreducible in GF(2)[X]: x+1 and x^5 + x^2 + 1, whose product, x^6 + x^5 + x^3 + x^2 + x + 1, is encoded by 111's binary representation, '1101111'.

Complement: A235033. Intersection of A235034 & A235035. Union of A091206 & A235036. Subsequence of A235045.
A235036 and A235039 give composite and odd composite (after 1) terms occurring in this sequence.
Gives the positions of zeros in A236380, i.e. such n that A234741(n) = A234742(n).
Cf. also A048720.

A235033 Numbers which are factored to a different set of primes in Z as to the irreducible polynomials in GF(2)[X].

Original entry on oeis.org

5, 9, 10, 15, 17, 18, 20, 21, 23, 25, 27, 29, 30, 33, 34, 35, 36, 39, 40, 42, 43, 45, 46, 49, 50, 51, 53, 54, 55, 57, 58, 60, 63, 65, 66, 68, 69, 70, 71, 72, 75, 77, 78, 79, 80, 81, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 95, 98, 99, 100, 101, 102, 105, 106

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

If a term is included in this sequence, then all its ordinary multiples as well as any "A048720-multiples" are included as well. (Cf. the characteristic function A235046.)

The sequence which gives all such n that A001222(n) differs from A091222(n) is a subsequence of this sequence.

			5 is included in this sequence, because, although it is prime, its binary representation '101' encodes a polynomial x^2 + 1, which is reducible in polynomial ring GF(2)[X] as (x+1)(x+1), i.e., 5 = A048720(3,3).
9 is included in this sequence, as it factors as 3*3 in Z, the corresponding polynomial (bin.repr. '1001'): x^3 + 1 factors as (x+1)(x^2+x+1), i.e., 9 = A048720(3,7), so even although the number of prime/irreducible factors is the same, the factors themselves (i.e., their binary codes) are not exactly the same, thus 9 is included here.
On the other hand, none of 2, 3, 4, 11 and 111 are included in this sequence because they occur in the complement sequence, A235032 (please see examples there).

Gives the positions of nonzeros in A236380, i.e., n such that A234741(n) <> A234742(n).
Characteristic function: A235046.
Complement: A235032. Subsets: A091209, A091214.

A280505 The palindromic kernel of n in base 2 (with carryless GF(2)[X] factorization): a(n) = A091255(n,A057889(n)).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 12, 1, 14, 15, 16, 17, 18, 1, 20, 21, 2, 3, 24, 1, 2, 27, 28, 3, 30, 31, 32, 33, 34, 7, 36, 1, 2, 5, 40, 1, 42, 3, 4, 45, 6, 1, 48, 7, 2, 51, 4, 3, 54, 1, 56, 5, 6, 1, 60, 1, 62, 63, 64, 65, 66, 1, 68, 1, 14, 3, 72, 73, 2, 15, 4, 3, 10, 7, 80, 1, 2, 9, 84, 85, 6, 1, 8, 3, 90, 1, 12, 93, 2, 5, 96, 1, 14, 99, 4, 9, 102, 1, 8, 15, 6

Offset: 1

Antti Karttunen, Jan 09 2017

a(n) = the maximal GF(2)[X]-divisor of n which in base 2 is either a palindrome or becomes a palindrome if trailing 0's are omitted.
More precisely: a(n) = the unique term m of A057890 for which A280500(n,m) > 0 and A091222(m) >= A091222(k) for all such terms k of A057890 for which A280500(n,k) > 0.
All terms are in A057890 and each term of A057890 occurs an infinite number of times.

Cf. A048720, A057889, A057890, A091222, A091255, A280501, A280503, A280506.

(define (A280505 n) (A091255bi n (A057889 n))) ;; A091255bi implements the 2-argument GF(2)[X] GCD-function (A091255).

a(n) = A091255(n,A057889(n)).
Other identities. For all n >= 1:
a(A057889(n)) = a(n).
A048720(a(n), A280506(n)) = n.

A331166 a(n) = min(n, A057889(n)), where A057889 is bijective base-2 reverse.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 11, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 19, 22, 27, 28, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 37, 42, 43, 44, 45, 46, 47, 48, 35, 38, 51, 44, 43, 54, 55, 56, 39, 46, 55, 60, 47, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 69, 74, 83, 84, 85, 86, 87, 88, 77, 90, 91, 92, 93, 94, 95, 96, 67, 70

Offset: 0

Antti Karttunen, Jan 12 2020

There is a large number of sequences b, related to binary expansion of n (A007088), for which it holds that b(n) = b(a(n)) for all n >= 0 (or n >= 1). For example, we have:
For all i, j:
  a(i) = a(j) => A002487(i) = A002487(j),
  a(i) = a(j) => A005811(i) = A005811(j),
  a(i) = a(j) => A286622(i) = A286622(j) => A000120(i) = A000120(j).
For all i, j > 0:
  a(i) = a(j) => A007814(i) = A007814(j),
  a(i) = a(j) => A280505(i) = A280505(j),
  a(i) = a(j) => A305788(i) = A305788(j) => A091222(i) = A091222(j).

Antti Karttunen, Table of n, a(n) for n = 0..16383
Antti Karttunen, Data supplement: n, a(n) computed for n = 0..65537
Index entries for sequences related to binary expansion of n

Cf. A000120, A002487, A005811, A007088, A007814, A030101, A057889, A091222, A280505, A286622, A305788.

Cf. also A330740, A331167, A331173.

A030101(n) = if(n<1,0,subst(Polrev(binary(n)),x,2));
A057889(n) = if(!n,n,A030101(n/(2^valuation(n,2))) * (2^valuation(n, 2)));
A331166(n) = min(n, A057889(n));

a(n) = min(n, A057889(n)).

A304107 Analog for squarefree numbers when n is factored in polynomial ring GF(2)[X], so that the binary expansion of n defines the corresponding (0,1)-polynomial. These are numbers n such that the said polynomial doesn't have any duplicated irreducible divisors.

Original entry on oeis.org

1, 2, 3, 6, 7, 9, 11, 13, 14, 18, 19, 22, 23, 25, 26, 29, 31, 33, 35, 37, 38, 41, 43, 46, 47, 49, 50, 53, 55, 58, 59, 61, 62, 66, 67, 70, 71, 73, 74, 77, 79, 82, 83, 86, 87, 89, 91, 93, 94, 97, 98, 101, 103, 106, 109, 110, 111, 113, 115, 117, 118, 121, 122, 123, 127, 129, 131, 133, 134, 137, 139, 142, 143, 145, 146, 149, 154, 155, 157, 158, 159, 161

Offset: 1

Antti Karttunen, May 13 2018

nonn

Positions of nonzeros in A091219 and A304109. Numbers n such that A091221(n) = A091222(n).
Numbers n that cannot be expressed as n = A048720(k,A000695(m)) for any k >= 0, m >= 2.
It seems that a(n) is approximately 2n for large n. See also comments in A304110.

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

Cf. A304108 (complement), A304109 (characteristic function), A304110 (least monotonic left inverse).
Cf. A000695, A014580, A048720, A091219, A091221, A091222, A304111.
Cf. also A005117.

A304109(n) = { my(fm=factor(Pol(binary(n))*Mod(1, 2))); for(k=1, #fm~, if(fm[k, 2] > 1, return(0))); (1); };
k=0; n=0; while(k<100, n++; if(A304109(n), k++; print1(n,", ")));

For n >= 1, A304110(a(n)) = 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).

A304108 Numbers n such that the (0,1)-polynomial encoded in binary expansion of n has at least one duplicated irreducible divisor when the factorization is done in polynomial ring GF(2)[X].

Original entry on oeis.org

4, 5, 8, 10, 12, 15, 16, 17, 20, 21, 24, 27, 28, 30, 32, 34, 36, 39, 40, 42, 44, 45, 48, 51, 52, 54, 56, 57, 60, 63, 64, 65, 68, 69, 72, 75, 76, 78, 80, 81, 84, 85, 88, 90, 92, 95, 96, 99, 100, 102, 104, 105, 107, 108, 112, 114, 116, 119, 120, 124, 125, 126, 128, 130, 132, 135, 136, 138, 140, 141, 144, 147, 148, 150, 151, 152, 153, 156, 160, 162

Offset: 1

Antti Karttunen, May 13 2018

nonn

Positions of zeros in A091219 and A304109. Numbers n such that A091221(n) < A091222(n).

			4 is present as 4 = A048720(2,2) = A048720(A014580(1), A014580(1)).
5 is present as 5 = A048720(3,3) = A048720(A014580(2), A014580(2)).
10 is present as 10 = A048720(2,A048720(3,3)).

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

Cf. A304107 (complement).
Cf. A014580, A048720, A091219, A091221, A091222, A304109.
Cf. also A013929.

isA304108(n) = { my(fm=factor(Pol(binary(n))*Mod(1, 2))); for(k=1, #fm~, if(fm[k, 2] > 1, return(1))); (0); };
k=0; n=0; while(k<100, n++; if(isA304108(n), k++; print1(n,", ")));

A091248 Number of irreducible factors in the factorization of X^n + 1 over GF(2) (counted with multiplicity).

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 3, 8, 3, 4, 2, 8, 2, 6, 5, 16, 3, 6, 2, 8, 6, 4, 3, 16, 3, 4, 4, 12, 2, 10, 7, 32, 5, 6, 6, 12, 2, 4, 5, 16, 3, 12, 4, 8, 8, 6, 3, 32, 5, 6, 8, 8, 2, 8, 5, 24, 5, 4, 2, 20, 2, 14, 13, 64, 7, 10, 2, 12, 6, 12, 3, 24, 9, 4, 8, 8, 6, 10, 3, 32, 5, 6, 2, 24, 12, 8, 5, 16, 9, 16

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Antti Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials.

Cf. A000374 (number of distinct irreducible factors of the same polynomials).

Cf. A000051, A091222, A318622.

h:= proc(n) option remember;  numtheory:-phi(n)/numtheory:-order(2,n/2^padic:-ordp(n,2)) end proc:
f:= n -> add(h(d),d=numtheory:-divisors(n)):
map(f, [$1..100]); # Robert Israel, Aug 30 2018

h[n_] := EulerPhi[n]/MultiplicativeOrder[2, n/2^IntegerExponent[n, 2]];
a[n_] := DivisorSum[n, h];
Array[a, 100] (* Jean-François Alcover, Aug 19 2022, after Robert Israel *)

a(n) = A091222(A000051(n)).

a(n) = Sum_{d|n} A318622(d). - Robert Israel, Aug 30 2018

A256170 Irregular triangle where the n-th row contains the binary representations of the factors of the member of GF(2)[x] whose binary representation is n.

Original entry on oeis.org

2, 3, 2, 2, 3, 3, 2, 3, 7, 2, 2, 2, 3, 7, 2, 3, 3, 11, 2, 2, 3, 13, 2, 7, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 3, 2, 3, 7, 19, 2, 2, 3, 3, 7, 7, 2, 11, 3, 13, 2, 2, 2, 3, 25, 2, 13, 3, 3, 7, 2, 2, 7, 3, 11, 2, 3, 3, 3, 31, 2, 2, 2, 2, 2, 3, 31

Offset: 2

Franklin T. Adams-Watters, Jun 07 2015

			9 is 1001 in binary, so it corresponds to x^3 + 1 in GF(2)[x]. This factors as (x+1) * (x^2+x+1), which have binary representations 3 and 7; so row 9 is 3, 7.
The triangle starts:
[empty row for n=1]
2
3
2, 2,
3, 3
2, 3
7
2, 2, 2
3, 7
2, 3, 3
11
2, 2, 3
13
2, 7
3, 3, 3

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

Cf. A014580, A027746, A091222 (row lengths).

f:= proc(n)
  local L,P,R;
  L:= convert(n,base,2);
  P:= add(L[i]*X^(i-1),i=1..nops(L));
  R:= Factors(P) mod 2;
  op(sort([seq(eval(r[1],X=2)$r[2], r=R[2])]));
end proc:
seq(f(n), n=1..50); # Robert Israel, Jun 07 2015

arow(n)=my(fm=factor(Pol(binary(n))*Mod(1,2)),x=2,np,r,k);for(k=1,(np=#fm~),fm[k,1]=eval(lift(fm[k,1])));r=vector(sum(j=1,np,fm[j,2]));k=0;for(j=1,np,for(i=1,fm[j,2],r[k++]=fm[j,1]));r

A136379 Number of irreducible polynomials (counted with multiplicity) dividing A036284(n), when it is considered as a GF(2)[X]-polynomial.

Original entry on oeis.org

2, 4, 9, 17, 25, 42, 76, 143, 273, 533, 1052, 2072, 4122, 8221, 16417, 32799

Offset: 0

Antti Karttunen, Dec 29 2007

nonn

a(n) = A091222(A036284(n)).

cp's OEIS Frontend

A235032 Numbers which are factored to the same set of primes in Z as to the binary codes of irreducible polynomials in GF(2)[X].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A235033 Numbers which are factored to a different set of primes in Z as to the irreducible polynomials in GF(2)[X].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A280505 The palindromic kernel of n in base 2 (with carryless GF(2)[X] factorization): a(n) = A091255(n,A057889(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A331166 a(n) = min(n, A057889(n)), where A057889 is bijective base-2 reverse.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A304107 Analog for squarefree numbers when n is factored in polynomial ring GF(2)[X], so that the binary expansion of n defines the corresponding (0,1)-polynomial. These are numbers n such that the said polynomial doesn't have any duplicated irreducible divisors.

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

A304108 Numbers n such that the (0,1)-polynomial encoded in binary expansion of n has at least one duplicated irreducible divisor when the factorization is done in polynomial ring GF(2)[X].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A091248 Number of irreducible factors in the factorization of X^n + 1 over GF(2) (counted with multiplicity).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A256170 Irregular triangle where the n-th row contains the binary representations of the factors of the member of GF(2)[x] whose binary representation is n.

Views

Author

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