A257688 -id:A257688 - cp's OEIS frontend

A206074 n-th irreducible polynomial over Q (with coefficients 0 or 1) evaluated at x=2.

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 97, 101, 103, 107, 109, 113, 115, 117, 121, 127, 131, 137, 139, 143, 145, 149, 151, 157, 163, 167, 169, 171, 173, 179, 181, 185, 191, 193, 197, 199, 203, 205, 209, 211, 213, 223, 227, 229

Offset: 1

Clark Kimberling, Feb 03 2012

nonn

Is every prime present?
Yes, see the Filaseta reference. - Thomas Ordowski, Feb 19 2014
Corresponding evaluation at x=10 is A206073. - Michael Somos, Feb 26 2014

			(See the example at A206073.)

Antti Karttunen, Table of n, a(n) for n = 1..21692
John Brillhart, Michael Filaseta, Andrew Odlyzko, On an irreducibility theorem of A. Cohn, Canad. J. Math. 33(1981), pp. 1055-1059.
Michael Filaseta, A further generalization of an irreducibility theorem of A. Cohn, Canad J. Math. 34 (1982), pp. 1390-1395.

Cf. A206073, A205783 (complement), A206075 (nonprime terms), A014580 (irreducible over GF(2), a subsequence of this one), A000040 (primes, also a subsequence), A260427 (terms that are reducible over GF(2)).
Cf. A255574 (left inverse).
Cf. also permutations A260421 - A260426.
Disjoint union of A257688 (without 1) and A260428.
a(n) differs from A186891(n+1) for the first time at n=21, where a(21) = 67, while A186891(22) = 65, a term missing from here. There are several other sequences that do not diverge until after approx. the twentieth term from this one (see the context-links).

t = Table[IntegerDigits[n, 2], {n, 1, 850}];
b[n_] := Reverse[Table[x^k, {k, 0, n}]]
p[n_, x_] := t[[n]].b[-1 + Length[t[[n]]]]
Table[p[n, x], {n, 1, 15}]
u = {}; Do[n++; If[IrreduciblePolynomialQ[p[n, x]],
AppendTo[u, n]], {n, 300}];
u                          (* A206074 *)
Complement[Range[200], u]  (* A205783 *)
b[n_] := FromDigits[IntegerDigits[u, 2][[n]]]
Table[b[n], {n, 1, 40}]    (* A206073 *)

for(n=2, 10^3, if( polisirreducible( Pol(binary(n)) ), print1(n,", ") ) ); \\ Joerg Arndt, Feb 19 2014

Other identities and observations. For all n >= 1:

A255574(a(n)) = n.

Clarified name, added more terms, Joerg Arndt, Feb 20 2014

A091206 Primes whose binary representation encodes a polynomial irreducible over GF(2).

Original entry on oeis.org

2, 3, 7, 11, 13, 19, 31, 37, 41, 47, 59, 61, 67, 73, 97, 103, 109, 131, 137, 157, 167, 191, 193, 211, 229, 239, 241, 283, 313, 379, 397, 419, 433, 463, 487, 499, 557, 563, 587, 601, 607, 613, 617, 631, 647, 661, 677, 701, 719, 757, 761, 769, 787, 827, 859

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

"Encoded in binary representation" means that a polynomial a(n)*X^n+...+a(0)*X^0 over GF(2) is represented by the binary number a(n)*2^n+...+a(0)*2^0 in Z (where each coefficient a(k) = 0 or 1).

Subsequence with Hamming weight nonprime starts 2, 1019, 1279, 1531, 1663, 1759, 1783, 1789, 2011, 2027, 2543, 2551, ... [Joerg Arndt, Nov 01 2013]. These are now given by A255569. - Antti Karttunen, May 14 2015

Antti Karttunen, Table of n, a(n) for n = 1..10226; all terms up to 1048357, binary length 20
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences related to binary encoded polynomials over GF(2)

Intersection of A014580 and A000040.
Apart from a(2) = 3 a subsequence of A027697. The numbers in A027697 but not here are listed in A238186.
Also subsequence of A235045 (its primes. Cf. also A235041-A235042).
Cf. A091209 (Primes whose binary expansion encodes a polynomial reducible over GF(2)), A091212 (Composite, and reducible over GF(2)), A091214 (Composite, but irreducible over GF(2)), A257688 (either 1, prime or irreducible over GF(2)).
Subsequence: A255569.

okQ[p_] := Module[{id, pol, x}, id = IntegerDigits[p, 2] // Reverse; pol = id.x^Range[0, Length[id] - 1]; IrreduciblePolynomialQ[pol, Modulus -> 2]];
Select[Prime[Range[1000]], okQ] (* Jean-François Alcover, Feb 06 2023 *)

is(n)=polisirreducible( Mod(1,2) * Pol(digits(n,2)) );
forprime(n=2,10^3,if (is(n), print1(n,", ")));
\\ Joerg Arndt, Nov 01 2013

a(n) = A000040(A091207(n)) = A014580(A091208(n)).

A091212 Composite numbers whose binary representation encodes a polynomial reducible over GF(2).

Original entry on oeis.org

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 88, 90, 92, 93, 94, 95, 96, 98, 99

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

"Encoded in binary representation" means that a polynomial a(n)*X^n+...+a(0)*X^0 over GF(2) is represented by the binary number a(n)*2^n+...+a(0)*2^0 in Z (where each coefficient a(k) = 0 or 1).
From Reinhard Zumkeller, Jul 05-12 2011, values for maximum n corrected by Antti Karttunen, May 18 2015: (Start)
a(n) = A192506(n) for n <= 36.
a(n) = A175526(n) for n <= 36.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..55429
A. Karttunen, Scheme-program for computing beginning of this sequence.
Index entries for sequences related to binary encoded polynomials over GF(2)

Intersection of A002808 and A091242.
Cf. A257688 (complement, either 1, irreducible in GF(2)[X] or prime), A091206 (prime and irreducible), A091209 (prime and reducible), A091214 (nonprime and irreducible).
Cf. A091213, A236861, A235036 (a subsequence, apart from 1).
Differs from both A175526 and A192506 for the first time at n=37, where a(37) = 56, while A175526(37) = A192506(37) = 55, a term missing from here (as 55 encodes a polynomial which is irreducible in GF(2)[X]).
Differs from its subsequence A205783(n+1) for the first time at n=47, where a(47) = 69, while 69 is missing from A205783.

isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
isA091212(n) = ((n > 1) && !isprime(n) && !isA014580(n));
n = 0; i = 0; while(n < 2^16, n++; if(isA091212(n), i++; write("b091212.txt", i, " ", n)));

a(n) = A091242(A091213(n)).

A257691 Numbers that are not A000120-abundant.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 101, 103, 107, 109, 111, 113, 119, 121, 123, 125, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 211, 219, 221, 223, 227, 229, 233, 239, 241, 247, 251, 257

Offset: 1

Antti Karttunen, May 11 2015

nonn

A000120-nonabundant numbers: Numbers n for which A192895(n) <= 0.

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

Cf. A000120, A192895.
Complement of A175526 (A000120-abundant numbers).
Disjoint union of A175522 (A000120-perfect numbers) and A175524 (A000120-deficient numbers).
Differs from A206074(n-1), A186891(n) and A257688(n) for the first time at n=19, where a(19) = 59, while A206074(18) = A186891(19) = A257688(19) = 55, a term missing from here.
Differs from A257689 for the first time at n=24, where a(24) = 79, while A257689(24) = 77, a term missing from here.

A192895[n_] := DivisorSum[n, Total[IntegerDigits[#, 2]]*(-1)^Boole[# == n]& ]; Reap[For[n=1, n<300, n++, If[A192895[n] <= 0, Sow[n]]]][[2, 1]] (* Jean-François Alcover, Dec 05 2015 *)

A192895(n) = sumdiv(n, d, hammingweight(d)*(-1)^(d==n));
isA257691(n) = (A192895(n) <= 0);
n=i=0; while(i < 10000, n++; if(isA257691(n), i++; write("b257691.txt", i, " ", n))); \\ Charles R Greathouse IV, Feb 07 2013

A325559 Numbers n such that for any divisor d of n, and some integer k, A048720(d,k) = n only for trivial cases d=1 and d=n.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 97, 101, 103, 107, 109, 113, 115, 117, 121, 127, 131, 137, 139, 143, 145, 149, 151, 157, 163, 167, 169, 171, 173, 179, 181, 185, 191, 193, 197, 199, 203, 205, 209, 211, 213, 223, 227, 229, 233

Offset: 1

Antti Karttunen, May 11 2019

nonn

These are numbers n such that there are only two divisor pairs (d, n/d) [namely, the trivial pairs (1, n) and (n, 1)] that satisfy the condition that when their binary expansions are converted to (0,1)-polynomials (e.g., 13=1101[2] encodes X^3 + X^2 + 1), then their product is the (0,1)-polynomial similarly converted from n, when the multiplication is done over field GF(2).

Differs from A206074 for the first time at n=173, where a(173) = 555, a value missing from A206074, while the first three terms of A206074 not present in this sequence are k = 689, 781 and 913, for all of which A325560(k) = 3, not 2.

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

Cf. A048720, A206074.
Positions of 2's in A325560, positions of 1's in A325563 (after the initial 1), fixed points of A325643 (after the initial 1).
Some subsequences: A257688 (after its initial 1), A325386 (the remaining terms).

A325560(n) = { my(p = Pol(binary(n))*Mod(1, 2)); sumdiv(n,d,my(q = Pol(binary(d))*Mod(1, 2)); !(p%q)); };
isA325559(n) = (2 == A325560(n));

A257689 Numbers that are either ludic or prime.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 115, 119, 121, 127, 131, 137, 139, 143, 149, 151, 157, 161, 163, 167, 173, 175, 179, 181, 191, 193, 197, 199, 209, 211, 221, 223, 227, 229, 233, 235, 239, 241, 247, 251, 257, 263, 265

Offset: 1

Antti Karttunen, May 07 2015

nonn

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

Union of primes (A000040) and ludic numbers (A003309).
Cf. A192506 (complement, neither ludic nor prime), A192503 (ludic and prime), A192504 (ludic and nonprime), A192505 (nonludic and prime).
Differs from A206074(n-1), A186891(n) and A257688(n) for the first time at n=19, where a(19) = 59, while A206074(18) = A186891(19) = A257688(19) = 55, a term missing from here.
Differs from A257691 for the first time at n=24, where a(24) = 77, while A257691(24) = 79.

a3309[nmax_] := a3309[nmax] = Module[{t = Range[2, nmax], k, r = {1}}, While[Length[t] > 0, k = First[t]; AppendTo[r, k]; t = Drop[t, {1, -1, k}]]; r];
ludicQ[n_, nmax_] /; 1 <= n <= nmax := MemberQ[a3309[nmax], n];
terms = 1000;
f[nmax_] := f[nmax] = Select[Range[nmax], ludicQ[#, nmax] || PrimeQ[#]&] // PadRight[#, terms]&;
f[nmax = terms];
f[nmax = 2 nmax];
While[f[nmax] != f[nmax/2], nmax = 2 nmax];
seq = f[nmax] (* Jean-François Alcover, Dec 10 2021, after Ray Chandler in A003309 *)

A260428 Composite numbers whose binary representations encode a polynomial (with coefficients 0 or 1) which is irreducible over Q, but reducible over GF(2).

Original entry on oeis.org

69, 77, 81, 121, 169, 205, 209, 261, 265, 275, 289, 295, 305, 321, 323, 327, 329, 339, 377, 405, 407, 437, 453, 473, 475, 481, 493, 517, 533, 551, 553, 559, 565, 575, 581, 583, 595, 625, 649, 667, 671, 689, 703, 707, 737, 747, 749, 755, 763, 767, 779, 781, 785, 805, 815, 833, 835, 851, 855, 861, 869, 893, 905

Offset: 1

Antti Karttunen, Jul 26 2015

nonn

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

Intersection of A002808 and A260427.
Intersection of A091212 and A206074.
Intersection of A091242 and A206075.
Complement of A257688 in A206074.

f:= proc(n) local L,p,x;
  if isprime(n) then return false fi;
  L:= convert(n,base,2);
  p:= add(L[i]*x^(i-1),i=1..nops(L));
  irreduc(p) and not (Irreduc(p) mod 2);
end proc:
select(f, [$2..10000]); # Robert Israel, Jul 27 2015

okQ[n_] := CompositeQ[n] && Module[{id, pol, x}, id = IntegerDigits[n, 2] // Reverse; pol = id.x^Range[0, Length[id]-1]; IrreduciblePolynomialQ[pol] && !IrreduciblePolynomialQ[pol, Modulus -> 2]];
Select[Range[1000], okQ] (* Jean-François Alcover, Feb 06 2023 *)

isA260428(n) = (polisirreducible( Pol(binary(n)) ) && !polisirreducible(Pol(binary(n))*Mod(1, 2)) && !isprime(n));
n = 0; i = 0; while(n < 65537, n++; if(isA260428(n), i++; write("b260428.txt", i, " ", n)));

A325386 Numbers n such that for any divisor d of n and some k, A048720(d,k) = n only for trivial cases d=1 and d=n, despite that n is neither prime nor in A014580.

Original entry on oeis.org

69, 77, 81, 121, 169, 205, 209, 261, 265, 275, 289, 295, 305, 321, 323, 327, 329, 339, 377, 405, 407, 437, 453, 473, 475, 481, 493, 517, 533, 551, 553, 555, 559, 565, 575, 581, 583, 595, 625, 649, 667, 671, 699, 703, 707, 737, 747, 749, 755, 763, 767, 779, 785, 805, 815, 833, 835, 849, 851, 855, 861, 869, 871, 885, 893, 905, 923, 925

Offset: 1

Antti Karttunen, May 11 2019

nonn

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

Terms of A325559 not in A257688.
Subsequence of A005408 (odd numbers).
Cf. A014580, A325560.
Differs from A260428 for the first time at n=32, where a(32) = 555, a value missing from A260428.

A325560(n) = { my(p = Pol(binary(n))*Mod(1, 2)); sumdiv(n,d,my(q = Pol(binary(d))*Mod(1, 2)); !(p%q)); };
isA325386(n) = (!isprime(n) && !polisirreducible(Pol(binary(n))*Mod(1,2)) && (2 == A325560(n)));

cp's OEIS Frontend

A206074 n-th irreducible polynomial over Q (with coefficients 0 or 1) evaluated at x=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A091206 Primes whose binary representation encodes a polynomial irreducible over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A091212 Composite numbers whose binary representation encodes a polynomial reducible over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A257691 Numbers that are not A000120-abundant.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A325559 Numbers n such that for any divisor d of n, and some integer k, A048720(d,k) = n only for trivial cases d=1 and d=n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A257689 Numbers that are either ludic or prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A260428 Composite numbers whose binary representations encode a polynomial (with coefficients 0 or 1) which is irreducible over Q, but reducible over GF(2).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A325386 Numbers n such that for any divisor d of n and some k, A048720(d,k) = n only for trivial cases d=1 and d=n, despite that n is neither prime nor in A014580.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI