| Displaying 1-6 of 6 results found.
page
1
Factorization-preserving isomorphism from nonnegative integers to binary codes for polynomials over GF(2).
+10
21
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
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:
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))). (End)
PROG
(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));
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); };
CROSSREFS
Cf. also A000005, A091220, A001221, A091221, A001222, A091222, A008683, A091219, A000040, A014580, A048720, A049084, A091227, A245703, A234741.
Permutation of natural numbers: a(1) = 1, a(p_n) = A014580(a(n)), a(c_n) = A091242(a(n)), where p_n = n-th prime, c_n = n-th composite number and A014580(n) and A091242(n) are binary codes for n-th irreducible and n-th reducible polynomials over GF(2), respectively.
+10
20
1, 2, 3, 4, 7, 5, 11, 6, 8, 12, 25, 9, 13, 17, 10, 14, 47, 18, 19, 34, 15, 20, 31, 24, 16, 21, 62, 26, 55, 27, 137, 45, 22, 28, 42, 33, 37, 23, 29, 79, 59, 35, 87, 71, 36, 166, 41, 58, 30, 38, 54, 44, 61, 49, 32, 39, 99, 76, 319, 46, 91, 108, 89, 48, 200, 53, 97, 75, 40, 50, 203, 70, 67, 57, 78, 64, 43, 51
COMMENTS
All the permutations A091202, A091204, A106442, A106444, A106446, A235041 share the same property that primes ( A000040) are mapped bijectively to the binary representations of irreducible GF(2) polynomials ( A014580) but while they determine the mapping of composites ( A002808) to the corresponding binary codes of reducible polynomials ( A091242) by a simple multiplicative rule, this permutation employs index-recursion also in that case.
FORMULA
a(1) = 1, a(p_n) = A014580(a(n)) and a(c_n) = A091242(a(n)), where p_n is the n-th prime, A000040(n) and c_n is the n-th composite, A002808(n). As a composition of related permutations:
Other identities. For all n >= 1, the following holds:
PROG
(PARI)
allocatemem(123456789);
a014580 = vector(2^18);
a091242 = vector(2^22);
i=0; j=0; n=2; while((n < 2^22), if(isA014580(n), i++; a014580[i] = n, j++; a091242[j] = n); n++)
A245703(n) = if(1==n, 1, if(isprime(n), a014580[ A245703(primepi(n))], a091242[ A245703(n-primepi(n)-1)]));
for(n=1, 10001, write("b245703.txt", n, " ", A245703(n))); (Scheme, with memoization-macro definec)
CROSSREFS
Similar or related permutations: A091202, A091204, A106442, A106444, A106446, A235041, A135141, A245701, A245702, A245821, A245822, A244987, A245450.
Factorization and index-recursion preserving isomorphism from nonnegative integers to polynomials over GF(2).
+10
16
0, 1, 2, 3, 4, 7, 6, 11, 8, 5, 14, 25, 12, 19, 22, 9, 16, 47, 10, 31, 28, 29, 50, 13, 24, 21, 38, 15, 44, 61, 18, 137, 32, 43, 94, 49, 20, 55, 62, 53, 56, 97, 58, 115, 100, 27, 26, 37, 48, 69, 42, 113, 76, 73, 30, 79, 88, 33, 122, 319, 36, 41, 274, 39, 64, 121, 86, 185
COMMENTS
This "deeply multiplicative" isomorphism is one of the deep variants of A091202 which satisfies most of the same identities as the latter, but it additionally preserves also the structures where we recurse on prime's index. E.g. we have: A091230(n) = a( A007097(n)) and A061775(n) = A091238(a(n)). This is because the permutation induces itself when it is restricted to the primes: a(n) = A091227(a( A000040(n))). On the other hand, when this permutation is restricted to the nonprime numbers ( A018252), permutation A245814 is induced.
FORMULA
a(0)=0, a(1)=1, a(p_i) = A014580(a(i)) for primes 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). As a composition of related permutations:
Other identities.
For all n >= 0, the following holds:
For all n >= 1, the following holds:
PROG
(PARI)
v014580 = vector(2^18); A014580(n) = v014580[n]; i=0; n=2; while((n < 2^22), if(isA014580(n), i++; v014580[i] = n); n++)
A091204(n) = if(n<=1, n, if(isprime(n), A014580( A091204(primepi(n))), {my(pfs, t, bits, i); pfs=factor(n); pfs[, 1]=apply(t->Pol(binary( A091204(t))), pfs[, 1]); sum(i=1, #bits=Vec(factorback(pfs))%2, bits[i]<<(#bits-i))}));
for(n=0, 8192, write("b091204.txt", n, " ", A091204(n)));
CROSSREFS
Cf. A000040, A007097, A010051, A014580, A018252, A048720, A061775, A091225, A091230, A091238, A091242.
Factorization-preserving bijection from nonnegative integers to GF(2)[X]-polynomials, version which fixes the elements that are irreducible in both semirings.
+10
14
0, 1, 2, 3, 4, 25, 6, 7, 8, 5, 50, 11, 12, 13, 14, 43, 16, 55, 10, 19, 100, 9, 22, 87, 24, 321, 26, 15, 28, 91, 86, 31, 32, 29, 110, 79, 20, 37, 38, 23, 200, 41, 18, 115, 44, 125, 174, 47, 48, 21, 642, 89, 52, 117, 30, 227, 56, 53, 182, 59, 172, 61, 62, 27, 64
COMMENTS
Like A091202 this is a factorization-preserving isomorphism from integers to GF(2)[X]-polynomials. The latter 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 primes ( A000040) straight to the irreducible GF(2)[X] polynomials ( A014580), but instead fixes the intersection of those two sets ( A091206), and maps the elements in their set-wise difference A000040 \ A014580 (= A091209) in numerical order to the set-wise difference A014580 \ A000040 (= A091214). The composite values are defined by the multiplicativity. E.g., we have a(3n) = A048724(a(n)) and a(3^n) = A001317(n) for all n.
FORMULA
a(0)=0, a(1)=1, a(p) = p for those primes p whose binary representations encode also irreducible GF(2)[X]-polynomials (i.e., p is in A091206), and for the rest of the primes q (those whose binary representation encode composite GF(2)[X]-polynomials, i.e., q is in A091209), a(q) = A091214( A235043(q)), and for composite natural numbers, a(p * q * r * ...) = a(p) X a(q) X a(r) X ..., where p, q, r, ... are primes and X stands for the carryless multiplication ( A048720) of GF(2)[X] polynomials encoded as explained in the Comments section.
EXAMPLE
a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206. a(4) = a(2*2) = a(2) X a(2) = 2 X 2 = 4.
a(9) = a(3*3) = a(3) X a(3) = 3 X 3 = 5.
a(5) = 25, as 5 is the first term of A091209 and 25 is the first term of A091214. a(10) = a(2*5) = a(2) X a(5) = 2 X 25 = 50.
Similarly, a(17) = 55, as 17 is the second term of A091209 and 55 is the second term of A091214. a(21) = a(3*7) = a(3) X a(7) = 3 X 7 = 9.
Exponent-recursed cross-domain bijection from N to GF(2)[X]. Variant of A091202 and A106442.
+10
10
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, 48, 69, 42, 43, 76, 73, 30, 35, 88, 33, 82, 87, 36, 91, 94, 39, 64, 121, 46, 97, 100, 111
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(e_j)) X A048723(a(p_k), a(e_k)) 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.
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)) = 3 X A048723(2,4) = 3 X 16 = 48.
Doubly-recursed cross-domain bijection from GF(2)[X] to N. Variant of A091205 and A106445.
+10
6
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
COMMENTS
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.
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(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.
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), 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.
Search completed in 0.009 seconds
|