A096825 Maximal size of an antichain in divisor lattice D(n).

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

Offset: 1

Author

Yuval Dekel (dekelyuval(AT)hotmail.com) and Vladeta Jovovic, Aug 17 2004

Keywords

• nonn

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

Examples

			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
		

Links

• Eric M. Schmidt, Table of n, a(n) for n = 1..10000
• S.-H. Cha, E. G. DuCasse and L. V. Quintas, Graph invariants based on the divides relation and ordered by prime signatures, arXiv:1405.5283 [math.NT] (2014), (2.19).

Crossrefs

Cf. A001055, A008480, A096826, A096827, A253249, A285573.

Programs

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 *)

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
def A096825(n):
    fs = factorint(n)
    return len(list(multiset_combinations(fs,sum(fs.values())//2))) # Chai Wah Wu, Aug 23 2021

Sage

def A096825(n) :
    if n==1 : return 1
    R. = QQ[]; mults = [x[1] for x in factor(n)]
    return prod((t^(m+1)-1)//(t-1) for m in mults)[sum(mults)//2]
# Eric M. Schmidt, May 11 2013

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

Extensions

More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 22 2004