A325559 -id:A325559 - cp's OEIS frontend

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375

Offset: 1

David Petry (petry(AT)accessone.com)

nonn

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.
The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014
2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021
For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

			x^4 + x^3 + 1 -> 16+8+1 = 25. Or, x^4 + x^3 + 1 -> 11001 (binary) = 25 (decimal).

A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (first 1377 terms from T. D. Noe)
Index entries for sequences operating on GF(2)[X]-polynomials

Written in binary: A058943.
Number of degree-n irreducible polynomials: A001037, see also A000031.
Multiplication table: A048720.
Characteristic function: A091225. Inverse: A091227. a(n) = A091202(A000040(n)). Almost complement of A091242. Union of A091206 & A091214 and also of A091250 & A091252. First differences: A091223. Apart from a(1) and a(2), a subsequence of A092246 and hence A000069.
Table of irreducible factors of n: A256170.
Irreducible polynomials satisfying particular conditions: A071642, A132447, A132449, A132453, A162570.
Factorization sentinel: A278239.
Sequences analyzing the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the corresponding integer: A234741, A234742, A235032, A235033, A235034, A235035, A235040, A236850, A325386, A325559, A325560, A325563, A325641, A325642, A325643.
Factorization-preserving isomorphisms: A091203, A091204, A235041, A235042.
See A115871 for sequences related to cross-domain congruences.
Functions based on the irreducibles: A305421, A305422.

fQ[n_] := Block[{ply = Plus @@ (Reverse@ IntegerDigits[n, 2] x^Range[0, Floor@ Log2@ n])}, ply == Factor[ply, Modulus -> 2] && n != 2^Floor@ Log2@ n]; fQ[2] = True; Select[ Range@ 378, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
Reap[Do[If[IrreduciblePolynomialQ[IntegerDigits[n, 2] . x^Reverse[Range[0, Floor[Log[2, n]]]], Modulus -> 2], Sow[n]], {n, 2, 1000}]][[2, 1]] (* Jean-François Alcover, Nov 21 2016 *)

is(n)=polisirreducible(Pol(binary(n))*Mod(1,2)) \\ Charles R Greathouse IV, Mar 22 2013

A325563 a(1) = 1; for n > 1, a(n) is the largest proper divisor d of n such that A048720(d,k) = n for some k.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, May 11 2019

nonn

For n > 1, a(n) is the largest proper divisor d of n for which it holds that when the binary expansion of d is converted to a (0,1)-polynomial (e.g., 13=1101[2] encodes X^3 + X^2 + 1), then that polynomial is a divisor of (0,1)-polynomial similarly converted from n, when the polynomial division is done over field GF(2). See the example.

			For n = 39 = 3*13, A032742(39) = 13, but 13 is not the answer because X^3 + X^2 + 1 does not divide X^5 + X^2 + X + 1 (39 is "100111" in binary) over GF(2). However, the next smaller divisor 3 works because X^5 + X^2 + X + 1 = (X^1 + 1)(X^4 + X^3 + X^2 + 1) when multiplication is done over GF(2). Note that 39 = A048720(3,29), where 29 is "11101" in binary. Thus a(39) = 3.

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

Cf. A032742, A048720, A325560, A325564, A325567, A325643.

Cf. A325559 (positions of ones, after the initial 1).

A325563(n) = if(1==n,n, my(p = Pol(binary(n))*Mod(1, 2)); fordiv(n,d,if((d>1),my(q = Pol(binary(n/d))*Mod(1, 2)); if(0==(p%q), return(n/d)))));

A048720(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A325563(n) = if(1==n,n,fordiv(n,d,if((d>1),for(t=1,n,if(A048720(n/d,t)==n,return(n/d)))))); \\ (Slow)

For all n, a(n) <= A032742(n).

A325643 a(1) = 1; for n > 1, a(n) is the least divisor d > 1 of n such that A048720(d,k) = n for some k.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, May 11 2019

nonn

For n > 1, a(n) is the least divisor d of n that is larger than 1 and for which it holds that when the binary expansion of d is converted to a (0,1)-polynomial (e.g., 13=1101[2] encodes X^3 + X^2 + 1), then that polynomial is a divisor of (0,1)-polynomial similarly converted from n, when the division is done over GF(2). See the example.

			For n = 21 = 3*7, 3 is not the answer because X^1 + 1 does not divide X^4 + X^2 + 1 (21 is "10101" in binary) over GF(2). However, the next larger divisor 7 works because X^4 + X^2 + 1 = (X^2 + X^1 + 1)^2 when multiplication is done over GF(2) (note that A048720(7,7) = 21). Thus a(21) = 7.

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

Cf. A048720, A325559 (fixed points after 1), A325563, A325641, A325642.

A325643(n) = if(1==n,n, my(p = Pol(binary(n))*Mod(1, 2)); fordiv(n,d,if((d>1),my(q = Pol(binary(d))*Mod(1, 2)); if(0==(p%q), return(d)))));

a(2n) = 2.
For all n >= 1, a(A325559(n)) = A325559(n).
For all n >= 1, n = a(n) * A325641(n) = A048720(a(n), A325642(n)).

A325560 a(n) is the number of divisors d of n such that A048720(d,k) = n for some k.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 3, 4, 2, 8, 2, 4, 4, 6, 2, 8, 2, 6, 3, 4, 3, 9, 2, 4, 3, 8, 2, 6, 2, 6, 6, 4, 2, 10, 3, 4, 4, 6, 2, 8, 2, 8, 3, 4, 2, 12, 2, 4, 6, 7, 3, 6, 2, 6, 2, 6, 2, 12, 2, 4, 5, 6, 2, 6, 2, 10, 2, 4, 2, 9, 4, 4, 2, 8, 2, 12, 2, 6, 3, 4, 4, 12, 2, 6, 4, 6, 2, 8, 2, 8, 5

Offset: 1

Antti Karttunen, May 11 2019

nonn

a(n) is the number of divisors d of n such that when the binary expansion of d is converted to a (0,1)-polynomial (e.g., 13=1101[2] encodes X^3 + X^2 + 1), that polynomial is a divisor of the (0,1)-polynomial similarly converted from n, when the polynomial division is done over field GF(2).

			39 = 3*13 has four divisors 1, 3, 13, 39, of which all other divisors except 13 are counted because we have A048720(1,39) = A048720(39,1) = A048720(3,29) = 39, but A048720(13,u) is not equal to 39 for any u, thus a(39) = 3. See also the example in A325563.

Cf. A000005, A048720, A091220, A325559 (positions of 2's), A325563, A325565.

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

For all n, A325565(n) <= a(n) <= min(A000005(n), A091220(n)).

A325641 a(1) = 1; for n > 1, a(n) = n/d for the least divisor d > 1 of n such that A048720(d,k) = n for some k.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, May 11 2019

nonn

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

Cf. A048720, A325642, A325643.

Cf. A325559 (positions of ones after the initial 1).

A325641(n) = if(1==n,n, my(p = Pol(binary(n))*Mod(1, 2)); fordiv(n,d,if((d>1),my(q = Pol(binary(d))*Mod(1, 2)); if(0==(p%q), return(n/d)))));

a(n) = n / A325643(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

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A325563 a(1) = 1; for n > 1, a(n) is the largest proper divisor d of n such that A048720(d,k) = n for some k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A325643 a(1) = 1; for n > 1, a(n) is the least divisor d > 1 of n such that A048720(d,k) = n for some k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A325560 a(n) is the number of divisors d of n such that A048720(d,k) = n for some k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A325641 a(1) = 1; for n > 1, a(n) = n/d for the least divisor d > 1 of n such that A048720(d,k) = n for some k.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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