A091203 -id:A091203 - cp's OEIS frontend

A106445 Exponent-recursed cross-domain bijection from GF(2)[X] to N. Variant of A091203 and A106443.

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, 48, 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 'superfactorized' structures, e.g. A106493(n) = A106490(a(n)), A106494(n) = A106491(a(n)), A106495(n) = A064372(a(n)). Shares with A091203 and A106443 the property that maps A014580(n) to A000040(n). Differs from the plain variant A091203 for the first time at n=32, where A091203(32)=32, while a(32)=512. Differs from the variant A106443 for the first time at n=48, where A106443(48)=768, while a(48)=48. Differs from a yet deeper variant A106447 for the first time at n=13, where A106447(13)=23, while a(13)=11.

			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) = 3 * 2^4 = 3 * 16 = 48.

Inverse: A106444.

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(e_j) * a(ir_k)^a(e_k) * ... = A000040(i)^a(e_i) * A000040(j)^a(e_j) * A000040(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.

A234747 Self-inverse and multiplicative permutation of natural numbers, A091202-conjugate of Blue code: a(n) = A091203(A193231(A091202(n))).

Original entry on oeis.org

0, 1, 3, 2, 9, 5, 6, 11, 27, 4, 15, 7, 18, 13, 33, 10, 81, 19, 12, 17, 45, 22, 21, 37, 54, 25, 39, 8, 99, 43, 30, 41, 243, 14, 57, 55, 36, 23, 51, 26, 135, 31, 66, 29, 63, 20, 111, 59, 162, 121, 75, 38, 117, 61, 24, 35, 297, 34, 129, 47, 90, 53, 123, 44, 729

Offset: 0

Antti Karttunen, Dec 31 2013

a(n) has the same prime signature as n: the permutation maps primes to primes, squares to squares, cubes to cubes, and so on.

			Example of multiplicativity: a(7)=11, a(23)=37, a(7*23) = a(161) = a(7)*a(23) = 11*37 = 407.

Cf. A091202, A091203, A193231, A234751.

See A234748 for a variant.

(define (A234747 n) (A091203 (A193231 (A091202 n))))

a(n) = A091203(A193231(A091202(n))).

Completely multiplicative with p_i = p_{A234751(i)} (where p_i stands for the i-th prime, A000040(i)), and a(x*y) = a(x)*a(y) for x, y > 0.

A003961 Completely multiplicative with a(prime(k)) = prime(k+1).

Original entry on oeis.org

1, 3, 5, 9, 7, 15, 11, 27, 25, 21, 13, 45, 17, 33, 35, 81, 19, 75, 23, 63, 55, 39, 29, 135, 49, 51, 125, 99, 31, 105, 37, 243, 65, 57, 77, 225, 41, 69, 85, 189, 43, 165, 47, 117, 175, 87, 53, 405, 121, 147, 95, 153, 59, 375, 91, 297, 115, 93, 61, 315, 67, 111, 275, 729, 119

Offset: 1

Marc LeBrun

Meyers (see Guy reference) conjectures that for all r >= 1, the least odd number not in the set {a(i): i < prime(r)} is prime(r+1). - N. J. A. Sloane, Jan 08 2021
Meyers' conjecture would be refuted if and only if for some r there were such a large gap between prime(r) and prime(r+1) that there existed a composite c for which prime(r) < c < a(c) < prime(r+1), in which case (by Bertrand's postulate) c would necessarily be a term of A246281. - Antti Karttunen, Mar 29 2021
a(n) is odd for all n and for each odd m there exists a k with a(k) = m (see A064216). a(n) > n for n > 1: bijection between the odd and all numbers. - Reinhard Zumkeller, Sep 26 2001
a(n) and n have the same number of distinct primes with (A001222) and without multiplicity (A001221). - Michel Marcus, Jun 13 2014
From Antti Karttunen, Nov 01 2019: (Start)
More generally, a(n) has the same prime signature as n, A046523(a(n)) = A046523(n). Also A246277(a(n)) = A246277(n) and A287170(a(n)) = A287170(n).
Many permutations and other sequences that employ prime factorization of n to encode either polynomials, partitions (via Heinz numbers) or multisets in general can be easily defined by using this sequence as one of their constituent functions. See the last line in the Crossrefs section for examples.
(End)

			a(12) = a(2^2 * 3) = a(prime(1)^2 * prime(2)) = prime(2)^2 * prime(3) = 3^2 * 5 = 45.
a(A002110(n)) = A002110(n + 1) / 2.

Richard K. Guy, editor, Problems From Western Number Theory Conferences, Labor Day, 1983, Problem 367 (Proposed by Leroy F. Meyers, The Ohio State U.).

Indranil Ghosh, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Index entries for sequences computed from indices in prime factorization.
Index entries for sequences related to Heinz numbers.

See A045965 for another version.
Row 1 of table A242378 (which gives the "k-th powers" of this sequence), row 3 of A297845 and of A306697. See also arrays A066117, A246278, A255483, A308503, A329050.
Cf. A064989 (a left inverse), A064216, A000040, A002110, A000265, A027746, A046523, A048673 (= (a(n)+1)/2), A108228 (= (a(n)-1)/2), A191002 (= a(n)*n), A252748 (= a(n)-2n), A286385 (= a(n)-sigma(n)), A283980 (= a(n)*A006519(n)), A341529 (= a(n)*sigma(n)), A326042, A049084, A001221, A001222, A122111, A225546, A260443, A245606, A244319, A246269 (= A065338(a(n))), A322361 (= gcd(n, a(n))), A305293.
Cf. A191555, A252738.
Cf. A249734, A249735 (bisections).
Cf. A246261 (a(n) is of the form 4k+1), A246263 (of the form 4k+3), A246271, A246272, A246259, A246281 (n such that a(n) < 2n), A246282 (n such that a(n) > 2n), A252742.
Cf. A275717 (a(n) > a(n-1)), A275718 (a(n) < a(n-1)).
Cf. A003972 (Möbius transform), A003973 (Inverse Möbius transform), A318321.
Cf. A300841, A305421, A322991, A250469, A269379 for analogous shift-operators in other factorization and quasi-factorization systems.
Cf. also following permutations and other sequences that can be defined with the help of this sequence: A005940, A163511, A122111, A260443, A206296, A265408, A265750, A275733, A275735, A297845, A091202 & A091203, A250245 & A250246, A302023 & A302024, A302025 & A302026.
A version for partition numbers is A003964, strict A357853.
A permutation of A005408.
Applying the same transformation again gives A357852.
Other multiplicative sequences: A064988, A357977, A357978, A357980, A357983.
A056239 adds up prime indices, row-sums of A112798.
Cf. A000720, A076610, A296150.

a003961 1 = 1
a003961 n = product $ map (a000040 . (+ 1) . a049084) $ a027746_row n
-- Reinhard Zumkeller, Apr 09 2012, Oct 09 2011
(MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
(require 'factor)
(define (A003961 n) (apply * (map A000040 (map 1+ (map A049084 (factor n))))))
;; Antti Karttunen, May 20 2014

a:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
seq(a(n), n=1..80);  # Alois P. Heinz, Sep 13 2017

a[p_?PrimeQ] := a[p] = Prime[ PrimePi[p] + 1]; a[1] = 1; a[n_] := a[n] = Times @@ (a[#1]^#2& @@@ FactorInteger[n]); Table[a[n], {n, 1, 65}] (* Jean-François Alcover, Dec 01 2011, updated Sep 20 2019 *)
Table[Times @@ Map[#1^#2 & @@ # &, FactorInteger[n] /. {p_, e_} /; e > 0 :> {Prime[PrimePi@ p + 1], e}] - Boole[n == 1], {n, 65}] (* Michael De Vlieger, Mar 24 2017 *)

a(n)=local(f); if(n<1,0,f=factor(n); prod(k=1,matsize(f)[1],nextprime(1+f[k,1])^f[k,2]))

a(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Michel Marcus, May 17 2014

use ntheory ":all";  sub a003961 { vecprod(map { next_prime($) } factor(shift)); }  # _Dana Jacobsen, Mar 06 2016

from sympy import factorint, prime, primepi, prod
def a(n):
    f=factorint(n)
    return 1 if n==1 else prod(prime(primepi(i) + 1)**f[i] for i in f)
[a(n) for n in range(1, 11)] # Indranil Ghosh, May 13 2017

If n = Product p(k)^e(k) then a(n) = Product p(k+1)^e(k).
Multiplicative with a(p^e) = A000040(A000720(p)+1)^e. - David W. Wilson, Aug 01 2001
a(n) = Product_{k=1..A001221(n)} A000040(A049084(A027748(n,k))+1)^A124010(n,k). - Reinhard Zumkeller, Oct 09 2011 [Corrected by Peter Munn, Nov 11 2019]
A064989(a(n)) = n and a(A064989(n)) = A000265(n). - Antti Karttunen, May 20 2014 & Nov 01 2019
A001221(a(n)) = A001221(n) and A001222(a(n)) = A001222(n). - Michel Marcus, Jun 13 2014
From Peter Munn, Oct 31 2019: (Start)
a(n) = A225546((A225546(n))^2).
a(A225546(n)) = A225546(n^2).
(End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} ((p^2-p)/(p^2-nextprime(p))) = 2.06399637... . - Amiram Eldar, Nov 18 2022

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Original entry on oeis.org

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375

Offset: 1

David Petry (petry(AT)accessone.com)

nonn

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.
The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014
2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021
For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

			x^4 + x^3 + 1 -> 16+8+1 = 25. Or, x^4 + x^3 + 1 -> 11001 (binary) = 25 (decimal).

A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (first 1377 terms from T. D. Noe)
Index entries for sequences operating on GF(2)[X]-polynomials

Written in binary: A058943.
Number of degree-n irreducible polynomials: A001037, see also A000031.
Multiplication table: A048720.
Characteristic function: A091225. Inverse: A091227. a(n) = A091202(A000040(n)). Almost complement of A091242. Union of A091206 & A091214 and also of A091250 & A091252. First differences: A091223. Apart from a(1) and a(2), a subsequence of A092246 and hence A000069.
Table of irreducible factors of n: A256170.
Irreducible polynomials satisfying particular conditions: A071642, A132447, A132449, A132453, A162570.
Factorization sentinel: A278239.
Sequences analyzing the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the corresponding integer: A234741, A234742, A235032, A235033, A235034, A235035, A235040, A236850, A325386, A325559, A325560, A325563, A325641, A325642, A325643.
Factorization-preserving isomorphisms: A091203, A091204, A235041, A235042.
See A115871 for sequences related to cross-domain congruences.
Functions based on the irreducibles: A305421, A305422.

fQ[n_] := Block[{ply = Plus @@ (Reverse@ IntegerDigits[n, 2] x^Range[0, Floor@ Log2@ n])}, ply == Factor[ply, Modulus -> 2] && n != 2^Floor@ Log2@ n]; fQ[2] = True; Select[ Range@ 378, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
Reap[Do[If[IrreduciblePolynomialQ[IntegerDigits[n, 2] . x^Reverse[Range[0, Floor[Log[2, n]]]], Modulus -> 2], Sow[n]], {n, 2, 1000}]][[2, 1]] (* Jean-François Alcover, Nov 21 2016 *)

is(n)=polisirreducible(Pol(binary(n))*Mod(1,2)) \\ Charles R Greathouse IV, Mar 22 2013

A091247 Characteristic function of A091242: 1 if the n-th GF(2)[X] polynomial is reducible, 0 otherwise.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

Antti Karttunen, Table of n, a(n) for n = 0..65537
A. Karttunen, Scheme-program for computing this sequence.
Index entries for characteristic functions
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A066247, A091203, A091205, A091246.

Complementary to A091225. Partial sums give A091245.

a(n) = if (n<2, 0, ! polisirreducible(Mod(1,2)*Pol(binary(n)))); \\ Michel Marcus, Apr 12 2015

a(n) = A066247(A091203(n)) = A066247(A091205(n)).

A091225 Characteristic function of A014580: 1 if the n-th GF(2)[X] polynomial is irreducible, 0 otherwise.

Original entry on oeis.org

0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

Antti Karttunen, Table of n, a(n) for n = 0..100000
A. Karttunen, Scheme-program for computing this sequence
Index entries for characteristic functions
Index entries for sequences operating on GF(2)[X]-polynomials

a(n) = A010051(A091203(n)) = A010051(A091205(n)). Partial sums give A091226. Cf. A091227. Complementary to A091247.

a(n) = polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ Michel Marcus, Nov 11 2017

Data section extended up to a(120) by Antti Karttunen, Jan 01 2023

A234741 a(n) is the base-2 carryless product of the prime factors of n; Encoding of the product of the polynomials over GF(2) represented by the prime factors of n (with multiplicity).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 5, 10, 11, 12, 13, 14, 15, 16, 17, 10, 19, 20, 9, 22, 23, 24, 17, 26, 15, 28, 29, 30, 31, 32, 29, 34, 27, 20, 37, 38, 23, 40, 41, 18, 43, 44, 17, 46, 47, 48, 21, 34, 51, 52, 53, 30, 39, 56, 53, 58, 59, 60, 61, 62, 27, 64, 57, 58, 67

Offset: 1

Antti Karttunen, Jan 22 2014

nonn

"Encoding" means the number whose binary representation is given by the coefficients of the polynomial, e.g., 13=1101[2] encodes X^3+X^2+1. The product is the usual multiplication of polynomials in GF(2)[X] (or binary multiplication without carry-bits, cf. A048720).

a(n) <= n. [As all terms of the table A061858 are nonnegative]

			a(9) = a(3*3) = 5, as when we multiply 3 ('11' in binary) with itself, and discard the carry-bits, using XOR (A003987) instead of normal addition, we get:
   11
  110
-----
  101
that is, 5, as '101' is its binary representation. In other words, a(9) = a(3*3) = A048720(3,3) = 5.
Alternatively, 9 = 3*3, and 3=11[2] encodes the polynomial X+1, and (X+1)*(X+1) = X^2+1 in GF(2)[X], which is encoded as 101[2] = 5, therefore a(9) = 5. - _M. F. Hasler_, Feb 16 2014

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences related to polynomials in ring GF(2)[X]

A235034 gives the k for which a(k)=k.
A236833(n) gives the number of times n occurs in this sequence.
A236841 gives the same sequence sorted and duplicates removed, A236834 gives the numbers that do not occur here, A236835 gives numbers that occur more than once.
A325562(n) gives the number of iterations needed before one of the fixed points (terms of A235034) is reached.
Cf. also A048720, A061858, A234742, A236378, A091202/A091203, A235041/A235042, A266195, A325561, A325562.

A234741(n)={n=factor(n);n[,1]=apply(t->Pol(binary(t)),n[,1]);sum(i=1,#n=Vec(factorback(n))%2,n[i]<<(#n-i))} \\ M. F. Hasler, Feb 18 2014

a(0)=0, a(1)=1, and for n > 1, a(n) = A048720(A020639(n),a(n/A020639(n))). [A048720 used as a bivariate function]
Equally, for n with its unique prime factorization n = p_1 * ... * p_k, with the p_i not necessarily distinct primes, a(n) = p_1 x ... x p_k, where x stands for carryless multiplication defined in A048720, which is isomorphic to multiplication in GF(2)[X].
a(2n) = 2*a(n).
More generally, if A061858(x,y) = 0, then a(x*y) = a(x)*a(y).
a(A235034(n)) = A235034(n).
A236378(n) = n - a(n).

Term a(0) = 0 removed and a new primary definition added by Antti Karttunen, May 10 2019

A091205 Factorization and index-recursion preserving isomorphism from binary codes of GF(2) polynomials to integers.

Original entry on oeis.org

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, 32, 57, 162, 115, 60, 47, 26, 63, 72, 61, 50, 33, 28, 135, 138, 17, 48, 35, 22, 243, 92, 39, 90, 37, 40, 207, 42, 83, 108, 29, 38, 75, 64, 225, 114, 103

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

This "deeply multiplicative" bijection is one of the deep variants of A091203 which satisfy most of the same identities as the latter, but it additionally preserves also the structures where we recurse on irreducible polynomial's A014580-index. E.g., we have: A091238(n) = A061775(a(n)). The reason this holds is that when the permutation is restricted to the binary codes for irreducible polynomials over GF(2) (A014580), it induces itself: a(n) = A049084(a(A014580(n))).

On the other hand, when this permutation is restricted to the union of {1} and reducible polynomials over GF(2) (A091242), permutation A245813 is induced.

Antti Karttunen, Table of n, a(n) for n = 0..8192
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials
Index entries for sequences that are permutations of the natural numbers

Inverse: A091204.
Similar or related permutations: A091203, A106443, A106445, A106447, A235042, A245704, A245813, A245821.
Cf. A000040, A007097, A010051, A014580, A049084, A061775, A091238, A091225, A091226, A091230, A091242.

allocatemem(123456789);
v091226 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
n=2; while((n < 2^22), if(isA014580(n), v091226[n] = v091226[n-1]+1, v091226[n] = v091226[n-1]); n++)
A091226(n) = v091226[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)}));
for(n=0, 8192, write("b091205.txt", n, " ", A091205(n)));
\\ Antti Karttunen, Aug 16 2014

a(0)=0, a(1)=1. For n that is coding an irreducible polynomial, that is if n = A014580(i), we have a(n) = A000040(a(i)) and for reducible polynomials a(ir_i X ir_j X ...) = a(ir_i) * a(ir_j) * ..., where ir_i = A014580(i), X stands for carryless multiplication of polynomials over GF(2) (A048720) and * for the ordinary multiplication of integers (A004247).
As a composition of related permutations:
a(n) = A245821(A245704(n)).
Other identities.
For all n >= 0, the following holds:
a(A091230(n)) = A007097(n). [Maps iterates of A014580 to the iterates of primes. Permutation A245704 has the same property.]
For all n >= 1, the following holds:
A010051(a(n)) = A091225(n). [After a(1)=1, maps binary representations of irreducible GF(2) polynomials, A014580, bijectively to primes and the binary representations of corresponding reducible polynomials, A091242, to composite numbers, in some order. The permutations A091203, A106443, A106445, A106447, A235042 and A245704 have the same property.]

Name changed by Antti Karttunen, Aug 16 2014

A091222 Number of irreducible polynomials dividing n-th GF(2)[X]-polynomial, counted with multiplicity.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 4, 4, 3, 1, 4, 2, 2, 2, 4, 1, 2, 3, 3, 2, 4, 1, 5, 2, 5, 2, 4, 1, 2, 3, 5, 1, 3, 2, 3, 4, 3, 1, 5, 2, 2, 5, 3, 2, 4, 1, 4, 3, 3, 1, 5, 1, 2, 3, 6, 4, 3, 1, 6, 2, 3, 2, 5, 1, 2, 4, 3, 2, 4, 2, 6, 2, 2, 3, 4, 6, 3, 1, 4, 2, 5, 1, 4, 2, 2, 3, 6, 1, 3, 3, 3, 3, 6

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A000051, A001222, A091203, A091205, A091248.

Cf. A256170.

for n from 1 to 1000 do
  L:= convert(n,base,2);
  P:= add(L[i]*X^(i-1),i=1..nops(L));
  R:= Factors(P) mod 2;
  a[n]:= add(r[2],r=R[2]);
od:
seq(a[n],n=1..1000); # Robert Israel, Jun 07 2015

a(n)=my(fm=factor(Pol(binary(n))*Mod(1, 2))); sum(k=1, #fm~, fm[k, 2]) \\ Franklin T. Adams-Watters, Jun 07 2015

a(n) = A001222(A091203(n)) = A001222(A091205(n)).

a(A000051(n)) = A091248(n).

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

Antti Karttunen, Jan 03 2004

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

Antti Karttunen, Table of n, a(n) for n = 0..8192
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials
Index entries for sequences that are permutations of the natural numbers

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.

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

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)

cp's OEIS Frontend

A106445 Exponent-recursed cross-domain bijection from GF(2)[X] to N. Variant of A091203 and A106443.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A234747 Self-inverse and multiplicative permutation of natural numbers, A091202-conjugate of Blue code: a(n) = A091203(A193231(A091202(n))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A003961 Completely multiplicative with a(prime(k)) = prime(k+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Perl

Python

Formula

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A091247 Characteristic function of A091242: 1 if the n-th GF(2)[X] polynomial is reducible, 0 otherwise.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A091225 Characteristic function of A014580: 1 if the n-th GF(2)[X] polynomial is irreducible, 0 otherwise.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A234741 a(n) is the base-2 carryless product of the prime factors of n; Encoding of the product of the polynomials over GF(2) represented by the prime factors of n (with multiplicity).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions