login
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
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
Cf. A186971. Rightmost elements in rows of A186972.
Sequence in context: A269572 A029198 A029175 * A056889 A275761 A232396
KEYWORD
nonn,look,hear
AUTHOR
Alois P. Heinz, Mar 01 2011
STATUS
approved