A091209 -id:A091209 - cp's OEIS frontend

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

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

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

Numbers that do not occur in A234742 (A236842).
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.

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

Complement: A236842.
A setwise difference of A236848 and A236849.
A091209 is a subsequence.
Positions of zeros in A236853, A236846, A236847 and A236862.
Cf. A236845.
Cf. also A236834.

For all n, A236379(a(n)) > 0.

A235034 Numbers whose prime divisors, when multiplied together without carry-bits (as encodings of GF(2)[X]-polynomials, with A048720), produce the original number; numbers for which A234741(n) = n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 34, 37, 38, 40, 41, 43, 44, 46, 47, 48, 51, 52, 53, 56, 58, 59, 60, 61, 62, 64, 67, 68, 71, 73, 74, 76, 79, 80, 82, 83, 85, 86, 88, 89, 92, 94, 95, 96, 97, 101

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

If n is present, then 2n is present also, as shifting binary representation left never produces any carries.

			All primes occur in this sequence as no multiplication -> no need to add any intermediate products -> no carry bits produced.
Composite numbers like 15 are also present, as 15 = 3*5, and when these factors (with binary representations '11' and '101') are multiplied as:
   101
  1010
  ----
  1111 = 15
we see that the intermediate products 1*5 and 2*5 can be added together without producing any carry-bits (as they have no 1-bits in the same columns/bit-positions), so A048720(3,5) = 3*5 and thus 15 is included in this sequence.

Gives the positions of zeros in A236378, i.e., n such that A234741(n) = n.
Intersection with A235035 gives A235032.
Other subsequences: A000040 (A091206 and also A091209), A045544 (A004729), A093641, A235040 (gives odd composites in this sequence), A235050, A235490.
Cf. A048720, A061858, A234741.

A235033 Numbers which are factored to a different set of primes in Z as to the irreducible polynomials in GF(2)[X].

Original entry on oeis.org

5, 9, 10, 15, 17, 18, 20, 21, 23, 25, 27, 29, 30, 33, 34, 35, 36, 39, 40, 42, 43, 45, 46, 49, 50, 51, 53, 54, 55, 57, 58, 60, 63, 65, 66, 68, 69, 70, 71, 72, 75, 77, 78, 79, 80, 81, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 95, 98, 99, 100, 101, 102, 105, 106

Offset: 1

Antti Karttunen, Jan 02 2014

nonn

If a term is included in this sequence, then all its ordinary multiples as well as any "A048720-multiples" are included as well. (Cf. the characteristic function A235046.)

The sequence which gives all such n that A001222(n) differs from A091222(n) is a subsequence of this sequence.

			5 is included in this sequence, because, although it is prime, its binary representation '101' encodes a polynomial x^2 + 1, which is reducible in polynomial ring GF(2)[X] as (x+1)(x+1), i.e., 5 = A048720(3,3).
9 is included in this sequence, as it factors as 3*3 in Z, the corresponding polynomial (bin.repr. '1001'): x^3 + 1 factors as (x+1)(x^2+x+1), i.e., 9 = A048720(3,7), so even although the number of prime/irreducible factors is the same, the factors themselves (i.e., their binary codes) are not exactly the same, thus 9 is included here.
On the other hand, none of 2, 3, 4, 11 and 111 are included in this sequence because they occur in the complement sequence, A235032 (please see examples there).

Gives the positions of nonzeros in A236380, i.e., n such that A234741(n) <> A234742(n).
Characteristic function: A235046.
Complement: A235032. Subsets: A091209, A091214.

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

Original entry on oeis.org

5, 10, 15, 17, 20, 23, 27, 29, 30, 34, 39, 40, 45, 46, 51, 53, 54, 57, 58, 60, 65, 68, 71, 75, 78, 80, 83, 85, 90, 92, 95, 99, 101, 102, 105, 106, 107, 108, 113, 114, 116, 119, 120, 127, 129, 130, 135, 136, 139, 141, 142, 147, 150, 151, 153, 156, 160, 163, 165

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

Numbers that occur more than once in A234741.

			5 occurs here, because it occurs in A234741 both as A234741(5)=5 and A234741(9)=5, as A048720(3,3)=5.
43 do not occur here, as although it is a term of A091209, it only occurs at A234741(43) as it cannot be obtained by other means as a carryless product than as 43 = A048720(3,25).

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

Positions of terms larger than one in A236833.

Cf. A236833, A236834. A091209 is NOT a subsequence.

For all n, A236379(a(n)) > 0.

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

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

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.

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.

A236849 Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number and have at least one prime divisor encoding a reducible polynomial in ring GF(2)[X].

Original entry on oeis.org

25, 50, 55, 75, 87, 100, 110, 115, 145, 150, 165, 174, 175, 185, 200, 203, 213, 220, 225, 230, 253, 261, 275, 285, 290, 299, 300, 301, 319, 325, 330, 345, 348, 350, 355, 357, 370, 375, 385, 391, 395, 400, 406, 415, 425, 426, 435, 440, 445, 450, 460, 475, 477, 495, 505, 506, 515, 522, 525, 529, 535, 545, 550, 555

Offset: 1

Antti Karttunen, Jan 31 2014

nonn

Terms of A236842 (A234742) that are divisible by at least one of the primes in A091209.

a(4)=75, is the first term here which does not occur in A236834. On the other hand, A236834(5)=91 is the first of its terms that does not occur here.

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

Setwise difference A236848 \ A236844, and also A236842 \ A236860.

Cf. A091209, A234742, A236842, A236848, A236834.

A294883 Number of divisors of n that are irreducible when their binary expansion is interpreted as polynomial over GF(2).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Nov 09 2017

nonn

Number of terms of A014580 that divide n.

Antti Karttunen, Table of n, a(n) for n = 1..21845
Index entries for sequences related to polynomials in ring GF(2)[X]

Cf. A000005, A014580, A091225, A294881, A294884.
Cf. A091209 (gives a subset of zeros).
Cf. also A234741, A234742, A294893.

A294883(n) = sumdiv(n,d,polisirreducible(Mod(1, 2)*Pol(binary(d))));

a(n) = Sum_{d|n} A091225(d).
a(n) + A294884(n) = A000005(n).
a(n) = A294881(n) + A091225(n).

Previous Showing 11-20 of 24 results. Next

cp's OEIS Frontend

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

A235034 Numbers whose prime divisors, when multiplied together without carry-bits (as encodings of GF(2)[X]-polynomials, with A048720), produce the original number; numbers for which A234741(n) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A235033 Numbers which are factored to a different set of primes in Z as to the irreducible polynomials in GF(2)[X].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A236849 Numbers that occur as results of remultiplication (GF(2)[X] -> N) of some number and have at least one prime divisor encoding a reducible polynomial in ring GF(2)[X].

Views

Author

Keywords

Comments

Links

Crossrefs