OFFSET
1,3
COMMENTS
Oex divisors d of an integer n are defined in A186443: those divisors d which are either 1 or numbers such that d^k || n (the highest power of d dividing n) has odd exponent k.
A positive number is called an oex prime if it has only two oex divisors; since every n >= 2 has at least two oex divisors, 1 and n, an oex prime q has only oex divisors 1 and q. A000430 is the sequence of oex primes q, i.e., A186643(q) = 2 iff q is an entry in A000430.
A unique factorization, called an oex prime power factorization, of integers n is introduced as follows: each factor p^e in the conventional prime power factorization n = Product(p^e) is written as (p^2)^(e/2) if e is even, and as (p^2)^floor(e/2)*p if e is odd. This represents n as a product of oex primes of the type q=p^2, with unconstrained exponents e/2, and of oex primes of the type q=p with exponents 0 or 1. (This is similar to splitting n into its squarefree part A007913(n) times A008833(n), followed by an ordinary prime factorization in both parts separately.)
Let n = q_1^a_1*q_2^a_2*... and m = q_1^b_1*q_2^b_2*..., a_i,b_i >= 0 be the oex prime power factorizations of n and m. Define the oex GCD of n and m as [n,m] = q_1^min(a_1,b_1) * q_2^min(a_2,b_2) * .... Then a(n) = Sum_{m=1..n, [m,n]=1} 1, the oex analog of the Euler-phi function.
FORMULA
Let core(n) = p_1*...*p_r = A007913(n), n/core(n) = A008833(n) = q_1^c_1*...*q_t^c_t, where q_i are squares of primes.
If core(n)=1, then a(n) = n*Product_{j=1..r} (1-1/q_i); if core(n) tends to infinity, then a(n) ~ n * core(n) * Product_{i=1..t} (1-1/q_i) / Product_{j=1..r} (1+p_j).
a(n) <= A064380(n).
EXAMPLE
The oex prime power factorization of 16 is 4^2. Since [16,i]=1 for i=1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, and 15, a(16)=12.
The oex prime power factorization of 9 is 9. Thus a(9)=8.
MAPLE
highpp := proc(n, d) local nshf, a ; if n mod d <> 0 then 0; else nshf := n ; a := 0 ; while nshf mod d = 0 do nshf := nshf /d ; a := a+1 ; end do: a; end if; end proc:
oexgcd := proc(n, m) local a, p, kn, km ; a := 1 ; for p in numtheory[factorset](n) do kn := highpp(n, p) ; km := highpp(m, p) ; if type(kn, 'even') = type(km, 'even') then ; else kn := 2*floor(kn/2) ; km := 2*floor(km/2) ; end if; a := a*p^min(kn, km) ; end do: a ; end proc:
A186970 := proc(n) local a, i; a := 0 ; for i from 1 to n do if oexgcd(n, i) = 1 then a := a+1 ; end if; end do: a; end proc:
seq(A186970(n), n=1..80) ; # R. J. Mathar, Mar 18 2011
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Shevelev, Mar 01 2011
STATUS
approved