login
Number of nonempty chains in the divides relation on the divisors of n.
72

%I #37 Aug 21 2020 11:52:51

%S 1,3,3,7,3,11,3,15,7,11,3,31,3,11,11,31,3,31,3,31,11,11,3,79,7,11,15,

%T 31,3,51,3,63,11,11,11,103,3,11,11,79,3,51,3,31,31,11,3,191,7,31,11,

%U 31,3,79,11,79,11,11,3,175,3,11,31,127,11,51,3,31,11,51

%N Number of nonempty chains in the divides relation on the divisors of n.

%C For prime p, a(p)=3.

%C a(2^k) = 2^(k+1)-1.

%C For integers of the form n = p_1*p_2*...*p_k we have a(n) = A007047(k).

%C The value of a(n) depends only on the exponents in the prime factorization of n.

%H Alois P. Heinz, <a href="/A253249/b253249.txt">Table of n, a(n) for n = 1..20000</a>

%F Dirichlet g.f.: zeta(s)^2*A(s) where A(s) is the Dirichlet g.f. for A074206. - _Geoffrey Critzer_, May 23 2018

%F Sum_{k=1..n} a(k) ~ -4*n^r / (r*Zeta'(r)), where r = A107311 = 1.728647238998183618135103... is the root of the equation zeta(r) = 2. - _Vaclav Kotesovec_, Jan 31 2019

%F a(n) = 4*A002033(n-1) - 1 for n > 1. - _Geoffrey Critzer_, Aug 19 2020

%e a(10) = 11 because we have: {1}, {2}, {5}, {10}, {1|2}, {1|5}, {1|10}, {2|10}, {5|10}, {1|2|10}, {1|5|10}.

%p with(numtheory):

%p b:= proc(n) option remember: 1+ `if`(n=1, 0,

%p add(b(d), d=divisors(n) minus {n}))

%p end:

%p a:= n-> add(b(d), d=divisors(n)):

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Jun 04 2015

%t Table[Total[Table[Length[Select[Subsets[Divisors[n], {k}],Apply[And, Map[Apply[Divisible, #] &,Partition[Reverse[#], 2, 1]]] &]], {k, 1,PrimeOmega[n] + 1}]], {n, 1, 100}]

%Y Cf. A002033, A007047, A074206, A107311.

%K nonn

%O 1,2

%A _Geoffrey Critzer_, Jun 04 2015