cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 11 results. Next

A106444 Exponent-recursed cross-domain bijection from N to GF(2)[X]. Variant of A091202 and A106442.

Original entry on oeis.org

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
Offset: 0

Views

Author

Antti Karttunen, May 09 2005

Keywords

Comments

This map from the multiplicative domain of N to that of GF(2)[X] preserves 'superfactorized' structures, e.g. A106490(n) = A106493(a(n)), A106491(n) = A106494(a(n)), A064372(n) = A106495(a(n)). Shares with A091202 and A106442 the property that maps A000040(n) to A014580(n). Differs from A091202 for the first time at n=32, where A091202(32)=32, while a(32)=128. Differs from A106442 for the first time at n=48, where A106442(48)=192, while a(48)=48. Differs from A106446 for the first time at n=11, where A106446(11)=25, while a(11)=13.

Examples

			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.

Links

Crossrefs

Inverse: A106445.

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.

A091202 Factorization-preserving isomorphism from nonnegative integers to binary codes for polynomials over GF(2).

Original entry on oeis.org

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
Offset: 0

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Comments

E.g. we have the following identities: A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)), A008683(n) = A091219(a(n)), A014580(n) = a(A000040(n)), A049084(n) = A091227(a(n)).

Links

Crossrefs

Inverse: A091203.
Several variants exist: A235041, A091204, A106442, A106444, A106446.
Cf. also A000005, A091220, A001221, A091221, A001222, A091222, A008683, A091219, A000040, A014580, A048720, A049084, A091227, A245703, A234741.
Cf. also A302023, A302025, A305417, A305427 for other similar permutations.

Programs

  • 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));
A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
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); };
A091202(n) = if(n<=1,n,if(!(n%2),2*A091202(n/2),A305421(A091202(A064989(n))))); \\ Antti Karttunen, Jun 10 2018

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:
A091225(a(n)) = A010051(n). [Maps primes to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242. The permutations A091204, A106442, A106444, A106446, A235041 and A245703 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) = A305421(a(A064989(n))).
a(n) = A305417(A156552(n)) = A305427(A243071(n)).
(End)

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

Original entry on oeis.org

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
Offset: 1

Views

Author

Antti Karttunen, Aug 02 2014

Keywords

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.

Links

Crossrefs

Inverse: A245704.
Cf. A000040, A002808, A000720, A007097, A010051, A014580, A065855, A091225, A091230, A091242.
Similar or related permutations: A091202, A091204, A106442, A106444, A106446, A235041, A135141, A245701, A245702, A245821, A245822, A244987, A245450.

Programs

  • PARI
    allocatemem(123456789);
a014580 = vector(2^18);
a091242 = 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++; 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.
(definec (A245703 n) (cond ((= 1 n) n) ((= 1 (A010051 n)) (A014580 (A245703 (A000720 n)))) (else (A091242 (A245703 (A065855 n))))))

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).
a(1) = 1, after which, if A010051(n) is 1 [i.e. n is prime], then a(n) = A014580(a(A000720(n))), otherwise a(n) = A091242(a(A065855(n))).
As a composition of related permutations:
a(n) = A245702(A135141(n)).
a(n) = A091204(A245821(n)).
Other identities. For all n >= 1, the following holds:
a(A007097(n)) = A091230(n). [Maps iterates of primes to the iterates of A014580. Permutation A091204 has the same property]
A091225(a(n)) = A010051(n). [Maps primes to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242. The permutations A091202, A091204, A106442, A106444, A106446 and A235041 have the same property.]

A091204 Factorization and index-recursion preserving isomorphism from nonnegative integers to polynomials over GF(2).

Original entry on oeis.org

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
Offset: 0

Views

Author

Antti Karttunen, Jan 03 2004. Name changed Aug 16 2014

Keywords

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.

Links

Crossrefs

Inverse: A091205.
Similar or related permutations: A091202, A106442, A106444, A106446, A235041, A245703, A245814, A245822.
Cf. A000040, A007097, A010051, A014580, A018252, A048720, A061775, A091225, A091230, A091238, A091242.

Programs

  • PARI
    v014580 = vector(2^18); A014580(n) = v014580[n];
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
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)));
\\ Antti Karttunen, Aug 16 2014

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:
a(n) = A245703(A245822(n)).
Other identities.
For all n >= 0, the following holds:
a(A007097(n)) = A091230(n). [Maps iterates of primes to the iterates of A014580. Permutation A245703 has the same property]
For all n >= 1, the following holds:
A091225(a(n)) = A010051(n). [Maps primes bijectively to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242, in some order. The permutations A091202, A106442, A106444, A106446, A235041 and A245703 have the same property.]

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

Original entry on oeis.org

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
Offset: 0

Views

Author

Antti Karttunen, Jan 02 2014

Keywords

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.
This map satisfies many of the same identities as A091202, e.g., we have A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)) and A008683(n) = A091219(a(n)) for all n >= 1.

Examples

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

Links

Crossrefs

Inverse: A235042. Fixed points: A235045.
Cf. A010051, A048720, A091225, A091214, A235043, A048724, A115857, A115872.
Similar cross-multiplicative permutations: A091202, A091204, A106442, A106444, A106446.

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.

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

Views

Author

Antti Karttunen, Sep 13 2002

Keywords

Comments

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.

Examples

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

Links

Crossrefs

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.

Formula

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

A075167 Number of edges in each rooted plane tree produced with the unranking algorithm presented in A075166, which is based on prime factorization.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 3, 4, 5, 4, 6, 5, 4, 3, 7, 4, 8, 5, 5, 6, 9, 4, 4, 7, 4, 6, 10, 5, 11, 4, 6, 8, 5, 5, 12, 9, 7, 5, 13, 6, 14, 7, 5, 10, 15, 5, 5, 5, 8, 8, 16, 5, 6, 6, 9, 11, 17, 6, 18, 12, 6, 4, 7, 7, 19, 9, 10, 6, 20, 5, 21, 13, 5, 10, 6, 8, 22, 6, 4, 14, 23, 7, 8, 15, 11, 7, 24, 6, 7, 11
Offset: 1

Views

Author

Antti Karttunen, Sep 13 2002

Keywords

Comments

Each n occurs A000108(n) times in total.

Links

Crossrefs

Permutation of A072643 and A106457.
A253782 gives the positions where this sequence differs from A252464 (first time at n=16).
Cf. A000108, A000120, A029837, A055642, A051119, A061395, A071178, A075165, A075166, A106442, A253783.
Cf. also A106490.

Formula

a(n) = A106457(A106442(n)). - Antti Karttunen, May 09 2005
From Antti Karttunen, Jan 16 2015: (Start)
a(1) = 0; for n>1: a(n) = a(A071178(n)) + (A061395(n) - A061395(A051119(n))) + A253783(A051119(n)).
Other identities.
For all n >= 2, a(n) = A055642(A075166(n))/2. [Half of the number of decimal digits in A075166(n).]
For all n >= 2, a(n) = A029837(1+A075165(n))/2. [Half of the binary width of A075165(n).]
For all n >= 1, a(n) = A000120(A075165(n)). [Thus also the binary weight of A075165(n), because half of the bits are zeros.]
(End)

Extensions

More terms from Antti Karttunen, May 09 2005

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

Views

Author

Antti Karttunen, May 09 2005

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

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

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.

A075165 Sequence A075166 interpreted as binary numbers and converted to decimal.

Original entry on oeis.org

0, 2, 10, 12, 42, 44, 170, 52, 50, 172, 682, 180, 2730, 684, 178, 56, 10922, 204, 43690, 692, 690, 2732, 174762, 184, 202, 10924, 210, 2740, 699050, 716, 2796202, 212, 2738, 43692, 714, 820, 11184810, 174764, 10930, 696, 44739242, 2764, 178956970
Offset: 1

Views

Author

Antti Karttunen, Sep 13 2002

Keywords

Crossrefs

Permutation of A014486. Same sequence shown in binary: A075166. The binary width of each term / 2 is given by A075167.

Formula

a(n) = A106455(A106442(n)). - Antti Karttunen, May 09 2005

A075163 Position of A075165(n) in A014486 plus one.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 10, 8, 7, 11, 24, 13, 66, 25, 12, 9, 198, 16, 627, 27, 26, 67, 2057, 14, 15, 199, 17, 69, 6919, 30, 23715, 18, 68, 628, 29, 41, 82501, 2058, 200, 28, 290513, 72, 1033413, 201, 31, 6920, 3707853, 32, 38, 39, 629, 630, 13402698, 44, 71, 70, 2059
Offset: 1

Views

Author

Antti Karttunen, Sep 13 2002

Keywords

Comments

See A075166.

Links

Crossrefs

Inverse of A075164. a(n) = A075161(n-1)+1.

Formula

a(n) = A106453(A106442(n)). - Antti Karttunen, May 09 2005
Showing 1-10 of 11 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.