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

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, 31, 3, 51, 3, 63, 11, 11, 11, 103, 3, 11, 11, 79, 3, 51, 3, 31, 31, 11, 3, 191, 7, 31, 11, 31, 3, 79, 11, 79, 11, 11, 3, 175, 3, 11, 31, 127, 11, 51, 3, 31, 11, 51

Offset: 1

Author

Geoffrey Critzer, Jun 04 2015

Keywords

• nonn

Comments

For prime p, a(p)=3.

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

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

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

Examples

			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}.
		

Links

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

Crossrefs

Cf. A002033, A007047, A074206, A107311, A378219 (Dirichlet inverse).

Programs

Maple

with(numtheory):
b:= proc(n) option remember: 1+ `if`(n=1, 0,
       add(b(d), d=divisors(n) minus {n}))
    end:
a:= n-> add(b(d), d=divisors(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Jun 04 2015

Mathematica

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}]

Formula

Dirichlet g.f.: zeta(s)^2*A(s) where A(s) is the Dirichlet g.f. for A074206. - Geoffrey Critzer, May 23 2018

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

a(n) = 4*A002033(n-1) - 1 for n > 1. - Geoffrey Critzer, Aug 19 2020