cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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

Views

Author

Antti Karttunen, Jan 22 2014

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

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

Programs

Formula

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

A091214 Composite numbers whose binary representation encodes a polynomial irreducible over GF(2).

Original entry on oeis.org

25, 55, 87, 91, 115, 117, 143, 145, 171, 185, 203, 213, 247, 253, 285, 299, 301, 319, 333, 351, 355, 357, 361, 369, 375, 391, 395, 415, 425, 445, 451, 471, 477, 501, 505, 515, 529, 535, 539, 545, 623, 637, 665, 675, 687, 695, 721, 731, 789, 799, 803, 817
Offset: 1

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Comments

"Encoded in binary representation" means that a polynomial a(n)*X^n+...+a(0)*X^0 over GF(2) is represented by the binary number a(n)*2^n+...+a(0)*2^0 in Z (where each coefficient a(k) = 0 or 1).

Links

Crossrefs

Intersection of A002808 and A014580.
Subsequence of A235033, A236834 and A236838.
Left inverse: A235044.
Cf. A091206 (Primes whose binary expansion encodes a polynomial irreducible over GF(2)), A091209 (Primes that encode a polynomial reducible over GF(2)), A091212 (Composite, and reducible over GF(2)).
Cf. A091215, A235027, A235046, A236841, A236845, A236850, A236851, A236861.
Cf. also A235041-A235042.

Programs

  • Mathematica
    fQ[n_] := Block[{ply = Plus @@ (Reverse@ IntegerDigits[n, 2] x^Range[0, Floor@ Log2@ n])}, ply == Factor[ply, Modulus -> 2] && n != 2^Floor@ Log2@ n && ! PrimeQ@ n]; Select[ Range@ 840, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
  • PARI
    isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
isA091214(n) = (!isprime(n) && isA014580(n));
n = 0; i = 0; while(n < 2^20, n++; if(isA091214(n), i++; write("b091214.txt", i, " ", n)));
\\ The b-file was computed with this program. Antti Karttunen, May 17 2015

Formula

Other identities. For all n >= 1:
A235044(a(n)) = n. [A235044 works as a left inverse of this sequence.]
a(n) = A014580(A091215(n)). - Antti Karttunen, May 17 2015

Extensions

Entry revised and name corrected by Antti Karttunen, May 17 2015

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

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jan 31 2014

Keywords

Comments

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.

Links

Crossrefs

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.

Formula

For all n, A236379(a(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

Views

Author

Antti Karttunen, Jan 31 2014

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

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

Formula

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.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.