A236851 -id:A236851 - cp's OEIS frontend

A234742 Product of the binary encodings of the irreducible factors (with multiplicity) of the polynomial over GF(2) whose encoding is n.

0, 1, 2, 3, 4, 9, 6, 7, 8, 21, 18, 11, 12, 13, 14, 27, 16, 81, 42, 19, 36, 49, 22, 39, 24, 25, 26, 63, 28, 33, 54, 31, 32, 93, 162, 91, 84, 37, 38, 99, 72, 41, 98, 75, 44, 189, 78, 47, 48, 77, 50, 243, 52, 57, 126, 55, 56, 117, 66, 59, 108, 61, 62, 147, 64, 441

Offset: 0

Antti Karttunen, Jan 22 2014

"Product" refers to the ordinary multiplication of integers.
Differs from A235042 and A236837 for the first time at n=25, where a(n)=25, while A235042(25)=5 and A236837(25)=0. Thus A234741(A234742(n)) = n up to n=24.
a(n) >= n. [All terms of the table A061858 are nonnegative as the product of multiplying two numbers with carries is never less than when multiplying them without carries.]
Specifically, for all n, a(A091209(n)) > A091209(n).
a(A091209(n)) is always composite and, by the above inequality, larger than A091209(n), which implies that none of the terms of A091209 occur in this sequence. Cf. also A236844.
Starting with various terms (primes) in A235033 and iterating the map A234742, we get 5 -> 9 -> 21 -> 49 -> 77 -> 177 -> 333 = a(333).
Another example: 17 -> 81 -> 169 -> 309 -> 721 = a(721).
Does every chain of such iterations eventually reach a fixed point? (One of the terms of A235035.) Or do some of them manage to avoid such "traps" indefinitely? (Note how the terms of A235035 seem to get rarer, but only rather slowly.)
Starting from 23, we get the sequence: 23, 39, 99, 279, 775, 1271, 3003, 26411, 45059, ... which reaches its fixed point, 3643749709604450870616156947649219, after 55 iterations. - M. F. Hasler, Feb 18 2014. [This is now sequence A244323. See also A260729, A260735 and A260441.] - Antti Karttunen, Aug 05 2015
Note also that when coming backwards from some term of such a chain by iterating A234741, we may not necessarily end at the same term we started from.

			3 has binary representation '11', which encodes the polynomial X + 1, which is irreducible in GF(2)[X], so the result is just a(3)=3.
5 has binary representation '101' which encodes the polynomial X^2 + 1, which is reducible in the polynomial ring GF(2)[X], factoring as (X+1)(X+1), i.e., 5 = A048720(3,3), as 3 ('11' in binary) encodes the polynomial (X+1), irreducible in GF(2)[X]. 3*3 = 9, thus a(5)=9.
9 has binary representation '1001', which encodes the polynomial X^3 + 1, which factors (in GF(2)[X]!) as (X+1)(X^2+X+1), i.e., 9 = A048720(3,7) (7, '111' in binary, encodes the other factor polynomial X^2+X+1). 3*7 = 21, thus a(9)=21.
25 has binary representation '11001', which encodes the polynomial X^4 + X^3 + 1, which is irreducible in GF(2)[X], so the result is just a(25)=25.

Antti Karttunen, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

A235035 gives the k for which a(k)=k.
A236853(n) gives the number of times n occurs in this sequence.
A236842 gives the same sequence sorted and with duplicates removed, A236844 gives the numbers that do not occur here, A236845 gives numbers that occur more than once, A236846 the least inverse and A236847 the greatest inverse. A236850 gives such k that a(k) = A236837(k).
Cf. A014580, A048720, A234741, A236379, A236837, A236851 & A236852, A115857, A115872.
Cf. also A260712, A260713, A260716 and A244323, A260729, A260735, A260441 (iterations starting from various terms of A236844).

A234742(n)=factorback(subst(lift(factor(Mod(1,2)*Pol(binary(n)))),x,2)) \\ M. F. Hasler, Feb 18 2014, corrected Andrew Howroyd, Aug 01 2018

To compute a(n): factor the polynomial over GF(2) encoded by n, into its irreducible factors; in other words, find a unique multiset of terms i, j, ..., k (not necessarily distinct) from A014580 for which i x j x ... x k = n, where x stands for the carryless multiplication A048720. Then a(n) = i*j*...*k is the product of those terms with ordinary multiplication. Because of the effect of the carry-bits in the latter, the result is always greater than or equal to n, so we have a(n) >= n for all n.
a(2n) = 2*a(n).
a(A235035(n)) = A235035(n).
A236379(n) = a(n) - n.
For all n, a(n) >= A236837(n).

A091214 Composite numbers whose binary representation encodes a polynomial irreducible over GF(2).

Original entry on oeis.org

25, 55, 87, 91, 115, 117, 143, 145, 171, 185, 203, 213, 247, 253, 285, 299, 301, 319, 333, 351, 355, 357, 361, 369, 375, 391, 395, 415, 425, 445, 451, 471, 477, 501, 505, 515, 529, 535, 539, 545, 623, 637, 665, 675, 687, 695, 721, 731, 789, 799, 803, 817

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

Intersection of A002808 and A014580.
Subsequence of A235033, A236834 and A236838.
Left inverse: A235044.
Cf. A091206 (Primes whose binary expansion encodes a polynomial irreducible over GF(2)), A091209 (Primes that encode a polynomial reducible over GF(2)), A091212 (Composite, and reducible over GF(2)).
Cf. A091215, A235027, A235046, A236841, A236845, A236850, A236851, A236861.
Cf. also A235041-A235042.

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 && ! PrimeQ@ n]; Select[ Range@ 840, fQ] (* Robert G. Wilson v, Aug 12 2011 *)

isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
isA091214(n) = (!isprime(n) && isA014580(n));
n = 0; i = 0; while(n < 2^20, n++; if(isA091214(n), i++; write("b091214.txt", i, " ", n)));
\\ The b-file was computed with this program. Antti Karttunen, May 17 2015

Other identities. For all n >= 1:
A235044(a(n)) = n. [A235044 works as a left inverse of this sequence.]
a(n) = A014580(A091215(n)). - Antti Karttunen, May 17 2015

Entry revised and name corrected by Antti Karttunen, May 17 2015

A236850 After 0 and 1, numbers n whose binary representation encodes such a polynomial over GF(2) that all its irreducible factors (their binary codes) are primes in N (terms of A091206).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 1

Antti Karttunen, Feb 02 2014

nonn

To determine whether n belongs to this sequence: first find a unique multiset of terms i, j, ..., k (terms not necessarily distinct) from A014580 for which i x j x ... x k = n, where x stands for the carryless multiplication (A048720). If and only if NONE of those i, j, ..., k is a composite (in other words, if all are primes in N, i.e. terms of A091206), then n is a member.
Equally, numbers which can be constructed as p x q x ... x r, where p, q, ..., r are terms of A091206. (Compare to the definition of A236860.)
Also fixed points of A236851(n). Proof: if k is a term of this sequence, the operation described in A236851 reduces to an identity operation. On the other hand, if k is not a term of this sequence, then it contains at least one irreducible GF(2)[X]-factor which is a composite in N, which is thus "broken" by A236851 to two or more separate GF(2)[X]-factors (either irreducible or not), and because the original factor was irreducible, and GF(2)[X] is a unique factorization domain, the new product computed over the new set of factors (with one or more "broken" pieces) cannot be equal to the original k. (Compare this to how primes are "broken" in a similar way in A235027, also A235145.)
Also by similar to above reasoning, positions where A234742(n) = A236837(n).
This is a subsequence of A236841, from which this differs for the first time at n=43, where A236841(43)=43, while from here 43 is missing, and a(43)=44.

			25 is the first term not included, as although it encodes an irreducible polynomial in GF(2)[X]: X^4 + X^3 + 1 (binary code 11001), it is composite in Z, thus not in A091206, but in A091214.
27 is included, as it factors as 5 x 7, and both factors are present in A091206.
37 is included, as it is a member of A091206 (irreducible in both Z and GF(2)[X]).
43 is NOT included because, even although it is a prime in Z, it factors as 3 x 25 in GF(2)[X]. Of these, only 3 is a term of A091206, while 25 belongs to A091214, as it further divides to 5*5.

Antti Karttunen, Table of n, a(n) for n = 1..14166
Index entries for sequences operating on polynomials over GF(2)

Subsequence of A236841.
Subsequence: A235032.
Cf. A236860, A236851, A234741, A234742, A236851.

A236380 Difference between value of n, when remultiplied "upward", from GF(2)[X] to N, and when remultiplied "downward", from N to GF(2)[X]: a(n) = A234742(n) - A234741(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 0, 0, 0, 16, 8, 0, 0, 0, 0, 12, 0, 64, 32, 0, 16, 40, 0, 16, 0, 8, 0, 48, 0, 4, 24, 0, 0, 64, 128, 64, 64, 0, 0, 76, 32, 0, 80, 32, 0, 172, 32, 0, 0, 56, 16, 192, 0, 4, 96, 16, 0, 64, 8, 0, 48, 0, 0, 120, 0, 384, 128, 0, 256, 64, 128, 112, 128, 0, 0, 300, 0, 128, 152, 96, 64, 152, 0, 148, 160, 644, 64

Offset: 0

Antti Karttunen, Jan 24 2014

nonn

All terms are divisible by 4.

a(n) = 0 iff both A236378(n) and A236379(n) are zero, or in other words, iff A234741(n)=n and A234742(n)=n, which means that A235032 gives all such n, that a(n) = 0.

Antti Karttunen, Table of n, a(n) for n = 0..8191

A235032 gives the positions of zeros, A235033 the positions of nonzeros.

Cf. also A234741, A234742, A236378, A236379, A236851, A061858.

a(n) = A234742(n) - A234741(n).

a(n) = A236378(n) + A236379(n).

A236852 Remultiply n first "downward", from N to GF(2)[X], and then remultiply that result back "upward", from GF(2)[X] to N: a(n) = A234742(A234741(n)).

Original entry on oeis.org

0, 1, 2, 3, 4, 9, 6, 7, 8, 9, 18, 11, 12, 13, 14, 27, 16, 81, 18, 19, 36, 21, 22, 39, 24, 81, 26, 27, 28, 33, 54, 31, 32, 33, 162, 63, 36, 37, 38, 39, 72, 41, 42, 75, 44, 81, 78, 47, 48, 49, 162, 243, 52, 57, 54, 99, 56, 57, 66, 59, 108, 61, 62, 63, 64, 117, 66, 67, 324

Offset: 0

Antti Karttunen, Feb 02 2014

This sequence appears to be completely multiplicative with a(p) = A234742(p) although neither A234741 or A234742 are even multiplicative. Terms tested up to n = 10^7. - Andrew Howroyd, Aug 01 2018

Yes, this is true. Consider for example n = p*q*r*r, where p, q, r are primes in N. Then A234741(n) = p1 x q1 x q2 x q3 x r1 x r2 x r1 x r2, where p1, q1, r1, ..., are the irreducible factors of p, q, r when factored over GF(2), and x stands for multiplication in ring GF(2)[X] (A048720). [Note that these irreducible factors are not necessarily primes in N, except p1 (= p), which must be a term of A091206. Also, A234741(p) = p for any prime p.] Next, a(n) = A234742(p1 x q1 x q2 x q3 x r1 x r2 x r1 x r2) = p1 * q1 * q2 * q3 * r1 * r2 * r1 * r2, which can be obtained also as a(p)*a(q)*a(r)*a(r), thus proving the multiplicativity. - Antti Karttunen, Aug 02 2018

			From _Antti Karttunen_, Aug 02 2018: (Start)
For n = 3, we have A234741(3) = 3 = 11 in binary, which encodes a (0,1)-polynomial x+1, which is irreducible over GF(2) thus A234742(3) = 3 and  a(3) = 3.
For n = 5, we have A234741(5) = 5 = 101 in binary, which encodes a (0,1)-polynomial x^2 + 1, which factorizes as (x+1)(x+1) when factored over GF(2), that is 5 = A048720(3,3), thus it follows that A234742(5) = 3*3 = 9, and a(5) = 9.
For n = 9 = 3*3, we have A234741(9) = A048720(3,3) = 5, and A234742(5) = 9 as shown above. Also by multiplicativity, we have a(3*3) = a(3)*a(3) = 3*3 = 9.
(End)

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

Fixed points: A236860.

Cf. A048720, A234741, A234742, A236851, A236836-A236837, A236846-A236847.

(define (A236852 n) (A234742 (A234741 n)))

a(n) = A234742(A234741(n)).

Keyword mult added after Andrew Howroyd's observation. - Antti Karttunen, Aug 02 2018

cp's OEIS Frontend

A234742 Product of the binary encodings of the irreducible factors (with multiplicity) of the polynomial over GF(2) whose encoding is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A091214 Composite numbers whose binary representation encodes a polynomial irreducible over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A236850 After 0 and 1, numbers n whose binary representation encodes such a polynomial over GF(2) that all its irreducible factors (their binary codes) are primes in N (terms of A091206).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A236380 Difference between value of n, when remultiplied "upward", from GF(2)[X] to N, and when remultiplied "downward", from N to GF(2)[X]: a(n) = A234742(n) - A234741(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A236852 Remultiply n first "downward", from N to GF(2)[X], and then remultiply that result back "upward", from GF(2)[X] to N: a(n) = A234742(A234741(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

Extensions