A339490 -id:A339490 - cp's OEIS frontend

A337125 Length of the longest simple path in the divisor graph of {1,...,n}.

1, 2, 3, 4, 4, 6, 6, 7, 8, 9, 9, 11, 11, 12, 13, 14, 14, 16, 16, 17, 18, 19, 19, 21, 21, 22, 23, 24, 24, 26, 26, 27, 28, 28, 29, 30, 30, 30, 31, 32, 32, 34, 34, 36, 37, 37, 37, 39, 39, 41, 42, 43, 43, 44, 45, 46, 47, 47, 47, 49, 49, 49, 50, 51, 51, 53, 53, 54

Offset: 1

Nathan McNew, Aug 17 2020

a(n) is the length of the longest simple path in the graph on vertices {1,...,n} in which two vertices are connected by an edge if one divides another.
Saias shows that there exist positive constants b and c such that for sufficiently large n, b*n/log n < a(n) < c*n/log n.
The definition can also be formulated as: a(n) is the length of the longest sequence of distinct numbers between 1 and n such that if k immediately follows m, then either k divides m or m divides k. - Peter Luschny, Dec 28 2020
Can be formulated as an optimal subtour problem by introducing a depot node 0 that is adjacent to all other nodes. An integer linear programming formulation is as follows. For {i,j} in E, let binary decision variable x_{i,j} indicate whether edge {i,j} is traversed, and for i in N let binary decision variable y_i indicate whether node i is visited. The objective is to maximize Sum_{i in N \ {0}} y_i. The constraints are Sum_{{i,j} in E: k in {i,j}} x_{i,j} = 2 y_k for all k in N, y_0 = 1, as well as (dynamically generated) generalized subtour elimination constraints Sum_{i in S, j in S: {i,j} in E} x_{i,j} <= Sum_{i in S \ {k}} y_i for all S subset N \ {0} and k in S. - Rob Pratt, Dec 28 2020

			For n = 7, the divisor graph has the path 7-1-4-2-6-3, with length 6, but it is not possible to include all 7 integers into a single path, so a(7) = 6.
Other examples for small n (from _N. J. A. Sloane_, Oct 12 2021):
1: 1 (1)
2: 1-2 (2)
3: 2-1-3 (3)
4: 3-1-2-4 (4)
5: 3-1-2-4 (4)
6: 5-1-3-6-2-4 (6)
8: 5-1-3-6-2-4-8 (7)
9: insert 9 between 1 and 3 (8)
10: add 10 to the start (9)

Andrew Pollington, There is a long path in the divisor graph, Ars Combinatoria 16 (Jan. 1983), B, 303-304.

Rob Pratt, Table of n, a(n) for n = 1..200, the first 75 terms by Nathan McNew.
A. Chadozeau, Sur les partitions en chaînes du graphe divisoriel, Period. Math. Hungar. 56(2), 227-239, 2008.
G. Chartrand, R. Muntean, V. Saenpholphat, and P. Zhang, Which graphs are divisor graphs? Cong. Numerantium 151, 189-200, 2001.
Paul Erdős and Éric Saias, Sur le graphe divisoriel, Acta Arith. 73(2), 189-198, 1995.
Erich Friedman, Divisor chains (Problem of the Month (November 1998)).
Nathan McNew, Counting primitive subsets and other statistics of the divisor graph of {1,2,...,n}, arXiv:1808.04923v2 [math.NT], 2020. Published in: European Journal of Combinatorics, Volume 92, February 2021.
Paul Melotti and Éric Saias, On path partitions of the divisor graph, Acta Arith. 192, 329-339, 2020.
Carl Pomerance, On the longest simple path in the divisor graph, Proc. Southeastern Conf. Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, 1983, Cong. Num. 40 (1983), 291-304.
O. Roeder, Solution to last week’s Riddler Classic, FiveThirtyEight.
E. Saias, Applications des entiers à diviseurs denses, Acta Arithmetica, 83, 3 (1998), 225-240.
E. Saias, Étude du graphe divisoriel 3, Rend. Circ. Mat. Palermo (2) 52 no. 3, 481-488, 2003.
G. Tenenbaum, Sur un problème de crible et ses applications. II. Corrigendum et étude du graphe divisoriel, Ann. Sci. École Norm. Sup. (4) 28 (1995) 115-127.

Cf. A034298 (the smallest possible value of the largest number in a divisor chain of length n).
Cf. A035280 (divisor loops).
Cf. A320536 (least number of paths required to cover the divisor graph).
Cf. A339490 (number of longest paths).
Cf. A339491 (lexicographically earliest longest path).
A347698 gives n - a(n).

If p prime >= 5, a(p-1) = a(p). - Bernard Schott, Dec 28 2020

For 1 <= n <= 33: a(n) = floor(n*5/6) + [(n+1) mod 6 <> 0], where [] are the Iverson brackets. - Peter Luschny, Jan 02 2021

a(74) corrected by Rob Pratt, Dec 28 2020

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

Original entry on oeis.org

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

cp's OEIS Frontend

A337125 Length of the longest simple path in the divisor graph of {1,...,n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions