A339496 -id:A339496 - cp's OEIS frontend

A339491 Lexicographically earliest longest simple path in the divisor graph of {1,...,n}. Irregular triangle read by rows.

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

Offset: 1

Peter Luschny, Dec 29 2020

A simple path in the divisor graph of {1,...,n} is a sequence of distinct numbers between 1 and n such that if k immediately follows m, then either k divides m or m divides k. For more information, references and links see A337125.

			1:                     [1],
2:                    [1, 2],
3:                  [2, 1, 3],
4:                 [2, 4, 1, 3],
5:                 [2, 4, 1, 3],
6:              [3, 6, 2, 4, 1, 5],
7:              [3, 6, 2, 4, 1, 5],
8:             [3, 6, 2, 4, 8, 1, 5],
9:            [4, 8, 2, 6, 3, 9, 1, 5],
10:         [4, 8, 1, 5, 10, 2, 6, 3, 9],
11:         [4, 8, 1, 5, 10, 2, 6, 3, 9],
12:      [5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7],
13:      [5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7],
14:     [5, 10, 1, 7, 14, 2, 8, 4, 12, 6, 3, 9],
15:   [6, 12, 4, 8, 1, 7, 14, 2, 10, 5, 15, 3, 9],
16:  [6, 12, 4, 8, 16, 1, 7, 14, 2, 10, 5, 15, 3, 9].

Cf. A337125 (row length), A339490.
Cf. A339492, A339489, A339496.
Cf. A340114 (a variant problem).

with(Iterator):
DivisorPath := proc(n, k) local c, p, w, isok;
    isok := proc(A) local e, i, di; e := nops(A) - 1;
       di := (n, k) -> evalb(irem(n, k) = 0 or irem(k, n) = 0):
       for i from 1 to e while di(A[i], A[i+1]) do od;
       return evalb(i = e + 1) end:
    for c in Combination(n, k) do
       for p in Permute([seq(j + 1, j in c)], k) do
           w := convert(p, list);
           if isok(w) then return w fi:
od  od  end:
A337125 := [1, 2, 3, 4, 4, 6, 6, 7, 8, 9, 9]:
for n from 1 to 9 do DivisorPath(n, A337125[n]) od;

Signposting added to first comment by Peter Munn, Mar 12 2021

A339489 T(n, k) = Product(divisors(k) union {k*j : j = 2..floor(n/k)}). Triangle read by rows.

Original entry on oeis.org

1, 2, 2, 6, 2, 3, 24, 8, 3, 8, 120, 8, 3, 8, 5, 720, 48, 18, 8, 5, 36, 5040, 48, 18, 8, 5, 36, 7, 40320, 384, 18, 64, 5, 36, 7, 64, 362880, 384, 162, 64, 5, 36, 7, 64, 27, 3628800, 3840, 162, 64, 50, 36, 7, 64, 27, 100, 39916800, 3840, 162, 64, 50, 36, 7, 64, 27, 100, 11

Offset: 1

Peter Luschny, Dec 31 2020

For the connection with paths in the divisor graph of {1,...,n} see the comment in A339492.

			The triangle starts:
[1]                            1;
[2]                           2, 2;
[3]                         6, 2, 3;
[4]                       24, 8, 3, 8;
[5]                     120, 8, 3, 8, 5;
[6]                  720, 48, 18, 8, 5, 36;
[7]                5040, 48, 18, 8, 5, 36, 7;
[8]             40320, 384, 18, 64, 5, 36, 7, 64;
[9]          362880, 384, 162, 64, 5, 36, 7, 64, 27;
[10]      3628800, 3840, 162, 64, 50, 36, 7, 64, 27, 100;

T(n, 1) = A000142(n), T(n, n) = A007955(n).

Cf. A339491, A339492, A339496.

t := (n, k) -> NumberTheory:-Divisors(k) union {seq(k*j, j=2..n/k)}:
T := (n, k) -> mul(j, j = t(n, k)):
for n from 1 to 10 do seq(T(n, k), k=1..n) od;

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

Original entry on oeis.org

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

Peter Luschny, Dec 31 2020

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.

			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.

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

Cf. A339491, A339496, A339489.

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

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

cp's OEIS Frontend

A339491 Lexicographically earliest longest simple path in the divisor graph of {1,...,n}. Irregular triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Extensions

A339489 T(n, k) = Product(divisors(k) union {k*j : j = 2..floor(n/k)}). Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula