Displaying 1-10 of 38 results found.
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.
+20
13
0, 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16, 19, 22, 24, 25, 26, 28, 31, 32, 37, 38, 41, 44, 47, 48, 50, 52, 55, 56, 59, 61, 62, 64, 67, 73, 74, 76, 82, 87, 88, 91, 94, 96, 97, 100, 103, 104, 109, 110, 111, 112, 115, 117, 118, 122, 123, 124, 128, 131, 134, 137
PROG
(define A235035 (MATCHING-POS 1 0 (lambda (n) (or (zero? n) (= n (reduce * 1 (GF2Xfactor n)))))))
CROSSREFS
Gives the positions of zeros in A236379, i.e., n such that A234742(n) = n.
Numbers that do not occur as results of "upward" remultiplication (GF(2)[X] -> N) of any number; numbers not present in A234742.
+20
13
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
COMMENTS
This is a subsequence of A236848, thus all terms are divisible by at least one such prime which is reducible as polynomial over GF(2) (i.e. one of the primes in A091209). A236835(7)=27 is the first member of A236835 which does not occur here. a(12)=43 is the first term here which does not occur in A236835.
Number of iterations of A234742 needed when started from n before a fixed point is reached.
+20
9
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
COMMENTS
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.
FORMULA
Other identities:
a(2n) = a(n).
PROG
(PARI)
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))); (Scheme, two alternatives, the first one using memoizing definec-macro)
(define (A260712loop n) (let loop ((n ( A234742 n)) (prev_n n) (i 0)) (if (= n prev_n) i (loop ( A234742 n) n (+ 1 i)))))
CROSSREFS
Cf. A235035 (gives the positions of zeros).
Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number; A234742 sorted and duplicates removed.
+20
8
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
COMMENTS
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.
FORMULA
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<k<n, k|n) that both k and n/k are members of this sequence.
CROSSREFS
Positions of nonzero terms in A236853.
Iterates of A234742, starting from value a(0) = 1361, with a(1) = A234742(a(0)), a(2) = A234742(a(1)), etc.
+20
8
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
COMMENTS
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.
FORMULA
a(0) = 1361; for n >= 1, a(n) = A234742(a(n-1)).
EXAMPLE
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.
PROG
(PARI)
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") (Scheme, with memoizing macro definec)
CROSSREFS
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).
Number of iterations of A234742 needed when starting from A236844(n) before a fixed point is reached.
+20
8
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
COMMENTS
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).
PROG
(PARI)
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];
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, 189, write("b260713.txt", n, " ", A260713(n)));
Iterates of A234742, starting from value a(0) = 455, with a(1) = A234742(a(0)), a(2) = A234742(a(1)), etc.
+20
8
455, 3087, 24843, 72975, 332563, 602919, 5893875, 221402727, 322063831, 5853742587, 10696444275, 75642464331, 749833439355, 1724537517955, 2295761459035, 4498164915283, 9436077956619, 369311889576231, 10610033249983167, 135786986032294135, 460149860040811083, 2879918014301480295, 63102417694969716063, 339029616686070752991
COMMENTS
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.
FORMULA
a(0) = 455; for n >= 1, a(n) = A234742(a(n-1)).
EXAMPLE
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.
PROG
(PARI)
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") (Scheme, with memoizing macro definec)
CROSSREFS
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).
How much n increases when it is remultiplied from GF(2)[X] to Z: a(n) = A234742(n) - n.
+20
7
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
COMMENTS
All terms are divisible by 4.
CROSSREFS
A235035 gives the positions of zeros.
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).
+20
7
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
COMMENTS
All terms are divisible by 4.
CROSSREFS
A235032 gives the positions of zeros, A235033 the positions of nonzeros.
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.
+20
7
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
COMMENTS
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.
FORMULA
a(n) = minimal k such that A234742(k) = n, and 0 if no such k exists. For all n, a(n) <= n.
PROG
(Scheme) (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)))))
CROSSREFS
Differs from A236847 for the first time at n=91, where a(91)=35, while A236847(91)=91. A236844 gives the positions of zeros.
Search completed in 0.027 seconds
|