A234742 -id:A234742 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

1361, 3721, 8073, 40257, 64125, 344925, 1121373, 4127085, 47053305, 89025909, 256718241, 864417085, 2339944761, 7793372565, 10483463769, 15540712857, 19217417625, 51731153357, 315005744053, 731886242745, 3047881618969, 19546038155241, 55232813508469, 389828042124021, 1225948485247905, 17008166929275225

Offset: 0

Antti Karttunen, Aug 04 2015

nonn

1361 is the first term of A091209 that doesn't reach a fixed point at least for the first 2000 iterations of A234742. Cf. also A260716.

Note that 1361 = A048720(61,61).

			61 ("111101" in binary) = A014580(14), i.e., it encodes the fourteenth polynomial with coefficients 0 or 1 that is irreducible over GF(2), namely x^5 + x^4 + x^3 + x^2 + 1. When we multiply that polynomial by itself (in ring GF(2)[X]), we get x^10 + x^8 + x^6 + x^4 + 1, encoded by 1361 with binary representation "10101010001" [1361 = A048720(61,61)]. This is used as the initial value a(0) of this sequence. The next term is obtained by multiplying these two factors 61 and 61 as ordinary integers, which gives a(1) = 61*61 = 3721.
3721 ("111010001001" in binary) in turn encodes polynomial x^11 + x^10 + x^9 + x^7 + x^3 + 1 which factorizes in ring GF(2)[X] as (x + 1)(x + 1)(x + 1)(x^8 + x^5 + x^3 + x + 1). Polynomial (x + 1) is encoded by 3 ("11" in binary) and (x^8 + x^5 + x^3 + x + 1) by 299 ("100101011" in binary). Multiplying 3*3*3*299 in ordinary way gives the next term of the sequence, a(2) = 8073.

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

Cf. A014580, A048720, A234742, A260712, A260713, A260716.
Cf. A260720 (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 the next step).
Subsequence of A016813.
Cf. also A244323, A260729, A260735 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(1361, "b260441.txt")

;; With memoizing macro definec.
(definec (A260441 n) (if (zero? n) 1361 (A234742 (A260441 (- n 1)))))

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

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

Original entry on oeis.org

6, 6, 5, 4, 6, 55, 141, 5, 4, 1, 6, 2, 145, 55, 6, 2, 141, 5, 2, 4, 4, 1, 4, 5, 6, 3, 4, 2, 4, 145, 55, 1, 3, 6, 3, 2, 14, 2, 141, 27, 5, 65, 1, 10, 2, 1, 4, 4, 4, 1, 4, 3, 1, 3, 9, 5, 1, 6, 5, 18, 3, 4, 2, 6, 4, 3, 145, 17, 55, 4, 1, 11, 36, 1, 3, 6, 5, 14, 3, 2, 14, 4, 1, 10, 2, 13, 141, 1, 6, 3, 27, 5, 9, 2, 65, 10, 1, 10, 2, 10, 2, 2, 3, 52, 86, 1

Offset: 1

Antti Karttunen, Aug 04 2015

nonn

It is not known whether the sequence is well-defined for all values. For example, does a(190) have a finite value? Cf. sequence A260735, starting iteration from 455 = A236844(190).

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

Cf. A234742, A236844, A260712, A260735.

Subsequence: A260716.

allocatemem((2^29));
v236844 = [5, 10, 15, 17, 20, 23, 29, 30, 34, 35, 40, 43, 45, 46, 51, 53, 58, 60, 65, 68, 69, 70, 71, 79, 80, 83, 85, 86, 89, 90, 92, 95, 101, 102, 105, 106, 107, 113, 116, 119, 120, 125, 127, 129, 130, 135, 136, 138, 139, 140, 142, 149, 151, 153, 155, 158, 159, 160, 161, 163, 166, 170, 172, 173, 178, 179, 180, 181, 184, 187, 190, 195, 197, 199, 202, 204, 205, 207, 210, 212, 214, 215, 221, 223, 226, 227, 232, 233, 235, 237, 238, 240, 245, 249, 250, 251, 254, 255, 257, 258, 260, 263, 265, 267, 269, 270, 271, 272, 276, 277, 278, 280, 281, 284, 289, 293, 295, 298, 302, 303, 305, 306, 307, 310, 311, 315, 316, 317, 318, 320, 321, 322, 323, 326, 331, 332, 335, 337, 339, 340, 344, 346, 347, 349, 353, 356, 358, 359, 360, 362, 365, 367, 368, 371, 373, 374, 377, 380, 381, 383, 387, 389, 390, 394, 398, 401, 404, 405, 408, 409, 410, 414, 417, 420, 421, 424, 428, 430, 431, 437, 439, 442, 443, 446, 447, 449, 452, 453, 454];
A236844(n) = v236844[n];
A234742(n) = factorback(subst(lift(factor(Mod(1, 2)*Pol(binary(n)))), x, 2)); \\ After M. F. Hasler's Feb 18 2014 code.
A260712(n) = {my(prev=-1,i=-1); until((n==prev), prev = n; n = A234742(n); i++); return(i); };
A260713(n) = A260712(A236844(n));
for(n=1, 189, write("b260713.txt", n, " ", A260713(n)));

(define (A260713 n) (A260712 (A236844 n)))

a(n) = A260712(A236844(n)).

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.

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

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.

Showing 1-10 of 38 results. Next

cp's OEIS Frontend

A235035 Numbers n for which A234742(n) = n: numbers n whose binary representation encodes a GF(2)[X]-polynomial such that when its irreducible factors are multiplied together as ordinary integers (with carry-bits), the result is n.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A260712 Number of iterations of A234742 needed when started from n before a fixed point is reached.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Scheme

Formula

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Scheme

Formula

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

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