A339492 T(n, k) = tau(k) + floor(n/k) - 1, where tau = A000005. Triangle read by rows.

1, 2, 2, 3, 2, 2, 4, 3, 2, 3, 5, 3, 2, 3, 2, 6, 4, 3, 3, 2, 4, 7, 4, 3, 3, 2, 4, 2, 8, 5, 3, 4, 2, 4, 2, 4, 9, 5, 4, 4, 2, 4, 2, 4, 3, 10, 6, 4, 4, 3, 4, 2, 4, 3, 4, 11, 6, 4, 4, 3, 4, 2, 4, 3, 4, 2, 12, 7, 5, 5, 3, 5, 2, 4, 3, 4, 2, 6, 13, 7, 5, 5, 3, 5, 2, 4, 3, 4, 2, 6, 2

Offset: 1

Author

Peter Luschny, Dec 31 2020

Keywords

• nonn
• tabl

Comments

A simple path in the divisor graph of {1,...,n} is a sequence of distinct numbers between 1 and n such that if m immediately follows k, then either m divides k or k divides m. Let S(n, k) = divisors(k) union {k*j : j = 2..floor(n/k)}. A path p is only valid if the elements of the path p(k-1) are in S(n, p(k)), for k = 2..n.

Examples

			Row 6 lists the cardinalities of the sets {1, 2, 3, 4, 5, 6}, {1, 2, 4, 6}, {1, 3, 6}, {1, 2, 4}, {1, 5}, {1, 2, 3, 6}.
The triangle starts:
[1]                       1;
[2]                      2, 2;
[3]                    3, 2, 2;
[4]                   4, 3, 2, 3;
[5]                 5, 3, 2, 3, 2;
[6]                6, 4, 3, 3, 2, 4;
[7]              7, 4, 3, 3, 2, 4, 2;
[8]             8, 5, 3, 4, 2, 4, 2, 4;
[9]           9, 5, 4, 4, 2, 4, 2, 4, 3;
[10]        10, 6, 4, 4, 3, 4, 2, 4, 3, 4.
		

Crossrefs

T(n, 1) = A000027(n), T(n, n) = A000005(n), T(2n, n) = A334954(n).

Cf. A339491, A339496, A339489.

Programs

Maple

T := (n, k) -> NumberTheory:-tau(k) + iquo(n, k) - 1:
seq(seq(T(n, k), k = 1..n), n = 1..13);

Formula

T(n, k) = card(divisors(k) union {k*j : j = 2..floor(n/k)}).