A106456 -id:A106456 - cp's OEIS frontend

A106442 Exponent-recursed cross-domain bijection from N to GF(2)[X]. Position of A075166(n) in A106456.

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

Offset: 0

Antti Karttunen, May 09 2005

nonn

This map from the multiplicative domain of N to that of GF(2)[X] preserves Catalan-family 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.

			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,7-1) = 3 X 64 = 192.

Inverse: A106443. a(n) = A106454(A075163(n)).

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 n-th 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.

A106443 Exponent-recursed cross-domain bijection from GF(2)[X] to N. Position of A106456(n) in A075166.

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, 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

Offset: 0

Antti Karttunen, May 09 2005

nonn

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.

			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.

Inverse: A106442. a(n) = A075164(A106453(n)).

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.

A106455 Sequence A106456 interpreted as binary numbers and converted to decimal.

Original entry on oeis.org

0, 2, 10, 12, 50, 44, 42, 52, 178, 204, 170, 180, 682, 172, 210, 56, 226, 716, 2730, 820, 202, 684, 2738, 184, 10922, 2732, 722, 692, 690, 844, 43690, 228, 174770, 908, 2762, 2868, 174762, 10924, 2770, 824, 699050, 812, 43698, 2740, 738, 10956

Offset: 1

Antti Karttunen, May 09 2005

A. Karttunen, Scheme-program for computing this sequence.

a(n) = A075165(A106443(n)). Permutation of A014486. Same sequence shown in binary: A106456. The binary width of each term / 2 is given by A106457. GF(2)[X]-analog of A075165.

A106457 Number of edges in each rooted plane tree produced with the GF(2)[X] factorization unranking algorithm presented in A106456.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 4, 4, 3, 4, 5, 6, 5, 4, 5, 6, 4, 7, 6, 5, 5, 5, 5, 8, 4, 9, 5, 6, 6, 9, 7, 6, 5, 10, 5, 8, 6, 5, 7, 11, 5, 5, 8, 5, 7, 7, 6, 12, 5, 7, 6, 13, 6, 14, 9, 5, 4, 6, 10, 15, 6, 5, 7, 15, 6, 16, 10, 7, 8, 14, 7, 8, 6, 6, 11, 6, 6, 5, 9, 17, 6, 13, 6, 18, 8, 9, 12

Offset: 1

Antti Karttunen, May 09 2005

nonn

Also the digital length of A106456(n)/2. Each value v occurs A000108(v) times.

A. Karttunen, Scheme-program for computing this sequence.

a(n) = A075167(A106443(n)). Permutation of A072643.

A075166 Natural numbers mapped to Dyck path encodings of the rooted plane trees obtained by recursing on the exponents of the prime factorization of n.

Original entry on oeis.org

0, 10, 1010, 1100, 101010, 101100, 10101010, 110100, 110010, 10101100, 1010101010, 10110100, 101010101010, 1010101100, 10110010, 111000, 10101010101010, 11001100, 1010101010101010, 1010110100, 1010110010

Offset: 1

Antti Karttunen, Sep 13 2002

Note that we recurse on the exponent + 1 for all other primes except the largest one in the factorization. Thus for 6 = 3^1 * 2^1 we construct a tree by joining trees 1 and 2 with a new root node, for 7 = 7^1 * 5^0 * 3^0 * 2^0 we join four 1-trees (single leaves) with a new root node, for 8 = 2^3 we add a single edge below tree 3 and for 9 = 3^2 * 2^0 we join trees 2 and 1, to get the mirror image of tree 6. Compare to Matula/Goebel numbering of (unoriented) rooted trees as explained in A061773.

			The rooted plane trees encoded here are:
.....................o...............o.........o...o..o.......
.....................|...............|..........\./...|.......
.......o....o...o....o....o.o.o..o...o.o.o.o.o...o....o...o...
.......|.....\./.....|.....\|/....\./...\|.|/....|.....\./....
*......*......*......*......*......*......*......*......*.....
1......2......3......4......5......6......7......8......9.....

A. Karttunen, Alternative Catalan Orderings (with the complete Scheme source)
A. Karttunen, Complete Scheme-program for computing this sequence.

Permutation of A063171. Same sequence shown in decimal: A075165. The digital length of each term / 2 (the number of o-nodes in the corresponding trees) is given by A075167. Cf. A075171, A007088.

a(n) = A007088(A075165(n)) = A106456(A106442(n)). - Antti Karttunen, May 09 2005

A106454 Position of A014486(n-1) in A106455.

Original entry on oeis.org

1, 2, 3, 4, 7, 6, 5, 8, 16, 11, 14, 9, 12, 24, 21, 10, 15, 128, 64, 17, 32, 256, 65536, 13, 22, 29, 28, 56, 49, 18, 27, 192, 96, 45, 48, 384, 98304, 69, 42, 63, 20, 40, 107, 30, 255, 2048, 16384, 85, 512, 4096, 16777216, 273, 34, 51, 2097152, 1024, 257, 32768

Offset: 1

Antti Karttunen, May 09 2005

nonn

See A106456.

Inverse: A106453. a(n) = A106442(A075164(n)). a(n) = A106452(n-1)+1. GF(2)[X]-analog of A075164.

A106453 Position of A106455(n) in A014486 plus one.

Original entry on oeis.org

1, 2, 3, 4, 7, 6, 5, 8, 12, 16, 10, 13, 24, 11, 17, 9, 20, 30, 66, 41, 15, 25, 68, 14, 198, 67, 31, 27, 26, 44, 627, 21, 2059, 53, 71, 83, 2057, 199, 73, 42, 6919, 39, 629, 69, 34, 204, 23715, 35, 29, 628, 54, 201, 200, 86, 82501, 28, 205, 72, 290513, 125, 1033413

Offset: 1

Antti Karttunen, May 09 2005

nonn

See A106456.

Inverse: A106454. a(n) = A075163(A106443(n)). a(n) = A106451(n-1)+1. GF(2)[X]-analog of A075163.

A106451 Position of A106455(n+1) in A014486.

Original entry on oeis.org

0, 1, 2, 3, 6, 5, 4, 7, 11, 15, 9, 12, 23, 10, 16, 8, 19, 29, 65, 40, 14, 24, 67, 13, 197, 66, 30, 26, 25, 43, 626, 20, 2058, 52, 70, 82, 2056, 198, 72, 41, 6918, 38, 628, 68, 33, 203, 23714, 34, 28, 627, 53, 200, 199, 85, 82500, 27, 204, 71, 290512, 124, 1033412

Offset: 0

Antti Karttunen, May 09 2005

nonn

See A106456.

Inverse: A106452. a(n) = A106453(n+1)-1. GF(2)[X]-analog of A075161.

A106452 Position of A014486(n) in A106455, minus one.

Original entry on oeis.org

0, 1, 2, 3, 6, 5, 4, 7, 15, 10, 13, 8, 11, 23, 20, 9, 14, 127, 63, 16, 31, 255, 65535, 12, 21, 28, 27, 55, 48, 17, 26, 191, 95, 44, 47, 383, 98303, 68, 41, 62, 19, 39, 106, 29, 254, 2047, 16383, 84, 511, 4095, 16777215, 272, 33, 50, 2097151, 1023, 256, 32767

Offset: 0

Antti Karttunen, May 09 2005

nonn

See A106456. The next term, a(58) = 340282366920938463463374607431768211455 = (2^128) - 1 as A063171(58) = 1110101000, 11010100 = A063171(17), a(17)=127 and 127+1 = 128.

Inverse: A106451. a(n) = A106454(n+1)-1. GF(2)[X]-analog of A075162.

cp's OEIS Frontend

A106442 Exponent-recursed cross-domain bijection from N to GF(2)[X]. Position of A075166(n) in A106456.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A106443 Exponent-recursed cross-domain bijection from GF(2)[X] to N. Position of A106456(n) in A075166.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A106455 Sequence A106456 interpreted as binary numbers and converted to decimal.

Views

Author

Keywords

Links

Crossrefs

A106457 Number of edges in each rooted plane tree produced with the GF(2)[X] factorization unranking algorithm presented in A106456.

Views

Author

Keywords

Comments

Links

Crossrefs

A075166 Natural numbers mapped to Dyck path encodings of the rooted plane trees obtained by recursing on the exponents of the prime factorization of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A106454 Position of A014486(n-1) in A106455.

Views

Author

Keywords

Comments

Links

Crossrefs

A106453 Position of A106455(n) in A014486 plus one.

Views

Author

Keywords

Comments

Links

Crossrefs

A106451 Position of A106455(n+1) in A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

A106452 Position of A014486(n) in A106455, minus one.

Views

Author

Keywords

Comments

Links

Crossrefs