|
|
A116550
|
|
The bi-unitary analog of Euler's totient function of n.
|
|
10
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
|
|
REFERENCES
|
M. Lal, H. Wareham and R. Mifflin, Iterates of the bi-unitary totient function, Utilitas Math., 10 (1976), 347-350.
|
|
LINKS
|
|
|
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
|
|
EXAMPLE
|
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.
|
|
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;
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;
local a, k;
a := 0 ;
for k from 1 to n do
a := a+1 ;
end if ;
end do:
a ;
|
|
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 *)
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|