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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186970 The oex analog of the Euler phi-function for the oex prime power factorization of positive integers. 1
1, 1, 2, 3, 4, 3, 6, 4, 8, 5, 10, 7, 12, 8, 9, 12, 16, 11, 18, 12, 14, 14, 22, 9, 24, 16, 18, 18, 28, 13, 30, 16, 22, 21, 25, 24, 36, 24, 27, 17, 40, 17, 42, 30, 33, 29, 46, 27, 48, 32, 36, 36, 52, 24, 42, 25, 40, 37, 58, 28, 60, 40, 49, 48, 50, 30, 66, 48, 49, 35, 70, 32, 72, 48, 54, 54, 61, 36 (list; graph; refs; listen; history; text; internal format)
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.

LINKS

Table of n, a(n) for n=1..78.

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

Cf. A000010, A000430, A186443, A186444, A186776, A064380.

Sequence in context: A332931 A248376 A138796 * A064380 A290732 A353201

Adjacent sequences:  A186967 A186968 A186969 * A186971 A186972 A186973

KEYWORD

nonn

AUTHOR

Vladimir Shevelev, Mar 01 2011

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 October 5 04:53 EDT 2022. Contains 357244 sequences. (Running on oeis4.)