A248663 - OEIS

%I #129 Nov 01 2023 09:58:46

%S 0,1,2,0,4,3,8,1,0,5,16,2,32,9,6,0,64,1,128,4,10,17,256,3,0,33,2,8,

%T 512,7,1024,1,18,65,12,0,2048,129,34,5,4096,11,8192,16,4,257,16384,2,

%U 0,1,66,32,32768,3,20,9,130,513,65536,6,131072,1025,8,0,36,19

%N Binary encoding of the prime factors of the squarefree part of n.

%C The binary digits of a(n) encode the prime factorization of A007913(n), where the i-th digit from the right is 1 if and only if prime(i) divides A007913(n), otherwise 0. - _Robert Israel_, Jan 12 2015

%C Old name: a(1) = 0; a(A000040(n)) = 2^(n-1), and a(n*m) = a(n) XOR a(m).

%C XOR is the bitwise exclusive or operation (A003987).

%C a(k^2) = 0 for a natural number k.

%C Equivalently, the i-th binary digit from the right is 1 iff prime(i) divides n an odd number of times, otherwise zero. - _Ethan Beihl_, Oct 15 2016

%C When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443, with scheme explained in A206284), then A048675(n) gives the evaluation of that polynomial at x=2. This sequence is otherwise similar, except the polynomial is evaluated over the field GF(2), which implies also that all its coefficients are essentially reduced modulo 2. - _Antti Karttunen_, Dec 11 2015

%C Squarefree numbers (A005117) give the positions k where a(k) = A048675(k). - _Antti Karttunen_, Oct 29 2016

%C From _Peter Munn_, Jun 07 2021: (Start)

%C When we encode polynomials with nonnegative integer coefficients as described by _Antti Karttunen_ above, polynomial addition is represented by integer multiplication, multiplication is represented by A297845(.,.), and this sequence represents a surjective semiring homomorphism to polynomials in GF(2)[x] (encoded as described in A048720). The mapping of addition operations by this homomorphism is part of the sequence definition: "a(n*m) = a(n) XOR a(m)". The mapping of multiplication is given by a(A297845(n, k)) = A048720(a(n), a(k)).

%C In a related way, A329329 defines a representation of a different set of polynomials as positive integers, namely polynomials in GF(2)[x,y].

%C Let P_n(x,y) denote the polynomial represented, as in A329329, by n >= 1. If 0 is substituted for y in P_n(x,y), we get a polynomial P'_n(x,y) (in which y does not appear, of course) that is equivalent to a polynomial P'_n(x) in GF(2)[x]. a(n) is the integer encoding of P'_n(x) (described in A048720).

%C Viewed as above, this sequence represents another surjective homomorphism, a homomorphism between polynomial rings, with A329329(.,.)/A059897(.,.) and A048720(.,.)/A003987(.,.) as the respective ring operations.

%C a(n) can be composed as a(n) = A048675(A007913(n)) and the effect of the A007913(.) component corresponds to different operations on the respective polynomial domains of the two homomorphisms described above. In the first homomorphism, coefficients are reduced modulo 2; in the second, 0 is substituted for y. This is illustrated in the examples.

%C (End)

%H Peter Kagey, <a href="/A248663/b248663.txt">Table of n, a(n) for n = 1..5000</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SquarefreePart.html">Squarefree Part</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Polynomial_ring">Polynomial ring</a>

%H <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>

%F a(1) = 0; for n > 1, if n is a prime, a(n) = 2^(A000720(n)-1), otherwise a(A020639(n)) XOR a(A032742(n)). [After the definition.] - _Antti Karttunen_, Dec 11 2015

%F For n > 1, this simplifies to: a(n) = 2^(A055396(n)-1) XOR a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n. Cf. a similar formula for A048675.]

%F Other identities and observations. For all n >= 0:

%F a(n) = A048672(A100112(A007913(n))). - _Peter Kagey_, Dec 10 2015

%F From _Antti Karttunen_, Dec 11 2015, Sep 19 & Oct 27 2016, Feb 15 2021: (Start)

%F a(n) = a(A007913(n)). [The result depends only on the squarefree part of n.]

%F a(n) = A048675(A007913(n)).

%F a(A206296(n)) = A168081(n).

%F a(A260443(n)) = A264977(n).

%F a(A265408(n)) = A265407(n).

%F a(A275734(n)) = A275808(n).

%F a(A276076(n)) = A276074(n).

%F a(A283477(n)) = A006068(n).

%F (End)

%F From _Peter Munn_, Jan 09 2021 and Apr 20 2021: (Start)

%F a(n) = A007814(A225546(n)).

%F a(A019565(n)) = n; A019565(a(n)) = A007913(n).

%F a(A003961(n)) = 2 * a(n).

%F a(A297845(n, k)) = A048720(a(n), a(k)).

%F a(A329329(n, k)) = A048720(a(n), a(k)).

%F a(A059897(n, k)) = A003987(a(n), a(k)).

%F a(A331590(n, k)) = a(n) + a(k).

%F a(A334747(n)) = a(n) + 1.

%F (End)

%e a(3500) = a(2^2 * 5^3 * 7) = a(2) XOR a(2) XOR a(5) XOR a(5) XOR a(5) XOR a(7) = 1 XOR 1 XOR 4 XOR 4 XOR 4 XOR 8 = 0b0100 XOR 0b1000 = 0b1100 = 12.

%e From _Peter Munn_, Jun 07 2021: (Start)

%e The examples in the table below illustrate the homomorphisms (between polynomial structures) represented by this sequence.

%e The staggering of the rows is to show how the mapping n -> A007913(n) -> A048675(A007913(n)) = a(n) relates to the encoded polynomials, as not all encodings are relevant at each stage.

%e For an explanation of each polynomial encoding, see the sequence referenced in the relevant column heading. (Note also that A007913 generates squarefree numbers, and with these encodings, all squarefree numbers represent equivalent polynomials in N[x] and GF(2)[x,y].)

%e                      |<-----    encoded polynomials    ----->|

%e   n  A007913(n) a(n) |         N[x]    GF(2)[x,y]    GF(2)[x]|

%e                      |Cf.:  A206284       A329329     A048720|

%e --------------------------------------------------------------

%e   24                            x+3         x+y+1

%e           6                     x+1           x+1

%e                   3                                       x+1

%e --------------------------------------------------------------

%e   36                           2x+2          xy+y

%e           1                       0             0

%e                   0                                         0

%e --------------------------------------------------------------

%e   60                        x^2+x+2       x^2+x+y

%e          15                   x^2+x         x^2+x

%e                   6                                     x^2+x

%e --------------------------------------------------------------

%e   90                       x^2+2x+1      x^2+xy+1

%e          10                   x^2+1         x^2+1

%e                   5                                     x^2+1

%e --------------------------------------------------------------

%e This sequence is a left inverse of A019565. A019565(.) maps a(n) to A007913(n) for all n, effectively reversing the second stage of the mapping from n to a(n) shown above. So, with the encodings used here, A019565(.) represents each of two injective homomorphisms that map polynomials in GF(2)[x] to equivalent polynomials in N[x] and GF(2)[x,y] respectively.

%e (End)

%p f:= proc(n)

%p local F,f;

%p F:= select(t -> t[2]::odd, ifactors(n)[2]);

%p add(2^(numtheory:-pi(f[1])-1), f = F)

%p end proc:

%p seq(f(i),i=1..100); # _Robert Israel_, Jan 12 2015

%t a[1] = 0; a[n_] := a[n] = If[PrimeQ@ n, 2^(PrimePi@ n - 1), BitXor[a[#], a[n/#]] &@ FactorInteger[n][[1, 1]]]; Array[a, 66] (* _Michael De Vlieger_, Sep 16 2016 *)

%o (Ruby)

%o require 'prime'

%o def f(n)

%o   a = 0

%o   reverse_primes = Prime.each(n).to_a.reverse

%o   reverse_primes.each do |prime|

%o     a <<= 1

%o     while n % prime == 0

%o       n /= prime

%o       a ^= 1

%o     end

%o   end

%o   a

%o end

%o (Scheme, with memoizing-macro definec)

%o (definec (A248663 n) (cond ((= 1 n) 0) ((= 1 (A010051 n)) (A000079 (- (A000720 n) 1))) (else (A003987bi (A248663 (A020639 n)) (A248663 (A032742 n)))))) ;; Where A003987bi computes bitwise-XOR as in A003987.

%o ;; Alternatively:

%o (definec (A248663 n) (cond ((= 1 n) 0) (else (A003987bi (A000079 (- (A055396 n) 1)) (A248663 (A032742 n))))))

%o ;; _Antti Karttunen_, Dec 11 2015

%o (PARI) A248663(n) = vecsum(apply(p -> 2^(primepi(p)-1),factor(core(n))[,1])); \\ _Antti Karttunen_, Feb 15 2021

%o (Haskell)

%o import Data.Bits (xor)

%o a248663 = foldr (xor) 0 . map (\i -> 2^(i - 1)) . a112798_row

%o -- _Peter Kagey_, Sep 16 2016

%o (Python)

%o from sympy import factorint, primepi

%o from sympy.ntheory.factor_ import core

%o def a048675(n):

%o     f=factorint(n)

%o     return 0 if n==1 else sum([f[i]*2**(primepi(i) - 1) for i in f])

%o def a(n): return a048675(core(n)) print [a(n) for n in range(1, 101)] # _Indranil Ghosh_, Jun 21 2017

%Y Cf. A000040, A000079, A000720, A005117, A020639, A032742, A048672, A055396, A100112, A206284.

%Y A048675 composed with A007913. A007814 composed with A225546.

%Y A homomorphism from A297845/A003991 and from A329329/A059897 to A048720/A003987, mapping A206296 to A168081, A260443 to A264977, A265408 to A265407, A275734 to A275808, A276076 to A276074, A283477 to A006068.

%Y A left inverse of A019565.

%Y Other sequences used to express relationship between terms of this sequence: A003961, A007913, A331590, A334747.

%Y Cf. also A099884, A277330.

%Y A087207 is the analogous sequence with OR.

%Y A277417 gives the positions where coincides with A277333.

%Y A000290 gives the positions of zeros.

%K nonn,base

%O 1,3

%A _Peter Kagey_, Jan 11 2015

%E New name from _Peter Munn_, Nov 01 2023