A236836 -id:A236836 - cp's OEIS frontend

A236834 Numbers that do not occur as results of "downward" remultiplication (N -> GF(2)[X]) of any number; numbers not present in A234741.

25, 50, 55, 87, 91, 100, 110, 115, 117, 133, 143, 145, 159, 171, 174, 182, 185, 200, 203, 213, 220, 230, 234, 237, 247, 249, 253, 266, 267, 279, 285, 286, 290, 299, 301, 318, 319, 321, 333, 339, 342, 345, 348, 351, 355, 357, 361, 364, 369, 370, 375, 385, 391, 395, 400

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

Numbers that do not occur in A234741 (A236841).
This is a subsequence of A236838, thus all terms are GF(2)[X]-multiples of some of the terms of A091214. (Cf. also A236844).
a(5)=91 is the first term that does not occur in A236849. On the other hand, A236849(4)=75, is the first term in the latter which does not occur here.

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

Complement: A236841. This sequence is a setwise difference of A236838 and A236839.
A091214 is a subsequence.
Positions of zeros in A236833, A236836, A236837 and A236861
Cf. also A236844, A234741, A236835.

A236837 The greatest inverse of A234741: a(n) = the largest k such that A234741(k) = n, and 0 if no such k exists.

Original entry on oeis.org

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, 0, 26, 63, 28, 33, 54, 31, 32, 93, 162, 91, 84, 37, 38, 99, 72, 41, 98, 43, 44, 189, 78, 47, 48, 77, 0, 243, 52, 57, 126, 0, 56, 117, 66, 59, 108, 61, 62, 147, 64, 441, 186, 67, 324, 121

Offset: 0

Antti Karttunen, Jan 31 2014

nonn

A234741(a(n)) = n, unless n is in A236834, in which case a(n)=0.
For all n, a(n) <= A234742(n). A236850 gives such k that a(k) = A234742(k).
If n is in A236835, a(n) > A236836(n), otherwise a(n) = A236836(n).
a(2^n) = 2^n.
a(2n) = 2*a(n).

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

A236834 gives the positions of zeros.
Differs from A235042 and A234742 for the first time at n=25, where a(25)=0 but A235042(25)=5 and A234742(25)=25.
Cf. A236836 (the least inverse of A234741).
Cf. also A236833, A236835, A234741, A236841, A236850.

A236846 Least inverse of A234742: a(n) = minimal k such that when it is remultiplied "upwards", from GF(2)[X] to N, the result is n, and 0 if no such k exists.

Original entry on oeis.org

0, 1, 2, 3, 4, 0, 6, 7, 8, 5, 0, 11, 12, 13, 14, 0, 16, 0, 10, 19, 0, 9, 22, 0, 24, 25, 26, 15, 28, 0, 0, 31, 32, 29, 0, 0, 20, 37, 38, 23, 0, 41, 18, 0, 44, 0, 0, 47, 48, 21, 50, 0, 52, 0, 30, 55, 56, 53, 0, 59, 0, 61, 62, 27, 64, 0, 58, 67, 0, 0, 0, 0, 40, 73, 74, 43, 76, 49, 46, 0, 0, 17, 82, 0, 36, 0, 0, 87, 88, 0, 0, 35

Offset: 0

Antti Karttunen, Jan 31 2014

nonn

Apart from zero, each term occurs at most once. 91 is the smallest positive integer not present in this sequence.

Note that in contrast to the reciprocal case, where A234742(n) >= A236837(n) for all n [the former sequence gives the absolute upper bound for the latter], here it is not guaranteed that A234741(n) <= a(n) whenever a(n) > 0. For example, a(25)=25 and A234741(25)=17, and 25-17 = 8. On the other hand, a(75)=43, but A234741(75)=51, and 43-51 = -8.

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

Differs from A236847 for the first time at n=91, where a(91)=35, while A236847(91)=91.
A236844 gives the positions of zeros.
Cf. A234742.
Cf. also A236836, A236837.

(define (A236846 n) (let loop ((k n) (minv 0)) (cond ((zero? k) minv) ((= (A234742 k) n) (loop (- k 1) k)) (else (loop (- k 1) minv)))))

a(n) = minimal k such that A234742(k) = n, and 0 if no such k exists.

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

A236847 Greatest inverse of A234742: a(n) = maximal k such that when it is remultiplied "upwards", from GF(2)[X] to N, the result is n, and 0 if no such k exists.

Original entry on oeis.org

0, 1, 2, 3, 4, 0, 6, 7, 8, 5, 0, 11, 12, 13, 14, 0, 16, 0, 10, 19, 0, 9, 22, 0, 24, 25, 26, 15, 28, 0, 0, 31, 32, 29, 0, 0, 20, 37, 38, 23, 0, 41, 18, 0, 44, 0, 0, 47, 48, 21, 50, 0, 52, 0, 30, 55, 56, 53, 0, 59, 0, 61, 62, 27, 64, 0, 58, 67, 0, 0, 0, 0, 40, 73, 74, 43, 76, 49, 46, 0, 0, 17, 82, 0, 36, 0, 0, 87, 88, 0, 0, 91

Offset: 0

Antti Karttunen, Jan 31 2014

nonn

Apart from zero, each term occurs at most once. 35 is the smallest positive integer not present in this sequence.

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

Differs from A236846 for the first time at n=91, where a(91) = 91, while A236846(91) = 35.
A236844 gives the positions of zeros.
Cf. A234742.
Cf. also A236836, A236837.

(define (A236847 n) (let loop ((i n)) (cond ((zero? i) i) ((= (A234742 i) n) i) (else (loop (- i 1))))))

a(n) = maximal k such that A234742(k) = n, and 0 if no such k exists.

For all n, a(n) <= 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).

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

A236834 Numbers that do not occur as results of "downward" remultiplication (N -> GF(2)[X]) of any number; numbers not present in A234741.

Views

Author

Keywords

Comments

Links

Crossrefs

A236837 The greatest inverse of A234741: a(n) = the largest k such that A234741(k) = n, and 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

A236846 Least inverse of A234742: a(n) = minimal k such that when it is remultiplied "upwards", from GF(2)[X] to N, the result is n, and 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A236847 Greatest inverse of A234742: a(n) = maximal k such that when it is remultiplied "upwards", from GF(2)[X] to N, the result is n, and 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

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

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