|
|
A084422
|
|
Number of subsets of integers 1 through n (including the empty set) containing no pair of integers that share a common factor.
|
|
30
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003
|
|
STATUS
|
approved
|
|
|
|