|
Search: id:A106443
|
|
|
| A106443 |
|
Exponent-recursed cross-domain bijection from GF(2)[X] to N. Position of A106456(n) in A075166. |
|
+0
9
|
|
| 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, 512, 57, 162, 55, 60, 23, 26, 63, 72, 29, 50, 51, 28, 135, 66, 31, 768, 35, 34, 19683, 44, 39, 90, 37, 40, 99, 42, 41, 108, 43, 38, 75, 64, 225, 114, 47
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
This map from the multiplicative domain of GF(2)[X] to that of N preserves Catalan-family structures, e.g. A075164(n) = a(A106454(n)), A106453(n) = A075163(a(n)), A106455(n) = A075165(a(n)), A106456(n) = A075166(a(n)), A106457(n) = A075167(a(n)). Shares with A091203 and A106445 the property that maps A014580(n) to A000040(n). Differs from the former for the first time at n=32, where A091203(32)=32, while a(32)=512. Differs from the latter for the first time at n=48, where A106445(48)=48, while a(48)=768.
|
|
LINKS
|
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences that are permutations of the natural numbers
|
|
FORMULA
|
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(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(1+e_j)-1) * a(ir_k)^(a(1+e_k)-1) * ... = A000040(i)^a(e_i) * A000040(j)^(a(1+e_j)-1) * A000040(k)^(a(1+e_k)-1), 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. Here ir_i is the most significant (largest) irreducible polynomial in the factorization of n; its exponent e_i is not incremented before the recursion step, while the exponents of less significant factors 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) = 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) and the square of the second prime is 3^2=9. a(32) = a(A048723(2,5)) = 2^a(5) = 2^9 = 512. a(48) = a(3 X A048723(2,4)) = 3 * 2^(a(4+1)-1) = 3 * 2^(9-1) = 3 * 256 = 768.
|
|
CROSSREFS
|
Inverse: A106442. a(n) = A075164(A106453(n)).
Adjacent sequences: A106440 A106441 A106442 this_sequence A106444 A106445 A106446
Sequence in context: A112095 A091203 A106445 this_sequence A091205 A106447 A060866
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Antti Karttunen (His-Firstname.His-Surname(AT)iki.fi), May 09 2005
|
|
|
Search completed in 0.002 seconds
|
