login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A084422 Number of subsets of integers 1 through n (including the empty set) containing no pair of integers that share a common factor. 29
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

Alois P. Heinz, Table of n, a(n) for n = 0..220

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).

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.

Cf. A036234, A186974.

Sequence in context: A327480 A330022 A032473 * A175841 A293601 A171647

Adjacent sequences:  A084419 A084420 A084421 * A084423 A084424 A084425

KEYWORD

nonn

AUTHOR

Matthew Vandermast, Jun 26 2003

EXTENSIONS

More terms from Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 23 07:54 EDT 2022. Contains 353961 sequences. (Running on oeis4.)