

A106442


Exponentrecursed crossdomain bijection from N to GF(2)[X]. Position of A075166(n) in A106456.


11



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, 128, 23, 50, 49, 20, 55, 62, 53, 56, 59, 58, 61, 52, 27, 74, 67, 192, 69, 42, 43, 76, 73, 30, 35, 88, 33, 82, 87, 36, 91, 94, 39, 64, 121, 46, 97, 100, 111, 98
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

This map from the multiplicative domain of N to that of GF(2)[X] preserves Catalanfamily structures, e.g. A106454(n) = a(A075164(n)), A075163(n) = A106453(a(n)), A075165(n) = A106455(a(n)), A075166(n) = A106456(a(n)), A075167(n) = A106457(a(n)). Shares with A091202 and A106444 the property that maps A000040(n) to A014580(n). Differs from the former for the first time at n=32, where A091202(32)=32, while a(32)=128. Differs from the latter for the first time at n=48, where A106444(48)=48, while a(48)=192.


LINKS

Table of n, a(n) for n=0..70.
A. Karttunen, Schemeprogram for computing this sequence.
Index entries for sequences that are permutations of the natural numbers


FORMULA

a(0)=0, a(1)=1, a(p_i) = A014580(i) for primes p_i with index i and for composites n = p_i^e_i * p_j^e_j * p_k^e_k * ..., a(n) = A048723(a(p_i), a(e_i)) X A048723(a(p_j), a(1+e_j)1) X A048723(a(p_k), a(1+e_k)1) X ..., where X stands for carryless multiplication of GF(2)[X] polynomials (A048720) and A048723(n, y) raises the nth GF(2)[X] polynomial to the y:th power. Here p_i is the most significant prime in the factorization of n; its exponent e_i is not incremented before the recursion step, while the exponents of less significant primes e_j, e_k, ... are incremented by one before recursing and the result of the recursion is decremented by one before use.


EXAMPLE

a(5) = 7, as 5 is the 3rd prime and the third irreducible GF(2)[X] polynomial x^2+x+1 is encoded as A014580(3) = 7. a(32) = a(2^5) = A048723(A014580(1),a(5)) = A048723(2,7) = 128. a(48) = a(3 * 2^4) = 3 X A048723(2,a(4+1)1) = 3 X A048723(2,71) = 3 X 64 = 192.


CROSSREFS

Inverse: A106443. a(n) = A106454(A075163(n)).
Sequence in context: A125595 A091202 A106444 * A091204 A106446 A036467
Adjacent sequences: A106439 A106440 A106441 * A106443 A106444 A106445


KEYWORD

nonn


AUTHOR

Antti Karttunen, May 09 2005


STATUS

approved



