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

Author

Peter Luschny, Dec 29 2020

Keywords

• nonn
• tabf

Comments

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.

Examples

			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].
		

Crossrefs

Cf. A337125 (row length), A339490.

Cf. A339492, A339489, A339496.

Cf. A340114 (a variant problem).

Programs

Maple

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;

Extensions

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