Asymptotic estimates for phi functions for subsets of {m+1, m+2,...,n}

Melvyn B. Nathanson, Brooke Orosz

Published 2007-09-18Version 1

Let f(m,n) denote the number of relatively prime subsets of {m+1,m+2,...,n}, and let Phi(m,n) denote the number of subsets A of {m+1,m+2,...,n} such that gcd(A) is relatively prime to n. Let f_k(m,n) and Phi_k(m,n) be the analogous counting functions restricted to sets of cardinality k. Simple explicit formulas and asymptotic estimates are obtained for these four functions.