A235040 -id:A235040 - 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

A061858 Differences between the ordinary multiplication table A004247 and the carryless multiplication table for GF(2)[X] polynomials A048720, i.e., the effect of the carry bits in binary multiplication.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 0, 0, 0, 0, 12, 0, 8, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 16, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 24, 0, 0, 0

Offset: 0

Antti Karttunen, May 11 2001

			From _Peter Munn_, Jan 28 2021: (Start)
The top left 12 X 12 corner of the table:
      |  0   1   2   3   4   5   6   7   8   9  10  11
------+------------------------------------------------
   0  |  0   0   0   0   0   0   0   0   0   0   0   0
   1  |  0   0   0   0   0   0   0   0   0   0   0   0
   2  |  0   0   0   0   0   0   0   0   0   0   0   0
   3  |  0   0   0   4   0   0   8  12   0   0   0   4
   4  |  0   0   0   0   0   0   0   0   0   0   0   0
   5  |  0   0   0   0   0   8   0   8   0   0  16  16
   6  |  0   0   0   8   0   0  16  24   0   0   0   8
   7  |  0   0   0  12   0   8  24  28   0   0  16  28
   8  |  0   0   0   0   0   0   0   0   0   0   0   0
   9  |  0   0   0   0   0   0   0   0   0  16   0  16
  10  |  0   0   0   0   0  16   0  16   0   0  32  32
  11  |  0   0   0   4   0  16   8  28   0  16  32  52
(End)

"Zoomed in" variant: A061859.
Rows/columns 3, 5 and 7 are given by A048728, A048729, A048730.
Main diagonal divided by 4: A213673.
Numbers that generate no carries when multiplied in binary by 11_2: A003714, by 101_2: A048716, by 1001_2: A115845, by 10001_2: A115847, by 100001_2: A114086.
Other sequences related to the presence/absence of a carry in binary multiplication: A116361, A235034, A235040, A236378, A266195, A289726.

a(n) = A004247(n) - A048720(n).

A235034 Numbers whose prime divisors, when multiplied together without carry-bits (as encodings of GF(2)[X]-polynomials, with A048720), produce the original number; numbers for which A234741(n) = n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 34, 37, 38, 40, 41, 43, 44, 46, 47, 48, 51, 52, 53, 56, 58, 59, 60, 61, 62, 64, 67, 68, 71, 73, 74, 76, 79, 80, 82, 83, 85, 86, 88, 89, 92, 94, 95, 96, 97, 101

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

If n is present, then 2n is present also, as shifting binary representation left never produces any carries.

			All primes occur in this sequence as no multiplication -> no need to add any intermediate products -> no carry bits produced.
Composite numbers like 15 are also present, as 15 = 3*5, and when these factors (with binary representations '11' and '101') are multiplied as:
   101
  1010
  ----
  1111 = 15
we see that the intermediate products 1*5 and 2*5 can be added together without producing any carry-bits (as they have no 1-bits in the same columns/bit-positions), so A048720(3,5) = 3*5 and thus 15 is included in this sequence.

Gives the positions of zeros in A236378, i.e., n such that A234741(n) = n.
Intersection with A235035 gives A235032.
Other subsequences: A000040 (A091206 and also A091209), A045544 (A004729), A093641, A235040 (gives odd composites in this sequence), A235050, A235490.
Cf. A048720, A061858, A234741.

A235039 Odd numbers which are factored to the same set of primes in Z as to the irreducible polynomials in GF(2)[X]; odd terms of A235036.

Original entry on oeis.org

1, 111, 123, 219, 411, 511, 959, 1983, 2031, 3099, 3459, 3579, 4847, 5371, 6159, 7023, 7131, 7141, 7231, 7899, 7913, 8071, 8079, 9179, 12387, 12783, 13289, 15843, 26223, 27771, 28453, 28903, 31529, 31539, 39007, 45419, 49251, 49659, 51087, 53677, 56137, 57219, 61923

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

These are odd nonprime numbers in A235032. After a(0)=1, the odd composite numbers in A235032.

The terms a(1) - a(42) are all semiprimes. Presumably terms with a larger number of prime factors also exist.

			111 = 3*37. When these two prime factors (both terms of A091206), with binary representations '11' and '100101', are multiplied as:
   100101
  1001010
  -------
  1101111 = 111 in decimal
we see that the intermediate products 1*37 and 2*37 can be added together without producing any carry-bits (as they have no 1-bits in the same columns/bit-positions), so A048720(3,37) = 3*37 and thus 111 is included in this sequence.
Note that unlike in A235040, 15 = 3*5 is not included in this sequence, because its prime factor 5 is not in A091206, but instead decomposes further as A048720(3,3).

A subsequence of A235032, A235036, A235040 and A235045.

A235050 Squarefree numbers such that none of their prime factors share common 1-bits in the same bit-position of their binary representations.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 11, 13, 17, 19, 23, 26, 29, 31, 34, 37, 41, 43, 47, 53, 58, 59, 61, 67, 71, 73, 74, 79, 82, 83, 89, 97, 101, 103, 106, 107, 109, 113, 122, 127, 131, 137, 139, 146, 149, 151, 157, 163, 167, 173, 178, 179, 181, 191, 193, 194, 197, 199, 202, 211, 218, 223, 226, 227, 229, 233, 239, 241, 251, 257

Offset: 1

Antti Karttunen, Jan 22 2014

a(1)=1 is included on the grounds that it has no prime factors at all, thus no conflicting 1-bits.
After a(1)=1 all n such that A001414(n) = A072593(n), or equally, A001414(n) = A072594(n).
Union of noncomposites (A008578) and semiprimes of the form 2*A002144 (cf. also A235490).

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

Subsequences: A000040, A235490.
Subsequence of A005117.
Cf. also A001414, A072593, A072594, A235040.

A365451 Odd composite numbers k such that A349494(k) = A000120(k).

Original entry on oeis.org

15, 27, 51, 63, 85, 95, 111, 119, 123, 125, 187, 219, 221, 255, 335, 365, 411, 447, 485, 511, 629, 655, 685, 697, 771, 831, 879, 959, 965, 1011, 1139, 1241, 1285, 1405, 1535, 1563, 1649, 1731, 1779, 1791, 1799, 1923, 1983, 2005, 2019, 2031, 2043, 2045, 2227, 2605, 2735, 2815, 2827, 2885, 3099

Offset: 1

Robert Israel, Sep 03 2023

Odd composite numbers k such that for all divisors d of k, A000120(d) * A000120(k/d) = A000120(k).

			a(4) = 63 is a term because 63 = 3 * 21 = 7 * 9 with A000120(63) = 6, A000120(3) * A000120(21) = 2 * 3 = 6 and A000120(7) * A000120(9) = 3 * 2 = 6.

Robert Israel, Table of n, a(n) for n = 1..7500

Cf. A000120, A349494.
Includes x^3 for x in A019434.
Includes all members of A235040 except 1.

g:= proc(n) convert(convert(n, base, 2), `+`) end proc:
filter:= proc(n) local d, t;
  if isprime(n) then return false fi;
  t:= g(n);
  andmap(d -> g(d) * g(n/d) = t, select(d -> d^2 <= n, numtheory:-divisors(n)))
end proc:
select(filter, [seq(i,i=3..10000,2)]);

q[n_] := CompositeQ[n] && Ordering[(d = DigitCount[Divisors[n], 2, 1])*Reverse[d], -1][[1]] == Length[d]; Select[Range[3, 3100, 2], q] (* Amiram Eldar, Sep 04 2023 *)

is(n) = if(n%2 != 1 || isprime(n), return(0)); my(h=hammingweight(n), d=divisors(n), i); for(i=2,(#d+1)\2, if(hammingweight(d[i]) * hammingweight(d[#d+1-i]) > h, return(0))); n > 1 \\ David A. Corneth, Sep 04 2023

A365473 Odd semiprimes pq such that A000120(p)A000120(q) = A000120(p*q).

Original entry on oeis.org

15, 51, 85, 95, 111, 119, 123, 187, 219, 221, 335, 365, 411, 447, 485, 511, 629, 655, 685, 697, 771, 831, 879, 959, 965, 1011, 1139, 1241, 1285, 1405, 1535, 1563, 1649, 1731, 1779, 1799, 1923, 1983, 2005, 2019, 2031, 2045, 2227, 2605, 2735, 2815, 2827, 2885, 3099, 3183, 3279, 3281, 3291, 3327

Offset: 1

Robert Israel, Sep 04 2023

If p is an odd prime < 2^m and A365475(m) exists, then p * A365475(m) is a term. Thus, if A365475 is infinite, this sequence contains infinitely many multiples of every odd prime.

			a(3) = 85 is a term because 85 = 5 * 17 is an odd semiprime with A000120(5) * A000120(17) = 2 * 2 = 4 = A000120(85).

Robert Israel, Table of n, a(n) for n = 1..7230

Cf. A000120, A365475.

Intersection of A001358 and A235040, and intersection of A001358 and A365451.

g:= proc(n) convert(convert(n,base,2),`+`) end proc:
N:= 10^4: # for terms <= N
S:= NULL: p:= 2:
while 3*p <= N do
  p:= nextprime(p);
  t:= g(p);
  q:= 2:
  do
    q:= nextprime(q);
    if q = p or q*p > N then break fi;
    if g(q)*t = g(p*q) then S:= S, p*q fi;
od od:
sort([S]);

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

A061858 Differences between the ordinary multiplication table A004247 and the carryless multiplication table for GF(2)[X] polynomials A048720, i.e., the effect of the carry bits in binary multiplication.

Views

Author

Keywords

Examples

Crossrefs

Formula

A235034 Numbers whose prime divisors, when multiplied together without carry-bits (as encodings of GF(2)[X]-polynomials, with A048720), produce the original number; numbers for which A234741(n) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A235039 Odd numbers which are factored to the same set of primes in Z as to the irreducible polynomials in GF(2)[X]; odd terms of A235036.

Views

Author

Keywords

Comments

Examples

Crossrefs

A235050 Squarefree numbers such that none of their prime factors share common 1-bits in the same bit-position of their binary representations.

Views

Author

Keywords

Comments

Links

Crossrefs

A365451 Odd composite numbers k such that A349494(k) = A000120(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A365473 Odd semiprimes p*q such that A000120(p)*A000120(q) = A000120(p*q).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A365473 Odd semiprimes pq such that A000120(p)A000120(q) = A000120(p*q).