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.

Previous Showing 31-40 of 48 results. Next

A091245 Number of reducible GF(2)[X]-polynomials in range [0,n].

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 9, 10, 11, 12, 12, 13, 14, 15, 16, 17, 17, 18, 19, 20, 21, 22, 22, 23, 24, 25, 26, 27, 27, 28, 29, 30, 30, 31, 32, 33, 34, 35, 35, 36, 37, 38, 39, 40, 41, 42, 42, 43, 44, 45, 45, 46, 46, 47, 48, 49, 50, 51, 51, 52, 53, 54, 55, 56, 56
Offset: 0

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Comments

Analogous to A065855.

Examples

			In range [0,8] there are the following four reducible polynomials: 4,5,6,8 thus a(8) = 4.

Links

Crossrefs

Partial sums of A091247. Cf. A091242.

Programs

  • PARI
    first(n)=my(s); concat([0,0], vector(n-1,k, s += !polisirreducible(Pol(binary(k+1))*Mod(1,2)))) \\ Charles R Greathouse IV, Sep 02 2015

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

A091212 Composite numbers whose binary representation encodes a polynomial reducible over GF(2).

Original entry on oeis.org

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 88, 90, 92, 93, 94, 95, 96, 98, 99
Offset: 1

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Comments

"Encoded in binary representation" means that a polynomial a(n)*X^n+...+a(0)*X^0 over GF(2) is represented by the binary number a(n)*2^n+...+a(0)*2^0 in Z (where each coefficient a(k) = 0 or 1).
From Reinhard Zumkeller, Jul 05-12 2011, values for maximum n corrected by Antti Karttunen, May 18 2015: (Start)
a(n) = A192506(n) for n <= 36.
a(n) = A175526(n) for n <= 36.
(End)

Links

Crossrefs

Intersection of A002808 and A091242.
Cf. A257688 (complement, either 1, irreducible in GF(2)[X] or prime), A091206 (prime and irreducible), A091209 (prime and reducible), A091214 (nonprime and irreducible).
Cf. A091213, A236861, A235036 (a subsequence, apart from 1).
Differs from both A175526 and A192506 for the first time at n=37, where a(37) = 56, while A175526(37) = A192506(37) = 55, a term missing from here (as 55 encodes a polynomial which is irreducible in GF(2)[X]).
Differs from its subsequence A205783(n+1) for the first time at n=47, where a(47) = 69, while 69 is missing from A205783.

Programs

  • PARI
    isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
isA091212(n) = ((n > 1) && !isprime(n) && !isA014580(n));
n = 0; i = 0; while(n < 2^16, n++; if(isA091212(n), i++; write("b091212.txt", i, " ", n)));

Formula

a(n) = A091242(A091213(n)).

A245821 Permutation of natural numbers: a(n) = A091205(A245703(n)).

Original entry on oeis.org

1, 2, 3, 4, 5, 9, 7, 6, 8, 12, 11, 15, 23, 81, 18, 10, 17, 30, 13, 162, 27, 36, 19, 24, 16, 25, 38, 46, 37, 45, 31, 135, 14, 20, 50, 57, 47, 69, 21, 55, 83, 115, 419, 87, 60, 210, 61, 42, 54, 26, 90, 28, 29, 35, 32, 63, 171, 52, 59, 138, 113, 180, 111, 48, 88, 39, 41, 621, 72, 22, 953, 230, 103, 207, 126, 64, 33, 243
Offset: 1

Views

Author

Antti Karttunen, Aug 02 2014

Keywords

Links

Crossrefs

Inverse: A245822.
Other related permutations: A091205, A245703, A245815.
Fixed points: A245823.
Cf. A000040, A049084, A078442, A049076, A018252, A062298.

Programs

  • PARI
    allocatemem(234567890);
v014580 = vector(2^18);
v091226 = vector(2^22);
v091242 = 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++; v014580[i] = n; v091226[n] = v091226[n-1]+1, j++; v091242[j] = n; v091226[n] = v091226[n-1]); n++);
A014580(n) = v014580[n];
A091226(n) = v091226[n];
A091242(n) = v091242[n];
A091205(n) = if(n<=1, n, if(isA014580(n), prime(A091205(A091226(n))), {my(irfs, t); irfs=subst(lift(factor(Mod(1, 2)*Pol(binary(n)))), x, 2); irfs[,1]=apply(t->A091205(t), irfs[,1]); factorback(irfs)}));
A245703(n) = if(1==n, 1, if(isprime(n), A014580(A245703(primepi(n))), A091242(A245703(n-primepi(n)-1))));
A245821(n) = A091205(A245703(n));
for(n=1, 10001, write("b245821.txt", n, " ", A245821(n)));
  • Scheme
    (define (A245821 n) (A091205 (A245703 n)))

Formula

a(n) = A091205(A245703(n)).
Other identities. For all n >= 1, the following holds:
A078442(a(n)) = A078442(n), A049076(a(n)) = A049076(n). [Preserves "the order of primeness of n"].
a(p_n) = p_{a(n)} where p_n is the n-th prime, A000040(n).
a(n) = A049084(a(A000040(n))). [Thus the same permutation is induced also when it is restricted to primes].
A245815(n) = A062298(a(A018252(n))). [While restriction to nonprimes induces another permutation].

A246156 Odd reducible polynomials over GF(2), coded in binary. (Polynomials with the constant term 1 that are reducible over GF(2)).

Original entry on oeis.org

5, 9, 15, 17, 21, 23, 27, 29, 33, 35, 39, 43, 45, 49, 51, 53, 57, 63, 65, 69, 71, 75, 77, 79, 81, 83, 85, 89, 93, 95, 99, 101, 105, 107, 111, 113, 119, 121, 123, 125, 127, 129, 133, 135, 139, 141, 147, 149, 151, 153, 155, 159, 161, 163, 165, 169, 173, 175, 177, 179, 181, 183, 187, 189, 195, 197, 199, 201
Offset: 1

Views

Author

Antti Karttunen, Aug 20 2014

Keywords

Comments

Self-inverse permutation A193231 maps each term of this sequence to some term of A246158 and vice versa.

Examples

			5, which is 101 in binary, encodes polynomial x^2 + 1, which factorizes as (x+1)(x+1) over GF(2), (5 = A048720(3,3)), thus it is reducible in that polynomial ring. Also, its constant term is 1, (not zero), thus 5 is a member of this sequence.

Links

Crossrefs

Intersection of A091242 and A005408 (odd numbers).
A246157 is a subsequence. Cf. also A048720, A193231, A246158.

Programs

  • Maple
    filter:= proc(n) local L,p,x;
    L:= convert(n,base,2);
    p:= add(L[i]*x^(i-1),i=1..nops(L));
    not (Irreduc(p) mod 2)
end proc:
select(filter,[seq(2*i+1,i=1..100)]); # Robert Israel, Aug 21 2014

A246158 Odious reducible polynomials over GF(2), coded in binary. (Polynomials with an odd number of nonzero terms that are reducible over GF(2)).

Original entry on oeis.org

4, 8, 14, 16, 21, 22, 26, 28, 32, 35, 38, 42, 44, 49, 50, 52, 56, 62, 64, 69, 70, 74, 76, 79, 81, 82, 84, 88, 93, 94, 98, 100, 104, 107, 110, 112, 118, 121, 122, 124, 127, 128, 133, 134, 138, 140, 146, 148, 151, 152, 155, 158, 161, 162, 164, 168, 173, 174, 176, 179, 181, 182, 186, 188, 194, 196, 199, 200
Offset: 1

Views

Author

Antti Karttunen, Aug 20 2014

Keywords

Comments

Self-inverse permutation A193231 maps each term of this sequence to some term of A246156 and vice versa.
Each term belongs into a distinct infinite cycle in permutations like A246161/A246162 and A246163/A246164 apart from 4, which is in a finite cycle (3 4) of A246161/A246162 and 4 and 8 which both are in the same (infinite) cycle of A246163/A246164.

Examples

			4, which is 100 in binary, encodes polynomial x^2, which factorizes as (x)(x) over GF(2), (4 = A048720(2,2)), thus it is reducible in that polynomial ring. It also has an odd number of nonzero terms present (equally: odd number of 1-bits in its code), in this case just one, thus 4 is a member of this sequence.

Links

Crossrefs

Intersection of A091242 and A000069 (odious numbers).
A238186 and A246157 are subsequences.
Cf. also A048720, A246156, A193231, A246161, A246162, A246163, A246164.

A245450 Self-inverse permutation of natural numbers, A245703-conjugate of balanced bit-reverse: a(n) = A245704(A057889(A245703(n))).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 13, 8, 9, 10, 19, 12, 7, 14, 15, 16, 53, 18, 11, 20, 21, 22, 23, 24, 25, 26, 27, 33, 41, 30, 113, 32, 28, 34, 35, 36, 47, 39, 38, 92, 29, 54, 163, 85, 45, 462, 37, 60, 49, 70, 51, 94, 17, 42, 55, 74, 57, 156, 193, 48, 101, 62, 115, 64, 259, 77, 73, 132, 69, 50, 181, 102, 67, 56, 169, 76, 66, 78, 137, 87, 180, 398, 139, 84, 44
Offset: 1

Views

Author

Antti Karttunen, Aug 07 2014

Keywords

Links

Crossrefs

Cf. A010051, A244987, A057889, A245703, A245704, A234747, A234748, A245453.

Programs

Formula

a(n) = A245704(A057889(A245703(n))).
Other identities. For all n >= 1, the following holds:
A010051(a(n)) = A010051(n). [Maps primes to primes and composites to composites].

A244987 Self-inverse permutation of natural numbers, A245703-conjugate of Blue code: a(n) = A245704(A193231(A245703(n))).

Original entry on oeis.org

1, 3, 2, 6, 5, 4, 13, 8, 21, 15, 23, 16, 7, 25, 10, 12, 41, 18, 19, 64, 9, 22, 11, 49, 14, 26, 77, 39, 37, 34, 263, 105, 38, 30, 88, 70, 29, 33, 28, 133, 17, 54, 73, 126, 51, 462, 53, 60, 24, 66, 45, 74, 47, 42, 78, 94, 156, 81, 239, 48, 97, 62, 100, 20, 155, 50, 79, 98, 84, 36, 167, 141, 43, 52, 129, 164, 27, 55
Offset: 1

Views

Author

Antti Karttunen, Aug 07 2014

Keywords

Links

Crossrefs

Cf. A000040, A002808, A010051, A193231, A245703, A245704, A234747, A234748, A245450, A245454.

Programs

Formula

a(n) = A245704(A193231(A245703(n))).
Other identities. For all n >= 1, the following holds:
A010051(a(n)) = A010051(n). [Maps primes to primes and composites to composites].

A245815 Permutation of natural numbers induced when A245821 is restricted to nonprime numbers: a(n) = A062298(A245821(A018252(n))).

Original entry on oeis.org

1, 2, 5, 3, 4, 7, 9, 59, 11, 6, 20, 125, 18, 25, 15, 10, 16, 26, 32, 31, 103, 8, 12, 35, 41, 50, 13, 39, 85, 64, 43, 164, 29, 38, 17, 66, 19, 24, 21, 45, 132, 37, 105, 139, 82, 33, 65, 27, 507, 52, 14, 180, 161, 96, 46, 22, 190, 141, 87, 1603, 80, 36, 143, 107, 54, 670, 34, 47, 23, 68, 177, 1337, 40
Offset: 1

Views

Author

Antti Karttunen, Aug 02 2014

Keywords

Comments

This permutation is induced when A245821 is restricted to nonprimes, A018252, the first column of A114537, but equally, when it is restricted to column 2 (A007821), column 3 (A049078), etc. of that square array, or alternatively, to the successive rows of A236542.
The sequence of fixed points f(n) begins as 1, 2, 15, 142, 548, 1694, 54681. A018252(f(n)) gives the nonprime terms of A245823.

Links

Crossrefs

Inverse: A245816.
Related permutations: A245813, A245819, A245821.
Cf. A007821, A018252, A049078, A062298, A114537, A236542, A245823.

Programs

Formula

a(n) = A062298(A245821(A018252(n))).
As a composition of related permutations:
a(n) = A245813(A245819(n)).
Also following holds for all n >= 1:
a(n) = A062298(A049084(A245821(A007821(n)))).
a(n) = A062298(A049084(A049084(A245821(A049078(n))))).

A294884 Number of divisors of n that are not irreducible when their binary expansion is interpreted as polynomial over GF(2).

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 1, 3, 2, 3, 1, 4, 1, 2, 3, 4, 2, 4, 1, 5, 2, 2, 2, 6, 2, 2, 3, 4, 2, 6, 1, 5, 2, 3, 3, 7, 1, 2, 2, 7, 1, 5, 2, 4, 5, 3, 1, 8, 2, 4, 3, 4, 2, 6, 2, 6, 2, 3, 1, 10, 1, 2, 4, 6, 3, 5, 1, 5, 3, 6, 2, 10, 1, 2, 4, 4, 2, 5, 2, 9, 4, 2, 2, 9, 4, 3, 2, 6, 2, 10, 1, 5, 2, 2, 3, 10, 1, 4, 4, 7, 2, 6, 1, 6, 6
Offset: 1

Views

Author

Antti Karttunen, Nov 09 2017

Keywords

Comments

One more than the number of terms of A091242 that divide n: +1 is for divisor 1, which is also included in the count.

Links

Crossrefs

Cf. A000005, A091225, A091242, A294882, A294883.
Cf. also A234741, A234742, A294894.

Programs

  • PARI
    A294884(n) = sumdiv(n,d,!polisirreducible(Mod(1, 2)*Pol(binary(d))));

Formula

a(n) = Sum_{d|n} (1-A091225(d)).
a(n) + A294883(n) = A000005(n).
For n > 1, a(n) = 1 + A294882(n) - A091225(n).
Previous Showing 31-40 of 48 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.