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

A236842 Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number; A234742 sorted and duplicates removed.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

This sequence gives the range of A234742.
After 0 and 1 these are numbers n that have such a multiset of prime divisors p, q, ..., w (p * q * ... * w = n, with p, q, ..., w not necessarily distinct) that it can be arranged so that in at least one subset of divisors of n: (p, q, w), (pq, w), (pw, q), (p, qw), (pqw), ..., all divisors (for example, in the second case: pq and w) encode by their binary representations irreducible factors of polynomial ring over GF(2) (i.e., all occur in A014580) and their (ordinary) product is n.
Above condition implies that none of the terms of A091209 occur here.

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

Complement: A236844. A236860 is a subsequence.
Positions of nonzero terms in A236853.
Cf. A234742, A236841.

Use the characteristic function A236862(n) to determine whether n is a term of this sequence or not.
Specifically:
All numbers encoding an irreducible polynomial in GF(2)[X] (A014580) occur in this sequence. This means that a prime is in this sequence if and only if it is in A091206.
On the other hand, a composite integer n is in this sequence if and only if it is either in A014580 or it has such a proper factor k (1

A260735 Iterates of A234742, starting from value a(0) = 455, with a(1) = A234742(a(0)), a(2) = A234742(a(1)), etc.

Original entry on oeis.org

455, 3087, 24843, 72975, 332563, 602919, 5893875, 221402727, 322063831, 5853742587, 10696444275, 75642464331, 749833439355, 1724537517955, 2295761459035, 4498164915283, 9436077956619, 369311889576231, 10610033249983167, 135786986032294135, 460149860040811083, 2879918014301480295, 63102417694969716063, 339029616686070752991

Offset: 0

Antti Karttunen, Aug 04 2015

nonn

455 is the first term of A236844 that doesn't settle to a fixed point at least for the first 2000 iterations of A234742. Cf. also A260713.

			The initial value a(0) = 455 ("111000111" in binary) encodes polynomial (with coefficients 0 or 1) x^8 + x^7 + x^6 + x^2 + x + 1, which in ring GF(2)[X] factorizes as (x + 1)(x + 1)(x^2 + x + 1)(x^2 + x + 1)(x^2 + x + 1). (x+1) is encoded by 3 ("11" in binary) and (x^2 + x + 1) by 7 ("111" in binary). Multiplying 3*3*7*7*7 yields the next term of the sequence, thus a(1) = 3087.
3087 ("110000001111" in binary) in turn encodes polynomial x^11 + x^10 + x^3 + x^2 + x + 1 which factorizes as (x + 1)(x^2 + x + 1)(x^2 + x + 1)(x^3 + x^2 + 1)(x^3 + x^2 + 1). Polynomial (x^3 + x^2 + 1) is encoded by 13, as 13 is "1101" in binary. Multiplying 3*7*7*13*13 yields the next term of the sequence, a(2) = 24843.

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

Cf. A234742, A260712, A260713.
Cf. A260719  (for each term, gives the number of irreducible factors in ring GF(2)[X] for the corresponding encoded polynomial, equal to how many numbers are multiplied together at each step).
Subsequence of A004767.
Cf. also A244323, A260729, A260441 for iterations starting from other values.

allocatemem((2^30));
A234742(n) = factorback(subst(lift(factor(Mod(1, 2)*Pol(binary(n)))), x, 2)); \\ After M. F. Hasler's Feb 18 2014 code.
iterates_of_A234742(start, filename) = {my(n=start, prev=-1, prevprev=-1, i=0); until((n==prevprev), write(filename, i, " ", n); prevprev = prev; prev = n; n = A234742(n); i++)} \\ Computes b-file up to the second occurrence of the fixed point or until the user presses Ctrl-C.
iterates_of_A234742(455, "b260735.txt")

;; With memoizing macro definec.
(definec (A260735 n) (if (zero? n) 455 (A234742 (A260735 (- n 1)))))

a(0) = 455; for n >= 1, a(n) = A234742(a(n-1)).

A236379 How much n increases when it is remultiplied from GF(2)[X] to Z: a(n) = A234742(n) - n.

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 0, 0, 0, 12, 8, 0, 0, 0, 0, 12, 0, 64, 24, 0, 16, 28, 0, 16, 0, 0, 0, 36, 0, 4, 24, 0, 0, 60, 128, 56, 48, 0, 0, 60, 32, 0, 56, 32, 0, 144, 32, 0, 0, 28, 0, 192, 0, 4, 72, 0, 0, 60, 8, 0, 48, 0, 0, 84, 0, 376, 120, 0, 256, 52, 112, 112, 96, 0, 0, 276, 0, 100, 120, 96, 64, 88, 0, 148, 112, 644, 64

Offset: 0

Antti Karttunen, Jan 24 2014

nonn

All terms are divisible by 4.

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

A235035 gives the positions of zeros.

Cf. also A234742, A236378, A236380, A091209, A236835, A236844.

Scheme
```
(define (A236379 n) (- (A234742 n) n))
```

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

For all n, a(A091209(n)) > 0, and also a(A236844(n)) > 0 and a(A236835(n)) > 0.

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.

A236853 a(n) = Number of times n occurs in A234742.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 2, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 2, 1, 0, 0

Offset: 0

Antti Karttunen, Jan 31 2014

nonn

First positions where the numbers n=2..10 occur are at: 91, 351, 1001, 3159, 7007, 15561, 24453, 60021, 63063. These factor in Z as: 7*13, 3*3*3*13, 7*11*13, 3*3*3*3*3*13, 7*7*11*13, 3*3*7*13*19, 3*3*11*13*19, 3*3*3*3*3*13*19, 3*3*7*7*11*13.

Cf. also A236845.

			For 3, which is prime in Z, but also irreducible in GF(2)[X] (i.e., it is one of the primes in A091206), we have k = 3 as only solution for A234732(k) = 3, thus a(3)=1.
For 5, which is prime in Z, but factors as 3 X 3 in GF(2)[X] (i.e., it is one of the primes in A091209), there cannot be any k such that A234742(k) = 5, thus a(5)=0.
For 91 = 7*13, both 7 and 13 are irreducible in GF(2)[X], but also the product 91 is (i.e., a term of A014580), this means that both k = 7 X 13 = 35 and k = 91 give such k that A234742(k) = 91, thus a(91)=2.
For 351 = 3*3*3*13, the following subsets of divisors from combinations for which the product of divisors = n, are such that every divisor is a term of A014580: (3*3*3*13), (3*117) and (351), and thus we have 3X3X3X13 = 75, 3X117 = 159 and 351 = 351 (itself in A014580), three different k such that A234741(k) = 351, so a(351) = 3.
(In contrast, the combinations like 9*39 (9X39 = 287) or 13*27 (13X27 = 175) result different A234741(175) = 119 and A234741(287) = 223 values than 351 because neither 9, 39 or 27 are in A014580).
For 1001, which factors as 7*11*13, the following subsets of divisors are such that the product of divisors = n and that every divisor is a term of A014580: (7,11,13), (11,(7*13)), (7,(11*13)), (7*11*13), and when these are multiplied with the carryless multiplication (A048720), we get 7 X 11 X 13 = 381, 11 X 91 = 565, 7 X 143 = 941 and 1001 = 1001, the four different k: 381, 565, 941 and 1001 such that A234742(k) = 1001. Thus a(1001) = 4.

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

A236844 gives the positions of zeros, A236845 the positions of terms larger than one, A236842 the positions of nonzero terms.

Cf. A236862, A236833.

a(n) should have a direct formula computable from the prime factorization of n. See the example section, and comments in A236842 and formula/program code in A236862.

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

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.

A236845 Numbers that occur in more than one way as results of "upward" remultiplication (GF(2)[X] -> N) of some number.

Original entry on oeis.org

91, 117, 143, 171, 182, 234, 247, 273, 286, 333, 342, 351, 361, 364, 369, 429, 451, 468, 471, 494, 501, 513, 539, 546, 572, 609, 637, 666, 675, 684, 687, 702, 721, 722, 728, 738, 741, 803, 819, 847, 858, 902, 936, 942, 949, 957, 981, 988, 999, 1001, 1002, 1026, 1053, 1078, 1083, 1092, 1107, 1125

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

Numbers that occur more than once in A234742.
Those terms that encode an irreducible polynomial in ring GF(2)[X] with their binary representation (that is, those that are in A014580) seem to occur also all in A091214 (that is, are a subsequence of the latter).
If n is a term, then 2n is also a term.

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

Positions of terms larger than one in A236853.
Cf. A236844, A091214, A014580.
Cf. also A236835.

Showing 1-10 of 12 results. Next

cp's OEIS Frontend

A260713 Number of iterations of A234742 needed when starting from A236844(n) before a fixed point is reached.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

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

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

A236842 Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number; A234742 sorted and duplicates removed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A260735 Iterates of A234742, starting from value a(0) = 455, with a(1) = A234742(a(0)), a(2) = A234742(a(1)), etc.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Scheme

Formula

A236379 How much n increases when it is remultiplied from GF(2)[X] to Z: a(n) = A234742(n) - n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

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

A236853 a(n) = Number of times n occurs in A234742.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.