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).
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
Keywords
Examples
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
Links
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.
Programs
-
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
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).
A236378(n) = n - a(n).
Extensions
Term a(0) = 0 removed and a new primary definition added by Antti Karttunen, May 10 2019
Comments