A339492 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

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.

LINKS

Table of n, a(n) for n=1..91.

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;