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,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;
[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

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

Cf. A339491, A339496, A339489.

Sequence in context: A230296 A278317 A086454 * A069360 A175509 A213023

Adjacent sequences: A339489 A339490 A339491 * A339493 A339494 A339495

Keyword

nonn,tabl

Author

Peter Luschny, Dec 31 2020

Status

approved