A260735 -id:A260735 - cp's OEIS frontend

A260719 a(n) = A091222(A260735(n)): number of irreducible factors (in ring GF(2)[X]) of the binary encoded polynomial obtained after the n-th iteration of A234742, when starting with the initial value 455.

5, 5, 3, 4, 3, 5, 9, 2, 7, 2, 6, 6, 2, 2, 2, 3, 8, 8, 6, 5, 5, 7, 6, 4, 5, 6, 2, 7, 6, 4, 5, 4, 5, 4, 5, 9, 4, 10, 3, 4, 7, 4, 4, 3, 4, 3, 5, 8, 6, 4, 7, 5, 3, 7, 3, 3, 3, 3, 3, 7, 3, 5, 6, 6, 9, 4, 9, 3, 5, 6, 3, 4, 5, 7, 7, 4, 5, 2, 10, 11, 6, 6, 7, 13, 4, 6, 5, 10, 6, 4, 7, 4, 10, 8, 3, 7, 7, 4, 5, 5, 2, 4, 8, 3, 4, 3, 7, 4, 6, 3, 15, 3, 4, 7, 6, 6, 6, 5, 5, 8, 4

Offset: 0

Antti Karttunen, Aug 04 2015

nonn

Records occur in positions 0, 6, 37, 79, 83, 110, 329, 554, 1019, 1318, 2027, and they are 5, 9, 10, 11, 13, 15, 16, 17, 20, 21, 23.
First 2's occur at positions 7, 9, 12, 13, 14, 26, 77, 100, 127, 158, 161, 173, 183, 193, 201, 208, 442, 447, 528, 544, 642, 706, 1033, 1089, 1222, 1831.
Note that if this sequence ever obtains value 1, then the rest of terms are also 1's, as then A260735 has attained as its constant value one of the terms of A091214 (which is a subsequence of A235035, the fixed points of A234742).

			See example in A260735. This sequence gives the number of those irreducible factors (in ring GF(2)[X], not necessarily all primes in Z) that are multiplied together (in ordinary way) to get the next term of A260735. For example, a(0) = 5 (for 3 * 3 * 7 * 7 * 7), a(1) = 5 (for 3 * 7 * 7 * 13 * 13).

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

Cf. A091214, A091222, A234742, A235035, A260735, A260720.

allocatemem((2^30));
{my(n=455, fm); for(i=0,2049, fm=factor(Pol(binary(n))*Mod(1, 2)); write("b260719.txt", i, " ", sum(k=1, #fm~, fm[k, 2])); n = factorback(subst(lift(fm),x,2))); };

(define (A260719 n) (A091222 (A260735 n)))

a(n) = A091222(A260735(n)).

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

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

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

Original entry on oeis.org

0, 0, 0, 0, 6, 0, 0, 0, 5, 6, 0, 0, 0, 0, 5, 0, 4, 5, 0, 6, 4, 0, 55, 0, 0, 0, 4, 0, 141, 5, 0, 0, 140, 4, 1, 5, 0, 0, 54, 6, 0, 4, 2, 0, 145, 55, 0, 0, 3, 0, 6, 0, 2, 4, 0, 0, 1, 141, 0, 5, 0, 0, 3, 0, 2, 140, 0, 4, 4, 1, 4, 5, 0, 0, 1, 0, 2, 54, 5, 6, 3, 0, 3, 4, 4, 2, 0, 0, 4, 145, 0, 55, 139, 0, 1, 0, 0, 3, 53, 0, 3, 6, 0, 0, 3, 2, 14, 4, 0

Offset: 1

Antti Karttunen, Aug 04 2015

nonn

The fixed points of A234742 are in A235035, thus the latter gives the zeros of this sequence.

It is not known whether the sequence is well-defined for all values. For example, does a(455) or a(1361) have a finite value? Cf. sequences A260735 and A260441.

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

Cf. A235035 (gives the positions of zeros).
Cf. A234742, A260735, A260735, A260441.
Subsequences: A260713, A260716.

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.
A260712(n) = {my(prev=-1,i=-1); until((n==prev), prev = n; n = A234742(n); i++); return(i); };
for(n=1, 454, write("b260712.txt", n, " ", A260712(n)));

;; Uses memoizing definec-macro.
(definec (A260712 n) (let ((next (A234742 n))) (if (= next n) 0 (+ 1 (A260712 next)))))

(define (A260712loop n) (let loop ((n (A234742 n)) (prev_n n) (i 0)) (if (= n prev_n) i (loop (A234742 n) n (+ 1 i)))))

If A234742(n) = n, then a(n) = 0, otherwise a(n) = 1 + a(A234742(n)).
Other identities:
a(A235035(n)) = 0.
a(2n) = a(n).

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

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

Original entry on oeis.org

23, 39, 99, 279, 775, 1271, 3003, 26411, 45059, 53219, 96811, 180063, 538083, 1557987, 2994571, 5394027, 76600323, 78603291, 646326135, 5260930155, 11705029515, 55771437087, 918661840551, 2662267345431, 156054629431431, 1885162669463151, 2739827178329319, 23916267980687775, 343334160580618935

Offset: 0

Antti Karttunen and M. F. Hasler, Jul 23 2014

nonn

The sequence reaches its fixed point at a(55) = 3643749709604450870616156947649219, after which the sequence stays constant, a(55) = a(56) = a(57), etc.

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

Cf. A234742, A235033, A235035, A260712, A260713, A260716.

Cf. also A260729, A260735, A260441 (other such iterations).

A234742(n)=factorback(subst(lift(factor(Mod(1, 2)*Pol(binary(n)))), x, 2))+(n==1)
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.
iterates_of_A234742(23,"b244323.txt")

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

Original entry on oeis.org

29, 33, 93, 217, 341, 961, 2821, 7409, 8973, 53625, 94325, 225169, 470517, 1349089, 4076589, 22862205, 40165377, 506257425, 918577233, 1042701969, 5347778553, 76822655445, 242180261569, 243151045949, 835744242025, 1398202164821, 7718585207745, 17886399120625, 36628781776125, 140199249091321, 579641775855025, 3110633457224293, 9887055813390673

Offset: 0

Antti Karttunen, Aug 04 2015

nonn

The sequence reaches its fixed point at a(141) = after which the sequence stays constant, a(142) = a(143) = a(144), etc.

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

Cf. A234742, A260712, A260713.

Cf. also A244323, A260735, A260441 for iterations starting from other values.

allocatemem((2^29));
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.
iterates_of_A234742(29, "b260729.txt")

;; With memoizing macro definec.
(definec (A260729 n) (if (zero? n) 29 (A234742 (A260729 (- n 1)))))

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

cp's OEIS Frontend

A260719 a(n) = A091222(A260735(n)): number of irreducible factors (in ring GF(2)[X]) of the binary encoded polynomial obtained after the n-th iteration of A234742, when starting with the initial value 455.

Views

Author

Keywords

Comments

Examples

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

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

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula