A186994 Number of maximum subsets of {1, 2, ..., n} containing n and having pairwise coprime elements.

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 maximum (largest possible) subset are 1, n, and powers of primes that have no common factor with n. The cardinalities of maximum subsets is A186971(n).

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

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 maximum 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 maximum 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 * A385433 A056889 A275761

Adjacent sequences: A186991 A186992 A186993 * A186995 A186996 A186997

Keyword

nonn,look,hear,changed

Author

Alois P. Heinz, Mar 01 2011

Status

approved