login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 32
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

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]

FORMULA

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

EXAMPLE

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

PROG

(Scheme, with Antti Karttunen's IntSeq-library)

(definec (A234741 n) (if (< n 2) n (A048720bi (A020639 n) (A234741 (/ n (A020639 n)))))) ;; A048720bi is a bivariate-function for A048720.

(PARI) 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

CROSSREFS

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.

Sequence in context: A307282 A245354 A097377 * A063917 A234344 A331298

Adjacent sequences: A234738 A234739 A234740 * A234742 A234743 A234744

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jan 22 2014

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 04:29 EST 2022. Contains 358649 sequences. (Running on oeis4.)