Journal of Integer Sequences, Vol. 17 (2014), Article 14.3.7

The Number of Relatively Prime Subsets of a Finite Union of Sets of Consecutive Integers

Mohamed Ayad
Laboratoire de Mathématiques Pures et Appliquées
Université du Littoral
F-62228 Calais

Vincenzo Coia
Department of Statistics
University of British Columbia
Vancouver, BC V6T 1Z4

Omar Kihel
Department of Mathematics
Brock University
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,    dvi,    ps,    latex    

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.

Return to Journal of Integer Sequences home page