The Number of Relatively Prime Subsets of a Finite Union of Sets of Consecutive Integers
Laboratoire de Mathématiques Pures et Appliquées
Université du Littoral
Department of Statistics
University of British Columbia
Vancouver, BC V6T 1Z4
Department of Mathematics
St. Catharines, ON L2S 3A1
Let A be a finite union of disjoint sets of consecutive integers
and let n be a positive integer.
We give a formula for the number of relatively
prime subsets (resp., relatively prime subsets of cardinality k)
of A, which generalizes results of Nathanson, El Bachraoui
and others. We give as well similar formulas for the number of subsets
with gcd coprime to n.
Full version: pdf,
Received November 10 2011;
revised versions received November 11 2011; June 10 2013; September 17 2013; January 27 2014.
Published in Journal of Integer Sequences, February 16 2014.
Journal of Integer Sequences home page