A091205 -id:A091205 - cp's OEIS frontend

A245821 Permutation of natural numbers: a(n) = A091205(A245703(n)).

1, 2, 3, 4, 5, 9, 7, 6, 8, 12, 11, 15, 23, 81, 18, 10, 17, 30, 13, 162, 27, 36, 19, 24, 16, 25, 38, 46, 37, 45, 31, 135, 14, 20, 50, 57, 47, 69, 21, 55, 83, 115, 419, 87, 60, 210, 61, 42, 54, 26, 90, 28, 29, 35, 32, 63, 171, 52, 59, 138, 113, 180, 111, 48, 88, 39, 41, 621, 72, 22, 953, 230, 103, 207, 126, 64, 33, 243

Offset: 1

Antti Karttunen, Aug 02 2014

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Inverse: A245822.
Other related permutations:  A091205, A245703, A245815.
Fixed points: A245823.
Cf. A000040, A049084, A078442, A049076, A018252, A062298.

allocatemem(234567890);
v014580 = vector(2^18);
v091226 = vector(2^22);
v091242 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; j=0; n=2; while((n < 2^22), if(isA014580(n), i++; v014580[i] = n; v091226[n] = v091226[n-1]+1, j++; v091242[j] = n; v091226[n] = v091226[n-1]); n++);
A014580(n) = v014580[n];
A091226(n) = v091226[n];
A091242(n) = v091242[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)}));
A245703(n) = if(1==n, 1, if(isprime(n), A014580(A245703(primepi(n))), A091242(A245703(n-primepi(n)-1))));
A245821(n) = A091205(A245703(n));
for(n=1, 10001, write("b245821.txt", n, " ", A245821(n)));

(define (A245821 n) (A091205 (A245703 n)))

a(n) = A091205(A245703(n)).
Other identities. For all n >= 1, the following holds:
A078442(a(n)) = A078442(n), A049076(a(n)) = A049076(n). [Preserves "the order of primeness of n"].
a(p_n) = p_{a(n)} where p_n is the n-th prime, A000040(n).
a(n) = A049084(a(A000040(n))). [Thus the same permutation is induced also when it is restricted to primes].
A245815(n) = A062298(a(A018252(n))). [While restriction to nonprimes induces another permutation].

A106447 Doubly-recursed cross-domain bijection from GF(2)[X] to N. Variant of A091205 and A106445.

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, 512, 57, 162, 115, 60, 47, 26, 63, 72, 61, 50, 33, 28, 135, 138, 17, 48, 35, 22, 19683, 92, 39, 90, 37, 40, 207, 42, 83, 108, 29, 38, 75, 64, 225, 114

Offset: 0

Antti Karttunen, May 09 2005

nonn

Differs from A091205 for the first time at n=32, where A091205(32)=32, while a(32)=512. Differs from A106445 for the first time at n=13, where A106445(13)=11, while a(13)=23.

			a(5) = 9, as 5 encodes the GF(2)[X] polynomial x^2+1, which is the square of the second irreducible GF(2)[X] polynomial x+1 (encoded as 3), a(2)=2 and the square of the second prime is 3^2=9. a(13) = a(A014580(5)) = A000040(a(5)) = A000040(9) = 23. a(32) = a(A048723(2,5)) = a(2)^a(5) = 2^9 = 512. a(48) = a(3 X A048723(2,4)) = a(3) * a(2)^a(4) = 3 * 2^4 = 3 * 16 = 48.

Inverse: A106446. Variant: A091205.

a(0)=0, a(1)=1. For irreducible GF(2)[X] polynomials ir_i with index i (i.e. A014580(i)), a(ir_i) = A000040(a(i)) and for composite polynomials n = A048723(ir_i, e_i) X A048723(ir_j, e_j) X A048723(ir_k, e_k) X ..., a(n) = a(ir_i)^a(e_i) * a(ir_j)^a(e_j) * a(ir_k)^a(e_k) * ... = A000040(a(i))^a(e_i) * A000040(a(j))^a(e_j) * A000040(a(k))^a(e_k), where X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and A048723(n, y) raises the n-th GF(2)[X] polynomial to the y:th power, while * is the ordinary multiplication and ^ is the ordinary exponentiation.

A245813 Permutation of natural numbers induced when A091205 is restricted to {1} and binary codes for polynomials reducible over GF(2): a(1) = 1, a(n) = A062298(A091205(A091242(n-1))).

Original entry on oeis.org

1, 2, 5, 3, 4, 9, 11, 7, 6, 18, 10, 59, 20, 25, 16, 8, 50, 15, 32, 31, 12, 13, 38, 21, 41, 125, 85, 43, 17, 45, 52, 35, 22, 19, 103, 105, 33, 24, 14, 190, 68, 27, 66, 28, 161, 29, 80, 26, 54, 46, 177, 84, 258, 34, 180, 64, 90, 70, 507, 37, 196, 96, 39, 110, 430, 92, 78, 75, 600, 48, 40, 82, 213, 218, 71, 23, 87, 72, 51, 132, 30

Offset: 1

Antti Karttunen, Aug 16 2014

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Inverse: A245814.
Cf. A062298, A091242.
Related permutations: A091205, A245815, A245820.

allocatemem(234567890);
v091226 = vector(2^22);
v091242 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; j=0; n=2; while((n < 2^22), if(isA014580(n), i++; v091226[n] = v091226[n-1]+1, j++; v091242[j] = n; v091226[n] = v091226[n-1]); n++);
A062298(n) = n-primepi(n);
A091226(n) = v091226[n];
A091242(n) = v091242[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)}));
A245813(n) = if(n<=1, n, A062298(A091205(A091242(n-1))));
for(n=1, 10001, write("b245813.txt", n, " ", A245813(n)));

(define (A245813 n) (if (<= n 1) n (A062298 (A091205 (A091242 (- n 1))))))

a(1) = 1, and for n > 1, a(n) = A062298(A091205(A091242(n-1))).
As a composition of related permutations:
a(n) = A245815(A245820(n)).

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 6, 6, 7, 6, 7, 6, 6, 7, 6, 6, 7, 6, 7, 7, 6, 6, 7, 7, 6, 7, 6, 7, 8, 7, 7, 7, 7, 8, 7, 7, 6, 8, 8, 7, 7, 7, 6, 8, 7, 7, 8, 7, 8, 8, 6, 7, 8, 8, 7, 8, 7, 7, 9, 7, 8, 8, 7, 8, 9, 7, 7, 8, 8, 7, 8, 8, 7, 9, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 7, 8, 8, 8, 9, 7, 7, 9

Offset: 1

N. J. A. Sloane, Jun 22 2001

nonn

Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it. (Cf. A061773 for illustration).

Each n occurs A000081(n) times.

			a(4) = 3 because the rooted tree corresponding to the Matula-Goebel number 4 is "V", which has one root-node and two leaf-nodes, three in total.
See also the illustrations in A061773.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Keith Briggs, Matula numbers and rooted trees
Emeric Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

One more than A196050.
Sum of entries in row n of irregular table A214573.
Number of entries in row n of irregular tables A182907, A206491, A206495 and A212620.
One less than the number of entries in row n of irregular tables A184187, A193401 and A193403.
Cf. A005517 (the position of the first occurrence of n).
Cf. A005518 (the position of the last occurrence of n).
Cf. A091233 (their difference plus one).
Cf. A214572 (Numbers k such that a(k) = 8).
Cf. also A000081, A061773, A049084, A020639, A049076, A078442, A091238, A091204, A091205, A109082, A127301, A109129, A193402, A193405, A193406, A196047, A196068, A198333, A206487, A206494, A206496, A214569, A214571, A213670, A214568, A228599, A245817, A245818.
Cf. also A075166, A075167, A216648, A216649.

import Data.List (genericIndex)
a061775 n = genericIndex a061775_list (n - 1)
a061775_list = 1 : g 2 where
   g x = y : g (x + 1) where
      y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v - 1
          where t = a049084 x; u = a020639 x; v = x `div` u
-- Reinhard Zumkeller, Sep 03 2013

with(numtheory): a := proc (n) local u, v: u := n-> op(1, factorset(n)): v := n-> n/u(n): if n = 1 then 1 elif isprime(n) then 1+a(pi(n)) else a(u(n))+a(v(n))-1 end if end proc: seq(a(n), n = 1..108); # Emeric Deutsch, Sep 19 2011

a[n_] := Module[{u, v}, u = FactorInteger[#][[1, 1]]&; v = #/u[#]&; If[n == 1, 1, If[PrimeQ[n], 1+a[PrimePi[n]], a[u[n]]+a[v[n]]-1]]]; Table[a[n], {n, 108}] (* Jean-François Alcover, Jan 16 2014, after Emeric Deutsch *)

A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs,t,i); pfs=factor(n); pfs[,1]=apply(t->A061775(t),pfs[,1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i,1]*pfs[i,2])}));
for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));
\\ Antti Karttunen, Aug 16 2014

from functools import lru_cache
from sympy import isprime, factorint, primepi
@lru_cache(maxsize=None)
def A061775(n):
    if n == 1: return 1
    if isprime(n): return 1+A061775(primepi(n))
    return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022

a(1) = 1; if n = p_t (= the t-th prime), then a(n) = 1+a(t); if n = uv (u,v>=2), then a(n) = a(u)+a(v)-1.
a(n) = A091238(A091204(n)). - Antti Karttunen, Jan 2004
a(n) = A196050(n)+1. - Antti Karttunen, Aug 16 2014

More terms from David W. Wilson, Jun 25 2001

Extended by Emeric Deutsch, Sep 19 2011

A091247 Characteristic function of A091242: 1 if the n-th GF(2)[X] polynomial is reducible, 0 otherwise.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

Antti Karttunen, Table of n, a(n) for n = 0..65537
A. Karttunen, Scheme-program for computing this sequence.
Index entries for characteristic functions
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A066247, A091203, A091205, A091246.

Complementary to A091225. Partial sums give A091245.

a(n) = if (n<2, 0, ! polisirreducible(Mod(1,2)*Pol(binary(n)))); \\ Michel Marcus, Apr 12 2015

a(n) = A066247(A091203(n)) = A066247(A091205(n)).

A091225 Characteristic function of A014580: 1 if the n-th GF(2)[X] polynomial is irreducible, 0 otherwise.

Original entry on oeis.org

0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

Antti Karttunen, Table of n, a(n) for n = 0..100000
A. Karttunen, Scheme-program for computing this sequence
Index entries for characteristic functions
Index entries for sequences operating on GF(2)[X]-polynomials

a(n) = A010051(A091203(n)) = A010051(A091205(n)). Partial sums give A091226. Cf. A091227. Complementary to A091247.

a(n) = polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ Michel Marcus, Nov 11 2017

Data section extended up to a(120) by Antti Karttunen, Jan 01 2023

A091222 Number of irreducible polynomials dividing n-th GF(2)[X]-polynomial, counted with multiplicity.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 4, 4, 3, 1, 4, 2, 2, 2, 4, 1, 2, 3, 3, 2, 4, 1, 5, 2, 5, 2, 4, 1, 2, 3, 5, 1, 3, 2, 3, 4, 3, 1, 5, 2, 2, 5, 3, 2, 4, 1, 4, 3, 3, 1, 5, 1, 2, 3, 6, 4, 3, 1, 6, 2, 3, 2, 5, 1, 2, 4, 3, 2, 4, 2, 6, 2, 2, 3, 4, 6, 3, 1, 4, 2, 5, 1, 4, 2, 2, 3, 6, 1, 3, 3, 3, 3, 6

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A000051, A001222, A091203, A091205, A091248.

Cf. A256170.

for n from 1 to 1000 do
  L:= convert(n,base,2);
  P:= add(L[i]*X^(i-1),i=1..nops(L));
  R:= Factors(P) mod 2;
  a[n]:= add(r[2],r=R[2]);
od:
seq(a[n],n=1..1000); # Robert Israel, Jun 07 2015

a(n)=my(fm=factor(Pol(binary(n))*Mod(1, 2))); sum(k=1, #fm~, fm[k, 2]) \\ Franklin T. Adams-Watters, Jun 07 2015

a(n) = A001222(A091203(n)) = A001222(A091205(n)).

a(A000051(n)) = A091248(n).

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

Antti Karttunen, Jan 03 2004

nonn

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

Antti Karttunen, Table of n, a(n) for n = 0..8192
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials
Index entries for sequences that are permutations of the natural numbers

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.

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

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)

A278233 Filter-sequence for GF(2)[X]-factorization: sequence that gives the least natural number with the same prime signature that (0, 1)-polynomial encoded in the binary expansion of n has when it is factored over GF(2).

Original entry on oeis.org

1, 2, 2, 4, 4, 6, 2, 8, 6, 12, 2, 12, 2, 6, 8, 16, 16, 30, 2, 36, 4, 6, 6, 24, 2, 6, 12, 12, 6, 24, 2, 32, 6, 48, 6, 60, 2, 6, 12, 72, 2, 12, 6, 12, 24, 30, 2, 48, 6, 6, 32, 12, 6, 60, 2, 24, 12, 30, 2, 72, 2, 6, 12, 64, 36, 30, 2, 144, 4, 30, 6, 120, 2, 6, 24, 12, 6, 60, 6, 144, 4, 6, 30, 36, 64, 30, 2, 24, 6, 120, 2, 60, 6, 6, 12, 96, 2, 30, 12, 12, 30, 96, 2

Offset: 1

Antti Karttunen, Nov 16 2016

nonn

a(n) = the least number with the same prime signature as A091203(n).
This sequence works as an A046523-analog in the polynomial ring GF(2)[X] and can be used as a filter which matches with (and thus detects) any sequence in the database where a(n) depends only on the exponents of irreducible factors when the polynomial corresponding to n (via base-2 encoding) is factored over GF(2). These sequences are listed in the Crossrefs section, "Sequences that partition N into ...".
Matching in this context means that the sequence a matches with the sequence b iff for all i, j: a(i) = a(j) => b(i) = b(j). In other words, iff the sequence b partitions the natural numbers to the same or coarser equivalence classes (as/than the sequence a) by the distinct values it obtains.

			3 is "11" in binary, encodes polynomial x + 1, and 7 is "111" in binary, encodes polynomial x^2 + x + 1, both which are irreducible over GF(2). We can multiply their codes with carryless multiplication A048720 as A048720(3,7) = 9, A048720(9,3) = 27, A048720(9,7) = 63. Now a(27) = a(63) because the exponents occurring in both codes 27 and 63 are one 1 and two 2's, and their order is not significant when computing prime signature. Moreover a(27) = a(63) = 12 because that is the least number with a prime signature (1,2) in the more familiar domain of natural numbers.
a(25) = 2, because 25 is "11001" in binary, encoding polynomial x^4 + x^3 + 1, which is irreducible in the ring GF(2)[X], i.e., 25 is in A014580, whose initial term is 2.

Cf. A014580 (gives the positions of 2's), A048720, A057889, A091203, A091205, A193231, A235042, A278231, A278238, A278239.
Similar filtering sequences: A046523, A278222, A278226, A278236, A278243.
Sequences that partition N into same or coarser equivalence classes: A091220, A091221, A091222, A106493, A106494.
Cf. also A304529, A304751, A305788 (rgs-transform), A305789.

A278233(n) = { my(p=0, f=vecsort((factor(Pol(binary(n))*Mod(1, 2))[, 2]), , 4)); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ Antti Karttunen, Jun 10 2018

(define (A278233 n) (A046523 (A091203 n)))

a(n) = A046523(A091203(n)) = A046523(A091205(n)) = A046523(A235042(n)). [Because of the "sorting" essentially performed by A046523, any map from GF(2)[X] to Z can be used, as long as it is fully (cross-)multiplicative and preserves also the exponents intact.]
Other identities. For all n >= 1:
a(A014580(n)) = 2.
a(n) = a(A057889(n)) = a(A193231(n)).
a(A000695(n)) = A278238(n).
a(A277699(n)) = A278239(n).

A235042 Factorization-preserving bijection from GF(2)[X]-polynomials to nonnegative integers, version which fixes the elements that are irreducible in both semirings.

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, 5, 26, 63, 28, 33, 54, 31, 32, 93, 162, 91, 84, 37, 38, 99, 72, 41, 98, 15, 44, 189, 78, 47, 48, 77, 10, 243, 52, 57, 126, 17, 56, 117, 66, 59, 108, 61, 62, 147, 64, 441

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Like A091203 this is a factorization-preserving isomorphism from GF(2)[X]-polynomials to integers. The former are encoded in the binary representation of n like this: n=11, '1011' in binary, stands for polynomial x^3+x+1, n=25, '11001' in binary, stands for polynomial x^4+x^3+1. However, this version does not map the irreducible GF(2)[X] polynomials (A014580) straight to the primes (A000040), but instead fixes the intersection of those two sets (A091206), and maps the elements in their set-wise difference A014580 \ A000040 (= A091214) in numerical order to the set-wise difference A000040 \ A014580 (= A091209).
The composite values are defined by the multiplicativity. E.g., we have a(A048724(n)) = 3*a(n) and a(A001317(n)) = A000244(n) = 3^n for all n.
This map satisfies many of the same identities as A091203, e.g., we have 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)) and A091247(n) = A066247(a(n)) for all n >= 1.

			Here (t X u) = A048720(t,u):
a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206.
a(4) = a(2 X 2) = a(2)*a(2) = 2*2 = 4.
a(5) = a(3 X 3) = a(3)*a(3) = 3*3 = 9.
a(9) = a(3 X 7) = a(3)*a(7) = 3*7 = 21.
a(10) = a(2 X 3 X 3) = a(2)*a(3)*a(3) = 2*3*3 = 18.
a(15) = a(3 X 3 X 3) = a(3)^3 = 3^3 = 27.
a(17) = a(3 X 3 X 3 X 3) = a(3)^4 = 3^4 = 81.
a(21) = a(7 X 7) = a(7)*a(7) = 7*7 = 49.
a(25) = 5, as 25 is the first term of A091214 and 5 is the first term of A091209.
a(50) = a(2 X 25) = a(2)*a(25) = 2*5 = 10.

Inverse: A235041. Fixed points: A235045.
Cf. A010051, A004247, A091225, A091209, A235044.
Similar cross-multiplicative permutations: A091203, A091205, A106443, A106445, A106447.

a(0)=0, a(1)=1, a(p) = p for those irreducible GF(2)[X]-polynomials whose binary encoding is a prime (i.e., p is in A091206), and for the rest of irreducible GF(2)[X]-polynomials (those which are encoded by a composite natural number, i.e., q is in A091214), a(q) = A091209(A235044(q)), and for reducible polynomials, a(i X j X k X ...) = a(i) * a(j) * a(k) * ..., where each i, j, k, ... is in A014580, X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and * for the ordinary multiplication of integers (A004247).

cp's OEIS Frontend

A245821 Permutation of natural numbers: a(n) = A091205(A245703(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A106447 Doubly-recursed cross-domain bijection from GF(2)[X] to N. Variant of A091205 and A106445.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A245813 Permutation of natural numbers induced when A091205 is restricted to {1} and binary codes for polynomials reducible over GF(2): a(1) = 1, a(n) = A062298(A091205(A091242(n-1))).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A091247 Characteristic function of A091242: 1 if the n-th GF(2)[X] polynomial is reducible, 0 otherwise.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A091225 Characteristic function of A014580: 1 if the n-th GF(2)[X] polynomial is irreducible, 0 otherwise.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A091222 Number of irreducible polynomials dividing n-th GF(2)[X]-polynomial, counted with multiplicity.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

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

Views

Author

Keywords

Comments

Links