cp's OEIS Frontend

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

%I A096825 #29 Aug 23 2021 13:41:03
%S A096825 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,
%T A096825 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,
%U A096825 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
%N A096825 Maximal size of an antichain in divisor lattice D(n).
%C A096825 The divisor lattice D(n) is the lattice of the divisors of the natural number n.
%C A096825 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
%H A096825 Eric M. Schmidt, <a href="/A096825/b096825.txt">Table of n, a(n) for n = 1..10000</a>
%H A096825 S.-H. Cha, E. G. DuCasse and L. V. Quintas, <a href="http://arxiv.org/abs/1405.5283">Graph invariants based on the divides relation and ordered by prime signatures</a>, arXiv:1405.5283 [math.NT] (2014), (2.19).
%F A096825 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
%e A096825 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
%p A096825 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);
%t A096825 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 *)
%t A096825 Table[Length[Select[Divisors[n],PrimeOmega[#]==Round[PrimeOmega[n]/2]&]],{n,50}] (* _Gus Wiseman_, Aug 24 2018 *)
%o A096825 (Sage)
%o A096825 def A096825(n) :
%o A096825     if n==1 : return 1
%o A096825     R.<t> = QQ[]; mults = [x[1] for x in factor(n)]
%o A096825     return prod((t^(m+1)-1)//(t-1) for m in mults)[sum(mults)//2]
%o A096825 # _Eric M. Schmidt_, May 11 2013
%o A096825 (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
%o A096825 (Python)
%o A096825 from sympy import factorint
%o A096825 from sympy.utilities.iterables import multiset_combinations
%o A096825 def A096825(n):
%o A096825     fs = factorint(n)
%o A096825     return len(list(multiset_combinations(fs,sum(fs.values())//2))) # _Chai Wah Wu_, Aug 23 2021
%Y A096825 Cf. A001055, A008480, A096826, A096827, A253249, A285573.
%K A096825 nonn
%O A096825 1,6
%A A096825 Yuval Dekel (dekelyuval(AT)hotmail.com) and _Vladeta Jovovic_, Aug 17 2004
%E A096825 More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 22 2004