A236852 -id:A236852 - 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).

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

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, 17, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 51, 44, 45, 46, 47, 48, 49, 34, 51, 52, 53, 54, 39, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67

Offset: 0

Antti Karttunen, Feb 02 2014

nonn

			5 ('101' in binary) = 3 x 3 (3 = '11' in binary). 3 is in A091206, so it stays intact, and 3 x 3 = 5, thus a(5)=5.
25 ('11001' in binary) = 25 (25 is irreducible in GF(2)[X]). However, it divides as 5*5 in Z, so the result is 5 x 5 = 17, thus a(25)=17, 25 being the least n which is not fixed by this function.
43 ('101011' in binary) = 3 x 25, of which the latter factor divides to 5*5, thus the result is 3 x 5 x 5 = 3 x 17 = 15 x 5 = 51.

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

A236850 gives the fixed points.

Cf. A234741, A234742, A236380, A236852, A236836-A236837, A236846-A236847.

(define (A236851 n) (A234741 (A234742 n)))

a(n) = A234741(A234742(n)).
To compute a(n): factor n as a polynomial over GF(2) (where n is mapped to such polynomials via the binary representation of n), that is, find first a unique multiset of terms i, j, ..., k from A014580 for which i x j x ... x k = n, where x stands for the carryless multiplication (A048720). Then divide from those i, j, ..., k the ones that are in A091214 (composite integers in N) to their constituent prime factors (in N), and multiply all back together (including the factors that are in A091206 and thus not changed) with the carryless multiplication (A048720).
Compare this to how primes are "broken" in a similar way in A235027 (cf. also A235145).

A236860 After 0 and 1, numbers n all of whose prime divisors encode an irreducible polynomial over GF(2) (are terms of A091206).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 18, 19, 21, 22, 24, 26, 27, 28, 31, 32, 33, 36, 37, 38, 39, 41, 42, 44, 47, 48, 49, 52, 54, 56, 57, 59, 61, 62, 63, 64, 66, 67, 72, 73, 74, 76, 77, 78, 81, 82, 84, 88, 91, 93, 94, 96, 97, 98, 99, 103, 104, 108, 109

Offset: 1

Antti Karttunen, Mar 08 2014

nonn

After 0 and 1, positive integers which are products of p * q * ... * r, where p, q, ..., r are terms of A091206.
Also fixed points of A236852(n). Proof: if k is a term of this sequence, the operation described in A236852 reduces to an identity operation. On the other hand, if k is not a term of this sequence, then it has at least one prime divisor which is reducible in polynomial ring GF(2)[X], which is thus "broken" by A236852 (A234742) to two or more separate factors (either prime or not), and because the original factor was prime, and N 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.)
Note: This sequence is not equal to all n for which A234741(n) = A236846(n). The first counterexample occurs at a(325) = 741 (= 3*13*19) for which we have: A236846(741) = 281 (= 3 x 247 = 3 x (13*19)) while A234741(741) = 329 (= 3 x 13 x 19). Contrast this with the behavior of the "dual sequence" A236850, where the corresponding property holds.

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

Complement: A236848.
Subsequence of A236842.
Fixed points of A236852.
Cf. A091206, A236850.

isp(p) = polisirreducible( Mod(1, 2) * Pol(binary(p))); \\ A091206
isok(n) = if ((n==0), 1 , my(f=factor(n)); prod(k=1, #f~, isp(f[k,1])) != 0); \\ Michel Marcus, Dec 22 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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Scheme

Formula

A236860 After 0 and 1, numbers n all of whose prime divisors encode an irreducible polynomial over GF(2) (are terms of A091206).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI