|
|
A186994
|
|
Number of maximal subsets of {1, 2, ..., n} containing n and having pairwise coprime elements.
|
|
6
|
|
|
1, 1, 1, 1, 2, 1, 2, 1, 3, 2, 6, 1, 6, 2, 3, 2, 8, 1, 8, 2, 4, 2, 8, 1, 8, 4, 8, 6, 24, 1, 24, 6, 10, 6, 15, 2, 30, 6, 10, 3, 30, 2, 30, 6, 5, 6, 30, 2, 30, 6, 20, 12, 60, 4, 30, 6, 20, 12, 60, 2, 60, 12, 10, 12, 36, 4, 72, 12, 24, 3, 72, 4, 72, 12, 12, 12, 36
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
The elements of a maximal subset are 1, n, and powers of primes that have no common factor with n. The cardinalities of maximal subsets is A186971(n).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Product_{p in Primes with p<n and GCD(n,p)=1} floor(log_p(n)).
|
|
EXAMPLE
|
a(5) = 2 because there are 2 maximal subsets of {1,2,3,4,5} containing 5 and having pairwise coprime elements: {1,2,3,5}, {1,3,4,5}.
a(9) = 3, the maximal subsets are {1,2,5,7,9}, {1,4,5,7,9}, {1,5,7,8,9}.
|
|
MAPLE
|
with(numtheory):
a:= n-> mul(ilog[j](n), j={ithprime(i)$i=1..pi(n)} minus factorset(n)):
seq(a(n), n=1..200);
|
|
MATHEMATICA
|
a[n_] := Product[Log[p, n] // Floor, {p, Select[Range[n-1], PrimeQ[#] && GCD[n, #] == 1&]}]; Table[a[n], {n, 1, 200}] (* Jean-François Alcover, Dec 09 2014, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|