A084422
Number of subsets of integers 1 through n (including the empty set) containing no pair of integers that share a common factor.
Original entry on oeis.org
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
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.
- Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication. [Apparently unpublished as of 2016]
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.
-
Prepend[Table[Length@ Select[Rest@ Subsets@ Range@ n, Times @@ # == LCM @@ # &], {n, 22}] + 1, 1] (* Michael De Vlieger, Mar 27 2016 *)
-
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
-
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
More terms from Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003
A087080
Number of elements in the coprime subsets of the integers 1 to n.
Original entry on oeis.org
0, 1, 4, 12, 20, 52, 60, 148, 196, 300, 332, 780, 828, 1904, 2080, 2348, 2812, 6352, 6608, 14736, 15632, 17456, 18640, 41152, 42432, 60912, 64800, 80928, 85408, 186304, 187584, 406400, 457344, 497472, 523456, 585280, 596288, 1284224, 1348032, 1457792, 1495424
Offset: 0
Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003
a(4)=20 since the 12 coprime subsets of (1,2,3,4) are ( ) (1) (2) (3) (4) (1,2) (1,3) (1,4) (2,3) (3,4) (1,2,3) (1,3 4) and these contain 20 elements.
- Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication.
A087077 gives the number of elements in the primitive subsets.
A084422 gives the number coprime subsets.
A087081 gives the sum of the elements in coprime subsets.
-
iscoprime(v) = {local(i); for (i=1, #v-1, for (j=i+1, #v, if (gcd(v[i], v[j]) != 1, return (0)););); return (1);}
a(n) = {sn = vector(n, i, i); pset = vector(1<<#sn, i, vecextract(sn, i-1)); nb = 0; for (i=1, #pset, if (iscoprime(pset[i]), nb += #pset[i]);); return (nb);} \\ Michel Marcus, Jul 12 2013
A087078
Sum of the elements in the primitive subsets of the integers 1 to n.
Original entry on oeis.org
0, 1, 3, 11, 22, 73, 115, 341, 545, 1141, 1864, 4849, 6505, 16285, 26245, 47093, 68981, 163937, 221957, 517937, 726737, 1312865, 2093745, 4753105, 5953777, 12335601, 19516365, 34112821, 48603289, 107522689, 137759953, 302797921, 422868865
Offset: 0
Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003
a(4)=22 since the primitive subsets of (1,2,3,4) are ( ) (1) (2) (3) (4) (2,3) (3,4) and the sum of the elements in these subsets is 22.
- R. K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, New York, (1994).
A051026 gives the number of primitive subsets.
A087077 gives the number of elements in the primitive subsets.
A087081 gives the sum of the elements in the coprime subsets.
Showing 1-3 of 3 results.
Comments