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.

Previous Showing 21-30 of 48 results. Next

A091211 A091242-indices of primes that are composite GF(2)[X]-polynomials.

Original entry on oeis.org

2, 11, 16, 21, 32, 41, 55, 62, 66, 71, 81, 86, 91, 103, 113, 121, 123, 134, 142, 148, 150, 163, 165, 186, 190, 195, 210, 215, 221, 227, 229, 235, 239, 249, 261, 265, 270, 283, 288, 298, 300, 303, 307, 314, 319, 327, 333, 342, 350, 360, 369, 376, 380, 385
Offset: 1

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Links

Crossrefs

a(n) = A091246(A091209(n)). Complement of A091213.

A091213 A091242-indices of composite GF(2)[X]-polynomials that are also composite integers.

Original entry on oeis.org

1, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 63, 64, 65, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 79, 80, 82
Offset: 1

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Links

Crossrefs

a(n) = A091246(A091212(n)). Complement of A091211.

A234752 Binary encodings of reducible polynomials over GF(2)that are fixed by blue code: a(n) = A091242(A234749(n)).

Original entry on oeis.org

6, 18, 20, 21, 106, 107, 108, 120, 121, 126, 127, 258, 259, 260, 261, 272, 273, 278, 279, 360, 366, 367, 378, 380, 381, 1546, 1547, 1548, 1549, 1560, 1561, 1566, 1567, 1632, 1633, 1638, 1639, 1650, 1651, 1652, 1653, 1800, 1801, 1806, 1818, 1819, 1820, 1890, 1892, 1893, 1904, 1905, 1910, 1911
Offset: 1

Views

Author

Antti Karttunen, Feb 15 2014

Keywords

Comments

Irreducible polynomials over GF(2) (A014580) fixed by blue code (A193231) seem to be much rarer. The first 22 cases are: 7, 19, 109, 361, 379, 1807, 1821, 1891, 4645, 4663, 4897, 4915, 4941, 27327, 27329, 27589, 27607, 27829, 27851, 28067, 28081, 28125.

Links

Crossrefs

Intersection of A091242 and A118666.
Cf. A193231, A234745, A234746, A234749.

Programs

Formula

a(n) = A091242(A234749(n)).

A048720 Multiplication table {0..i} X {0..j} of binary polynomials (polynomials over GF(2)) interpreted as binary vectors, then written in base 10; or, binary multiplication without carries.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 4, 3, 0, 0, 4, 6, 6, 4, 0, 0, 5, 8, 5, 8, 5, 0, 0, 6, 10, 12, 12, 10, 6, 0, 0, 7, 12, 15, 16, 15, 12, 7, 0, 0, 8, 14, 10, 20, 20, 10, 14, 8, 0, 0, 9, 16, 9, 24, 17, 24, 9, 16, 9, 0, 0, 10, 18, 24, 28, 30, 30, 28, 24, 18, 10, 0, 0, 11, 20, 27, 32, 27, 20, 27, 32, 27, 20, 11, 0
Offset: 0

Views

Author

Antti Karttunen, Apr 26 1999

Keywords

Comments

Essentially same as A091257 but computed starting from offset 0 instead of 1.
Each polynomial in GF(2)[X] is encoded as the number whose binary representation is given by the coefficients of the polynomial, e.g., 13 = 2^3 + 2^2 + 2^0 = 1101_2 encodes 1*X^3 + 1*X^2 + 0*X^1 + 1*X^0 = X^3 + X^2 + X^0. - Antti Karttunen and Peter Munn, Jan 22 2021
To listen to this sequence, I find instrument 99 (crystal) works well with the other parameters defaulted. - Peter Munn, Nov 01 2022

Examples

			Top left corner of array:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 ...
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  0  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 ...
  0  3  6  5 12 15 10  9 24 27 30 29 20 23 18 17 ...
  ...
From _Antti Karttunen_ and _Peter Munn_, Jan 23 2021: (Start)
Multiplying 10 (= 1010_2) and 11 (= 1011_2), in binary results in:
     1011
  *  1010
  -------
   c1011
  1011
  -------
  1101110  (110 in decimal),
and we see that there is a carry-bit (marked c) affecting the result.
In carryless binary multiplication, the second part of the process (in which the intermediate results are summed) looks like this:
    1011
  1011
  -------
  1001110  (78 in decimal).
(End)

Links

Crossrefs

Cf. A051776 (Nim-product), A091257 (subtable).
Carryless multiplication in other bases: A325820 (3), A059692 (10).
Ordinary {0..i} * {0..j} multiplication table: A004247 and its differences from this: A061858 (which lists further sequences related to presence/absence of carry in binary multiplication).
Carryless product of the prime factors of n: A234741.
Binary irreducible polynomials ("X-primes"): A014580, factorization table: A256170, table of "X-powers": A048723, powers of 3: A001317, rearranged subtable with distinct terms (comparable to A054582): A277820.
See A014580 for further sequences related to the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the integer encoding.
Row/column 3: A048724 (even bisection of A003188), 5: A048725, 6: A048726, 7: A048727; main diagonal: A000695.
Associated additive operation: A003987.
Equivalent sequences, as compared with standard integer multiplication: A048631 (factorials), A091242 (composites), A091255 (gcd), A091256 (lcm), A280500 (division).
See A091202 (and its variants) and A278233 for maps from/to ordinary multiplication.
See A115871, A115872 and A277320 for tables related to cross-domain congruences.

Programs

  • Maple
    trinv := n -> floor((1+sqrt(1+8*n))/2); # Gives integral inverses of the triangular numbers
# Binary multiplication of nn and mm, but without carries (use XOR instead of ADD):
Xmult := proc(nn,mm) local n,m,s; n := nn; m := mm; s := 0; while (n > 0) do if(1 = (n mod 2)) then s := XORnos(s,m); fi; n := floor(n/2); # Shift n right one bit. m := m*2; # Shift m left one bit. od; RETURN(s); end;
  • Mathematica
    trinv[n_] := Floor[(1 + Sqrt[1 + 8*n])/2];
Xmult[nn_, mm_] := Module[{n = nn, m = mm, s = 0}, While[n > 0, If[1 == Mod[n, 2], s = BitXor[s, m]]; n = Floor[n/2]; m = m*2]; Return[s]];
a[n_] := Xmult[(trinv[n] - 1)*((1/2)*trinv[n] + 1) - n, n - (trinv[n]*(trinv[n] - 1))/2];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Mar 16 2015, updated Mar 06 2016 after Maple *)
  • PARI
    up_to = 104;
A048720sq(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A048720list(up_to) = { my(v = vector(1+up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A048720sq(col, a-col))); (v); };
v048720 = A048720list(up_to);
A048720(n) = v048720[1+n]; \\ Antti Karttunen, Feb 15 2021

Formula

a(n) = Xmult( (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n), (n-((trinv(n)*(trinv(n)-1))/2)) );
T(2b, c)=T(c, 2b)=T(b, 2c)=2T(b, c); T(2b+1, c)=T(c, 2b+1)=2T(b, c) XOR c - Henry Bottomley, Mar 16 2001
For n >= 0, A003188(2n) = T(n, 3); A003188(2n+1) = T(n, 3) XOR 1, where XOR is the bitwise exclusive-or operator, A003987. - Peter Munn, Feb 11 2021

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Original entry on oeis.org

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375
Offset: 1

Views

Author

David Petry (petry(AT)accessone.com)

Keywords

Comments

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.
The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014
2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021
For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

Examples

			x^4 + x^3 + 1 -> 16+8+1 = 25. Or, x^4 + x^3 + 1 -> 11001 (binary) = 25 (decimal).

Links

Crossrefs

Written in binary: A058943.
Number of degree-n irreducible polynomials: A001037, see also A000031.
Multiplication table: A048720.
Characteristic function: A091225. Inverse: A091227. a(n) = A091202(A000040(n)). Almost complement of A091242. Union of A091206 & A091214 and also of A091250 & A091252. First differences: A091223. Apart from a(1) and a(2), a subsequence of A092246 and hence A000069.
Table of irreducible factors of n: A256170.
Irreducible polynomials satisfying particular conditions: A071642, A132447, A132449, A132453, A162570.
Factorization sentinel: A278239.
Sequences analyzing the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the corresponding integer: A234741, A234742, A235032, A235033, A235034, A235035, A235040, A236850, A325386, A325559, A325560, A325563, A325641, A325642, A325643.
Factorization-preserving isomorphisms: A091203, A091204, A235041, A235042.
See A115871 for sequences related to cross-domain congruences.
Functions based on the irreducibles: A305421, A305422.

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]; fQ[2] = True; Select[ Range@ 378, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
Reap[Do[If[IrreduciblePolynomialQ[IntegerDigits[n, 2] . x^Reverse[Range[0, Floor[Log[2, n]]]], Modulus -> 2], Sow[n]], {n, 2, 1000}]][[2, 1]] (* Jean-François Alcover, Nov 21 2016 *)
  • PARI
    is(n)=polisirreducible(Pol(binary(n))*Mod(1,2)) \\ Charles R Greathouse IV, Mar 22 2013

A193231 Blue code for n: in binary coding of a polynomial over GF(2), substitute x+1 for x (see Comments for precise definition).

Original entry on oeis.org

0, 1, 3, 2, 5, 4, 6, 7, 15, 14, 12, 13, 10, 11, 9, 8, 17, 16, 18, 19, 20, 21, 23, 22, 30, 31, 29, 28, 27, 26, 24, 25, 51, 50, 48, 49, 54, 55, 53, 52, 60, 61, 63, 62, 57, 56, 58, 59, 34, 35, 33, 32, 39, 38, 36, 37, 45, 44, 46, 47, 40, 41, 43, 42, 85, 84, 86
Offset: 0

Views

Author

Franklin T. Adams-Watters, Jul 18 2011

Keywords

Comments

This is a self-inverse permutation of the nonnegative integers.
The function "substitute x+1 for x" on polynomials over GF(2) is completely multiplicative.
What is the density of fixed points in this sequence? Do we get a different answer if we look only at irreducible polynomials?
From Antti Karttunen, Dec 27 2013: (Start)
As what comes to the above question, the number of fixed points in range [2^(n-1),(2^n)-1] of the sequence is given by A131575(n). In range [0,0] there is one fixed point: 0, in range [1,1] there is also one: 1, in range [2,3] there are no fixed points, in range [4,7] there are two fixed points: 6 and 7, and so on. (Cf. also the C-code given in A118666.)
Similarly, the number of cycles in such ranges begins as 1, 1, 1, 3, 4, 10, 16, 36, 64, 136, ... which is A051437 shifted two steps right (prepended with 1's): Because the sequence is a self-inverse permutation, the number of its cycles in range [2^(n-1),(2^n)-1] is computed as: cycles(n) = (A011782(n)-number_of_fixedpoints(n))/2 + number_of_fixedpoints(n), which matches with the identity: A051437(n-2) = (A011782(n)-A131575(n))/2 + A131575(n), for n>=2.
In OEIS terms, the above comment about multiplicativeness can be rephrased as: a(A048720(x,y)) = A048720(a(x),a(y)) for all integers x, y >= 0. Here A048720(x,y) gives the product of carryless binary multiplication of x and y.
The permutation conjugates between Gray code and its inverse: A003188(n) = a(A006068(a(n))) and A006068(n) = a(A003188(a(n))) [cf. the identity 1.19-9d: gB = Bg^{-1} given on page 53 of fxtbook].
Because of the multiplicativity, the subset of irreducible (and respectively: composite) polynomials over GF(2) is closed under this permutation. Cf. the following mappings: a(A014580(n)) = A234750(n) and a(A091242(n)) = A234745(n).
(End)

Examples

			11, binary 1011, corresponds to polynomial x^3+x+1, substituting: (x+1)^3+(x+1)+1 = x^3+x^2+x+1 + x+1 + 1 = x^3+x^2+1, binary 1101 = decimal 13, so a(11) = 13.
From _Tilman Piesk_, Jun 26 2025: (Start)
The binary exponents of 11 are {0, 1, 3}, because 11 = 2^0 + 2^1 + 2^3.
a(11) = A001317(0) XOR A001317(1) XOR A001317(3) = 1 XOR 3 XOR 15 = 13. (End)

Links

Crossrefs

Cf. A000069, A001969, A001317, A003987, A048720, A048724, A065621, A051437, A118666 (fixed points), A131575, A234022 (the number of 1-bits), A234023, A010060, A234745, A234750.
Similarly constructed permutation pairs: A003188/A006068, A135141/A227413, A232751/A232752, A233275/A233276, A233277/A233278, A233279/A233280.
Other permutations based on this (by conjugating, composing, etc): A234024, A234025/A234026, A234027, A234612, A234613, A234747, A234748, A244987, A245812, A245454.

Programs

  • Mathematica
    f[n_] := Which[0 <= # <= 1, #, EvenQ@ #, BitXor[2 #, #] &[f[#/2]], True, BitXor[#, 2 # + 1] &[f[(# - 1)/2]]] &@ Abs@ n; Table[f@ n, {n, 0, 66}] (* Michael De Vlieger, Feb 12 2016, after Robert G. Wilson v at A048724 and A065621 *)
  • PARI
    tox(n) = local(x=Mod(1,2)*X, xp=1, r); while(n>0,if(n%2,r+=xp);xp*=x;n\=2);r
a(n)=subst(lift(subst(tox(n),X,X+1)),X,2)
  • PARI
    a(n)={local(x='x);subst(lift(Mod(1,2)*subst(Pol(binary(n),x),x,1+x)),x,2)};
  • Python
    def a065621(n): return n^(2*(n - (n&-n)))
def a048724(n): return n^(2*n)
l=[0, 1]
for n in range(2, 101):
    if n%2==0: l.append(a048724(l[n//2]))
    else: l.append(a065621(1 + l[(n - 1)//2]))
print(l) # Indranil Ghosh, Jun 04 2017
  • Scheme
    ;; with memoizing macro definec available in Antti Karttunen's IntSeq-library:
(define (A193231 n) (let loop ((n n) (i 0) (s 0)) (cond ((zero? n) s) ((even? n) (loop (/ n 2) (+ 1 i) s)) (else (loop (/ (- n 1) 2) (+ 1 i) (A003987bi s (A001317 i))))))) ;; A003987bi implements binary XOR, A003987.
;; Antti Karttunen, Dec 27 2013
  • Scheme
    ;; With memoizing macro definec available in Antti Karttunen's IntSeq-library.
;; Alternative implementation, a recurrence based on entangling even & odd numbers with complementary pair A048724 and A065621:
(definec (A193231 n) (cond ((< n 2) n) ((even? n) (A048724 (A193231 (/ n 2)))) (else (A065621 (+ (A193231 (/ (- n 1) 2)) 1)))))
;; Antti Karttunen, Dec 27 2013

Formula

From Antti Karttunen, Dec 27 2013: (Start)
a(0) = 0, and for any n = 2^a + 2^b + ... + 2^c, a(n) = A001317(a) XOR A001317(b) XOR ... XOR A001317(c), where XOR is bitwise XOR (A003987) and all the exponents a, b, ..., c are distinct, that is, they are the indices of 1-bits in the binary representation of n.
From above it follows, because all terms of A001317 are odd, that A000035(a(n)) = A010060(n) = A000035(a(2n)). Conversely, we also have A010060(a(n)) = A000035(n). Thus the permutation maps any even number to some evil number, A001969 (and vice versa), like it maps any odd number to some odious number, A000069 (and vice versa).
a(0)=0, a(1)=1, and for n>1, a(2n) = A048724(a(n)), a(2n+1) = A065621(1+a(n)). [A recurrence based on entangling even & odd numbers with the complementary pair A048724/A065621]
For all n, abs(a(2n)-a(2n+1)) = 1.
a(A000079(n)) = A001317(n).
(End)
It follows from the first paragraph above that a(A003987(n,k)) = A003987(a(n), a(k)), that is a(n XOR k) = a(n) XOR a(k). - Peter Munn, Nov 27 2019

A091209 Primes whose binary representation encodes a polynomial reducible over GF(2).

Original entry on oeis.org

5, 17, 23, 29, 43, 53, 71, 79, 83, 89, 101, 107, 113, 127, 139, 149, 151, 163, 173, 179, 181, 197, 199, 223, 227, 233, 251, 257, 263, 269, 271, 277, 281, 293, 307, 311, 317, 331, 337, 347, 349, 353, 359, 367, 373, 383, 389, 401, 409, 421, 431, 439, 443, 449, 457, 461, 467, 479, 491, 503, 509, 521, 523
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).
Except for 3, all primes with even Hamming weight (A027699) are terms, see A238186 for the subsequence of primes with odd Hamming weight. [Joerg Arndt and Antti Karttunen, Feb 19 2014]

Links

Crossrefs

Intersection of A000040 and A091242.
Disjoint union of A238186 and (A027699 \ {3}).
Left inverse: A235043.
Cf. A091206 (Primes whose binary expansion encodes a polynomial irreducible over GF(2)), A091212 (Composite, and reducible over GF(2)), A091214 (Composite, but irreducible over GF(2)).
Cf. also A235041-A235042, A234742.

Programs

  • Maple
    Primes:= select(isprime,[2,seq(2*i+1,i=1..1000)]):
filter:= proc(n) local L,x;
    L:= convert(n,base,2);
    Irreduc(add(L[i]*x^(i-1),i=1..nops(L))) mod 2;
end proc:
remove(filter,Primes); # Robert Israel, May 17 2015
  • Mathematica
    Select[Prime[Range[2, 100]], !IrreduciblePolynomialQ[bb = IntegerDigits[#, 2]; Sum[bb[[k]] x^(k-1), {k, 1, Length[bb]}], Modulus -> 2]&] (* Jean-François Alcover, Feb 28 2016 *)
  • PARI
    forprime(p=2, 10^3, if( ! polisirreducible( Mod(1,2)*Pol(binary(p)) ), print1(p,", ") ) ); \\ Joerg Arndt, Feb 19 2014

Formula

a(n) = A000040(A091210(n)) = A091242(A091211(n)).
Other identities. For all n >= 1:
A235043(a(n)) = n. [A235043 works as a left inverse of this sequence.]

A091205 Factorization and index-recursion preserving isomorphism from binary codes of GF(2) polynomials to integers.

Original entry on oeis.org

0, 1, 2, 3, 4, 9, 6, 5, 8, 15, 18, 7, 12, 23, 10, 27, 16, 81, 30, 13, 36, 25, 14, 69, 24, 11, 46, 45, 20, 21, 54, 19, 32, 57, 162, 115, 60, 47, 26, 63, 72, 61, 50, 33, 28, 135, 138, 17, 48, 35, 22, 243, 92, 39, 90, 37, 40, 207, 42, 83, 108, 29, 38, 75, 64, 225, 114, 103
Offset: 0

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Comments

This "deeply multiplicative" bijection is one of the deep variants of A091203 which satisfy most of the same identities as the latter, but it additionally preserves also the structures where we recurse on irreducible polynomial's A014580-index. E.g., we have: A091238(n) = A061775(a(n)). The reason this holds is that when the permutation is restricted to the binary codes for irreducible polynomials over GF(2) (A014580), it induces itself: a(n) = A049084(a(A014580(n))).
On the other hand, when this permutation is restricted to the union of {1} and reducible polynomials over GF(2) (A091242), permutation A245813 is induced.

Links

Crossrefs

Inverse: A091204.
Similar or related permutations: A091203, A106443, A106445, A106447, A235042, A245704, A245813, A245821.
Cf. A000040, A007097, A010051, A014580, A049084, A061775, A091238, A091225, A091226, A091230, A091242.

Programs

  • PARI
    allocatemem(123456789);
v091226 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
n=2; while((n < 2^22), if(isA014580(n), v091226[n] = v091226[n-1]+1, v091226[n] = v091226[n-1]); n++)
A091226(n) = v091226[n];
A091205(n) = if(n<=1,n,if(isA014580(n),prime(A091205(A091226(n))),{my(irfs,t); irfs=subst(lift(factor(Mod(1,2)*Pol(binary(n)))),x,2); irfs[,1]=apply(t->A091205(t),irfs[,1]); factorback(irfs)}));
for(n=0, 8192, write("b091205.txt", n, " ", A091205(n)));
\\ Antti Karttunen, Aug 16 2014

Formula

a(0)=0, a(1)=1. For n that is coding an irreducible polynomial, that is if n = A014580(i), we have a(n) = A000040(a(i)) and for reducible polynomials a(ir_i X ir_j X ...) = a(ir_i) * a(ir_j) * ..., where ir_i = A014580(i), X stands for carryless multiplication of polynomials over GF(2) (A048720) and * for the ordinary multiplication of integers (A004247).
As a composition of related permutations:
a(n) = A245821(A245704(n)).
Other identities.
For all n >= 0, the following holds:
a(A091230(n)) = A007097(n). [Maps iterates of A014580 to the iterates of primes. Permutation A245704 has the same property.]
For all n >= 1, the following holds:
A010051(a(n)) = A091225(n). [After a(1)=1, maps binary representations of irreducible GF(2) polynomials, A014580, bijectively to primes and the binary representations of corresponding reducible polynomials, A091242, to composite numbers, in some order. The permutations A091203, A106443, A106445, A106447, A235042 and A245704 have the same property.]

Extensions

Name changed by Antti Karttunen, Aug 16 2014

A091202 Factorization-preserving isomorphism from nonnegative integers to binary codes for polynomials over GF(2).

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 11, 8, 5, 14, 13, 12, 19, 22, 9, 16, 25, 10, 31, 28, 29, 26, 37, 24, 21, 38, 15, 44, 41, 18, 47, 32, 23, 50, 49, 20, 55, 62, 53, 56, 59, 58, 61, 52, 27, 74, 67, 48, 69, 42, 43, 76, 73, 30, 35, 88, 33, 82, 87, 36, 91, 94, 39, 64, 121, 46, 97, 100, 111, 98
Offset: 0

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Comments

E.g. we have the following identities: A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)), A008683(n) = A091219(a(n)), A014580(n) = a(A000040(n)), A049084(n) = A091227(a(n)).

Links

Crossrefs

Inverse: A091203.
Several variants exist: A235041, A091204, A106442, A106444, A106446.
Cf. also A000005, A091220, A001221, A091221, A001222, A091222, A008683, A091219, A000040, A014580, A048720, A049084, A091227, A245703, A234741.
Cf. also A302023, A302025, A305417, A305427 for other similar permutations.

Programs

  • PARI
    A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305420(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A091202(n) = if(n<=1,n,if(!(n%2),2*A091202(n/2),A305421(A091202(A064989(n))))); \\ Antti Karttunen, Jun 10 2018

Formula

a(0)=0, a(1)=1, a(p_i) = A014580(i) for primes p_i with index i and for composites a(p_i * p_j * ...) = a(p_i) X a(p_j) X ..., where X stands for carryless multiplication of GF(2)[X] polynomials (A048720).
Other identities. For all n >= 1, the following holds:
A091225(a(n)) = A010051(n). [Maps primes to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242. The permutations A091204, A106442, A106444, A106446, A235041 and A245703 have the same property.]
From Antti Karttunen, Jun 10 2018: (Start)
For n <= 1, a(n) = n, for n > 1, a(n) = 2*a(n/2) if n is even, and if n is odd, then a(n) = A305421(a(A064989(n))).
a(n) = A305417(A156552(n)) = A305427(A243071(n)).
(End)

A091203 Factorization-preserving isomorphism from binary codes of GF(2) polynomials to integers.

Original entry on oeis.org

0, 1, 2, 3, 4, 9, 6, 5, 8, 15, 18, 7, 12, 11, 10, 27, 16, 81, 30, 13, 36, 25, 14, 33, 24, 17, 22, 45, 20, 21, 54, 19, 32, 57, 162, 55, 60, 23, 26, 63, 72, 29, 50, 51, 28, 135, 66, 31, 48, 35, 34, 243, 44, 39, 90, 37, 40, 99, 42, 41, 108, 43, 38, 75, 64, 225, 114, 47, 324
Offset: 0

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Comments

E.g. we have the following identities: A000040(n) = a(A014580(n)), A091219(n) = A008683(a(n)), A091220(n) = A000005(a(n)), A091221(n) = A001221(a(n)), A091222(n) = A001222(a(n)), A091225(n) = A010051(a(n)), A091227(n) = A049084(a(n)), A091247(n) = A066247(a(n)).

Links

Crossrefs

Inverse: A091202.
Several variants exist: A235042, A091205, A106443, A106445, A106447.
Cf. also A000005, A000040, A001221, A001222, A004247, A008683, A010051, A014580, A048720, A049084, A066247, A091219, A091220, A091221, A091222, A091225, A091227, A091247, A234741, A234742, A245703, A245704, A278233.
Cf. also A302024, A302026, A305418, A305428 for other similar permutations.

Programs

  • PARI
    A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
A091203(n) = if(n<=1,n,if(!(n%2),2*A091203(n/2),A003961(A091203(A305422(n))))); \\ Antti Karttunen, Jun 10 2018

Formula

a(0)=0, a(1)=1. For n's coding an irreducible polynomial ir_i, that is if n=A014580(i), we have a(n) = A000040(i) and for composite polynomials a(ir_i X ir_j X ...) = p_i * p_j * ..., where p_i = A000040(i) and X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).
Other identities. For all n >= 1, the following holds:
A010051(a(n)) = A091225(n). [After a(1)=1, maps binary representations of irreducible GF(2) polynomials, A014580, to primes and the binary representations of corresponding reducible polynomials, A091242, to composite numbers. The permutations A091205, A106443, A106445, A106447, A235042 and A245704 have the same property.]
From Antti Karttunen, Jun 10 2018: (Start)
For n <= 1, a(n) = n, for n > 1, a(n) = 2*a(n/2) if n is even, and if n is odd, then a(n) = A003961(a(A305422(n))).
a(n) = A005940(1+A305418(n)) = A163511(A305428(n)).
A046523(a(n)) = A278233(n).
(End)
Previous Showing 21-30 of 48 results. Next

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

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