cp's OEIS Frontend

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

%I A116550 #43 Jul 16 2022 07:09:30
%S A116550 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,
%T A116550 21,28,15,30,31,23,24,25,29,36,27,28,31,40,21,42,35,34,33,46,36,48,36,
%U A116550 37,42,52,39,42,46,42,42,58,34,60,45,51,63,50,35,66,56,51,38,70,62,72,54
%N A116550 The bi-unitary analog of Euler's totient function of n.
%C A116550 a(1)=1; for n>1, a(n) is the number of numbers m<n such that A225174(m,n)=1. - _N. J. A. Sloane_, May 01 2013
%D A116550 M. Lal, H. Wareham and R. Mifflin, Iterates of the bi-unitary totient function, Utilitas Math., 10 (1976), 347-350.
%H A116550 Donovan Johnson, <a href="/A116550/b116550.txt">Table of n, a(n) for n = 1..10000</a>
%H A116550 László Tóth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Toth2/toth5.html">On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function</a>, JIS, Vol. 12 (2009), Article 09.5.2, function phi**(n).
%F A116550 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).
%F A116550 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
%e A116550 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.
%p A116550 # returns the greatest common unitary divisor of m and n, A225174(m,n)
%p A116550 f:=proc(m,n)
%p A116550    local i,ans;
%p A116550    ans:=1;
%p A116550    for i from 1 to min(m,n) do
%p A116550      if ((m mod i) = 0) and (igcd(i,m/i) = 1)  then
%p A116550        if ((n mod i) = 0) and (igcd(i,n/i) = 1)  then ans:=i; fi;
%p A116550      fi;
%p A116550    od;
%p A116550 ans; end;
%p A116550 A116550:=proc(n)
%p A116550   global f; local ct,m;
%p A116550   ct:=0;
%p A116550   if n = 1 then RETURN(1) else
%p A116550   for m from 1 to n-1 do
%p A116550     if f(m,n)=1 then ct:=ct+1; fi;
%p A116550   od:
%p A116550   fi;
%p A116550   ct;
%p A116550 end; # _N. J. A. Sloane_, May 01 2013
%p A116550 A116550 := proc(n)
%p A116550     local a,k;
%p A116550     a := 0 ;
%p A116550     for k from 1 to n do
%p A116550         if A165430(k,n) = 1 then
%p A116550             a := a+1 ;
%p A116550         end if ;
%p A116550     end do:
%p A116550     a ;
%p A116550 end proc: # _R. J. Mathar_, Jul 21 2016
%t A116550 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 *)
%t A116550 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 *)
%o A116550 (PARI) udivs(n) = {my(d = divisors(n)); select(x->(gcd(x, n/x)==1), d); }
%o A116550 gcud(n, m) = vecmax(setintersect(udivs(n), udivs(m)));
%o A116550 a(n) = if (n==1, 1, sum(k=1, n-1, gcud(n, k) == 1)); \\ _Michel Marcus_, Nov 09 2017
%o A116550 (PARI) phi(x,n) = sumdiv(n, d, moebius(d)*floor(x/d));
%o A116550 a(n) = sumdiv(n, d, (gcd(d, n/d) == 1) * (-1)^omega(d) * phi(n/d,d)); \\ _Amiram Eldar_, Jul 16 2022
%Y A116550 Cf. A225174, A005424, A225175, A225176, A000010, A047994.
%K A116550 nonn
%O A116550 1,3
%A A116550 _Leroy Quet_, Mar 16 2006
%E A116550 More terms from _R. J. Mathar_, Jan 23 2008
%E A116550 Entry revised by _N. J. A. Sloane_, May 01 2013