|
|
A096825
|
|
Maximal size of an antichain in divisor lattice D(n).
|
|
18
|
|
|
1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 4, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 3, 1, 2, 2, 2, 2, 3, 1, 2, 1, 2, 1, 4, 2, 2, 2, 2, 1, 4, 2, 2, 2, 2, 2, 2, 1, 2, 2, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
COMMENTS
|
The divisor lattice D(n) is the lattice of the divisors of the natural number n.
Also the number of divisors of n with half (rounded either way) as many prime factors (counting multiplicity) as n. - Gus Wiseman, Aug 24 2018
|
|
LINKS
|
|
|
FORMULA
|
a(n) is the coefficient at x^k in (1+x+...+x^k_1)*...*(1+x+...+x^k_q) where n=p_1^k_1*...*p_q^k_q is the prime factorization of n and k=floor((k_1+...+k_q)/2). - Alec Mihailovs (alec(AT)mihailovs.com), Aug 22 2004
|
|
EXAMPLE
|
There are two maximal size antichains of divisors of 180, namely {12, 18, 20, 30, 45} and {4, 6, 9, 10, 15}. Both have length 5 so a(180) = 5. - Gus Wiseman, Aug 24 2018
|
|
MAPLE
|
a:=proc(n) local klist, x; klist:=ifactors(n)[2, 1..-1, 2]; coeff(normal(mul((1-x^(k+1))/(1-x), k=klist)), x, floor(add(k, k=klist)/2)) end: seq(a(n), n=1..100);
|
|
MATHEMATICA
|
a[n_] := Module[{pp, kk, x}, {pp, kk} = Transpose[FactorInteger[n]]; Coefficient[ Product[ Total[x^Range[0, k]], {k, kk}], x, Quotient[ Total[ kk], 2] ] ]; Array[a, 100] (* Jean-François Alcover, Nov 20 2017 *)
Table[Length[Select[Divisors[n], PrimeOmega[#]==Round[PrimeOmega[n]/2]&]], {n, 50}] (* Gus Wiseman, Aug 24 2018 *)
|
|
PROG
|
(Sage)
if n==1 : return 1
R.<t> = QQ[]; mults = [x[1] for x in factor(n)]
return prod((t^(m+1)-1)//(t-1) for m in mults)[sum(mults)//2]
(PARI) a(n)=if(n<6||isprimepower(n), return(1)); my(d=divisors(n), r=1, u); d=d[2..#d-1]; for(k=0, 2^#d-1, if(hammingweight(k)<=r, next); u=vecextract(d, k); for(i=1, #u, for(j=i+1, #u, if(u[j]%u[i]==0, next(3)))); r=#u); r \\ Charles R Greathouse IV, May 14 2013
(Python)
from sympy import factorint
from sympy.utilities.iterables import multiset_combinations
fs = factorint(n)
return len(list(multiset_combinations(fs, sum(fs.values())//2))) # Chai Wah Wu, Aug 23 2021
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 22 2004
|
|
STATUS
|
approved
|
|
|
|