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,3

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.

Links

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

Example

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

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;

Crossrefs

Cf. A337125 (row length), A339490.

Cf. A339492, A339489, A339496.

Cf. A340114 (a variant problem).

Sequence in context: A159803 A308934 A058741 * A346871 A291712 A074945

Adjacent sequences: A339488 A339489 A339490 * A339492 A339493 A339494

Keyword

nonn,tabf

Author

Peter Luschny, Dec 29 2020

Extensions

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

Status

approved