cp's OEIS Frontend

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

%I A339491 #16 Mar 14 2021 20:37:24
%S A339491 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,
%T A339491 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,
%U A339491 3,9,1,7,5,10,2,8,4,12,6,3,9,1,7
%N A339491 Lexicographically earliest longest simple path in the divisor graph of {1,...,n}. Irregular triangle read by rows.
%C A339491 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.
%e A339491 1:                     [1],
%e A339491 2:                    [1, 2],
%e A339491 3:                  [2, 1, 3],
%e A339491 4:                 [2, 4, 1, 3],
%e A339491 5:                 [2, 4, 1, 3],
%e A339491 6:              [3, 6, 2, 4, 1, 5],
%e A339491 7:              [3, 6, 2, 4, 1, 5],
%e A339491 8:             [3, 6, 2, 4, 8, 1, 5],
%e A339491 9:            [4, 8, 2, 6, 3, 9, 1, 5],
%e A339491 10:         [4, 8, 1, 5, 10, 2, 6, 3, 9],
%e A339491 11:         [4, 8, 1, 5, 10, 2, 6, 3, 9],
%e A339491 12:      [5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7],
%e A339491 13:      [5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7],
%e A339491 14:     [5, 10, 1, 7, 14, 2, 8, 4, 12, 6, 3, 9],
%e A339491 15:   [6, 12, 4, 8, 1, 7, 14, 2, 10, 5, 15, 3, 9],
%e A339491 16:  [6, 12, 4, 8, 16, 1, 7, 14, 2, 10, 5, 15, 3, 9].
%p A339491 with(Iterator):
%p A339491 DivisorPath := proc(n, k) local c, p, w, isok;
%p A339491     isok := proc(A) local e, i, di; e := nops(A) - 1;
%p A339491        di := (n, k) -> evalb(irem(n, k) = 0 or irem(k, n) = 0):
%p A339491        for i from 1 to e while di(A[i], A[i+1]) do od;
%p A339491        return evalb(i = e + 1) end:
%p A339491     for c in Combination(n, k) do
%p A339491        for p in Permute([seq(j + 1, j in c)], k) do
%p A339491            w := convert(p, list);
%p A339491            if isok(w) then return w fi:
%p A339491 od  od  end:
%p A339491 A337125 := [1, 2, 3, 4, 4, 6, 6, 7, 8, 9, 9]:
%p A339491 for n from 1 to 9 do DivisorPath(n, A337125[n]) od;
%Y A339491 Cf. A337125 (row length), A339490.
%Y A339491 Cf. A339492, A339489, A339496.
%Y A339491 Cf. A340114 (a variant problem).
%K A339491 nonn,tabf
%O A339491 1,3
%A A339491 _Peter Luschny_, Dec 29 2020
%E A339491 Signposting added to first comment by _Peter Munn_, Mar 12 2021