VOOZH about

URL: https://oeis.org/A084422

⇱ A084422 - OEIS

login
A084422
Number of subsets of integers 1 through n (including the empty set) containing no pair of integers that share a common factor.
31
1, 2, 4, 8, 12, 24, 28, 56, 72, 104, 116, 232, 248, 496, 544, 616, 728, 1456, 1520, 3040, 3232, 3616, 3872, 7744, 8000, 11168, 11904, 14656, 15488, 30976, 31232, 62464, 69888, 76160, 80256, 89856, 91648, 183296, 192640, 208640, 214272, 428544
OFFSET
0,2
COMMENTS
Also the number of subsets of {1,...,n} whose product of elements is equal to the least common multiple of elements. - Michel Marcus, Mar 27 2016
REFERENCES
Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication. [Apparently unpublished as of 2016]
LINKS
N. J. Calkin and A. Granville, On the number of coprime-free sets, Number Theory: New York Seminar 1991-1995 (eds. D. Chudnovsky, et.al.), Springer-Verlag (1996).
Marcel K. Goh and Jonah Saks, Alternating-sum statistics for certain sets of integers, arXiv:2206.12535 [math.CO], 2022.
FORMULA
a(n) = 1 + Sum_{k=1..A036234(n)} A186974(n,k) if n>0; a(0) = 1.
EXAMPLE
Exactly 4 of the 2^4=16 subsets of the integers from 1 through 4 contain a pair of integers that share a common factor; these are {2,4}, {1,2,4}, {2,3,4} and {1,2,3,4}. The other 12 subsets do not; hence a(4)=12.
MATHEMATICA
Prepend[Table[Length@ Select[Rest@ Subsets@ Range@ n, Times @@ # == LCM @@ # &], {n, 22}] + 1, 1] (* Michael De Vlieger, Mar 27 2016 *)
PROG
(PARI) a(n)=nb = 0; S = vector(n, k, k); for (i = 0, 2^n - 1, ss = vecextract(S, i); if (prod(k=1, #ss, ss[k]) == lcm(ss), nb++); ); nb; \\ Michel Marcus, Mar 27 2016
(PARI) a(n, k=1)=if(n<2, return(n+1)); if(gcd(k, n)==1, a(n-1, n*k)) + a(n-1, k) \\ Charles R Greathouse IV, Aug 24 2016
CROSSREFS
Cf. A051026 gives the number of primitive subsets. A087080 gives the number of elements in coprime subsets. A087081 gives the sum of the elements in coprime subsets.
Sequence in context: A330022 A362261 A032473 * A175841 A293601 A171647
KEYWORD
nonn
AUTHOR
Matthew Vandermast, Jun 26 2003
EXTENSIONS
More terms from Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003
STATUS
approved