OFFSET
1,2
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.
FORMULA
T(n, k) = card(divisors(k) union {k*j : j = 2..floor(n/k)}).
EXAMPLE
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.
MAPLE
T := (n, k) -> NumberTheory:-tau(k) + iquo(n, k) - 1:
seq(seq(T(n, k), k = 1..n), n = 1..13);
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Dec 31 2020
STATUS
approved