A116550 The bi-unitary analog of Euler's totient function of n.

1, 1, 2, 3, 4, 3, 6, 7, 8, 6, 10, 8, 12, 9, 9, 15, 16, 12, 18, 14, 14, 15, 22, 17, 24, 18, 26, 21, 28, 15, 30, 31, 23, 24, 25, 29, 36, 27, 28, 31, 40, 21, 42, 35, 34, 33, 46, 36, 48, 36, 37, 42, 52, 39, 42, 46, 42, 42, 58, 34, 60, 45, 51, 63, 50, 35, 66, 56, 51, 38, 70, 62, 72, 54

Offset: 1

Author

Leroy Quet, Mar 16 2006

Keywords

• nonn

Comments

a(1)=1; for n>1, a(n) is the number of numbers mA225174(m,n)=1. - N. J. A. Sloane, May 01 2013

Examples

			12 = 2^2 * 3^1. Of the positive integers < 12, there are 8 integers where no prime divides these integers the same number of times the prime divides 12: 1, 2 = 2^1, 5 = 5^1, 7 = 7^1, 8 = 2^3, 9 = 3^2, 10 = 2^1 *5^1 and 11 = 11^1. So a(12) = 8. The other positive integers < 12 (3 = 3^1, 4 = 2^2 and 6 = 2^1 * 3^1) each are divisible by at least one prime the same number of times this prime divides 12.
		

References

• M. Lal, H. Wareham and R. Mifflin, Iterates of the bi-unitary totient function, Utilitas Math., 10 (1976), 347-350.

Links

• Donovan Johnson, Table of n, a(n) for n = 1..10000
• László Tóth, On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function, JIS, Vol. 12 (2009), Article 09.5.2, function phi**(n).

Crossrefs

Cf. A225174, A005424, A225175, A225176, A000010, A047994.

Programs

Maple

# returns the greatest common unitary divisor of m and n, A225174(m,n)
f:=proc(m,n)
   local i,ans;
   ans:=1;
   for i from 1 to min(m,n) do
     if ((m mod i) = 0) and (igcd(i,m/i) = 1)  then
       if ((n mod i) = 0) and (igcd(i,n/i) = 1)  then ans:=i; fi;
     fi;
   od;
ans; end;
A116550:=proc(n)
  global f; local ct,m;
  ct:=0;
  if n = 1 then RETURN(1) else
  for m from 1 to n-1 do
    if f(m,n)=1 then ct:=ct+1; fi;
  od:
  fi;
  ct;
end; # N. J. A. Sloane, May 01 2013
A116550 := proc(n)
    local a,k;
    a := 0 ;
    for k from 1 to n do
        if A165430(k,n) = 1 then
            a := a+1 ;
        end if ;
    end do:
    a ;
end proc: # R. J. Mathar, Jul 21 2016

Mathematica

a[1] = 1; a[n_] := With[{pp = Power @@@ FactorInteger[n]}, Count[Range[n], m_ /; Intersection[pp, Power @@@ FactorInteger[m]] == {}]]; Table[a[n], {n, 1, 90}] (* Jean-François Alcover, Sep 05 2013 *)
phi[x_, n_] := DivisorSum[n, MoebiusMu[#]*Floor[x/#] &]; a[n_] := DivisorSum[n, (-1)^PrimeNu[#]*phi[n/#, #] &, CoprimeQ[#, n/#] &]; Array[a, 100] (* Amiram Eldar, Jul 16 2022 *)

PARI

udivs(n) = {my(d = divisors(n)); select(x->(gcd(x, n/x)==1), d); }
gcud(n, m) = vecmax(setintersect(udivs(n), udivs(m)));
a(n) = if (n==1, 1, sum(k=1, n-1, gcud(n, k) == 1)); \\ Michel Marcus, Nov 09 2017

PARI

phi(x,n) = sumdiv(n, d, moebius(d)*floor(x/d));
a(n) = sumdiv(n, d, (gcd(d, n/d) == 1) * (-1)^omega(d) * phi(n/d,d)); \\ Amiram Eldar, Jul 16 2022

Formula

For n>1, if n = product{p=primes,p|n} p^b(n,p), where each b(n,p) is a positive integer, then a(n) is number of positive integers m, m < n, such that each b(m,p) does not equal b(n,p).

a(n) = Sum_{d|n, gcd(d,n/d)=1} (-1)^omega(d) * phi(x, n), where phi(x, n) = #{1 <= k <= x, gcd(k, n) = 1} = Sum_{d|n} mu(d) * floor(x/d) (Tóth, 2009). - Amiram Eldar, Jul 16 2022

Extensions

More terms from R. J. Mathar, Jan 23 2008

Entry revised by N. J. A. Sloane, May 01 2013