%I
%S 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,
%T 23,24,24,26,26,27,28,28,29,30,30,30,31,32,32,34,34,36,37,37,37,39,39,
%U 41,42,43,43,44,45,46,47,47,47,49,49,49,50,51,51,53,53,54
%N Length of the longest simple path in the divisor graph of {1,...,n}.
%C 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.
%C 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.
%C 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
%C 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
%D Andrew Pollington, There is a long path in the divisor graph, Ars Combinatoria 16 (Jan. 1983), B, 303304.
%H Rob Pratt, <a href="/A337125/b337125.txt">Table of n, a(n) for n = 1..200</a>, the first 75 terms by Nathan McNew.
%H A. Chadozeau, <a href="https://doi.org/10.1007/s1099800862273">Sur les partitions en chaînes du graphe divisoriel</a>, Period. Math. Hungar. 56(2), 227239, 2008.
%H G. Chartrand, R. Muntean, V. Saenpholphat, and P. Zhang, <a href="http://faculty.nps.edu/rgera/papers/WHICH%20GRAPHS%20ARE%20DIVISOR%20GRAPHS.PDF"> Which graphs are divisor graphs?</a> Cong. Numerantium 151, 189200, 2001.
%H Paul Erdős and Éric Saias, <a href="https://doi.org/10.4064/AA732189198">Sur le graphe divisoriel</a>, Acta Arith. 73(2), 189198, 1995.
%H Erich Friedman, <a href="https://erichfriedman.github.io/mathmagic/1198.html"> Divisor chains (Problem of the Month (November 1998))</a>.
%H Nathan McNew, <a href="https://arxiv.org/abs/1808.04923">Counting primitive subsets and other statistics of the divisor graph of {1,2,...,n}</a>, arXiv:1808.04923v2 [math.NT], 2020. Published in: <a href="https://doi.org/10.1016/j.ejc.2020.103237">European Journal of Combinatorics</a>, Volume 92, February 2021.
%H Paul Melotti and Éric Saias, <a href="https://doi.org/10.4064/aa180711264"> On path partitions of the divisor graph</a>, Acta Arith. 192, 329339, 2020.
%H Carl Pomerance, <a href="https://math.dartmouth.edu/~carlp/divisorgraph.pdf">On the longest simple path in the divisor graph</a>, Proc. Southeastern Conf. Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, 1983, Cong. Num. 40 (1983), 291304.
%H O. Roeder, <a href="https://fivethirtyeight.com/features/isthisbathroomoccupied/">Solution to last week’s Riddler Classic</a>, FiveThirtyEight.
%H E. Saias, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa83/aa8333.pdf">Applications des entiers à diviseurs denses</a>, Acta Arithmetica, 83, 3 (1998), 225240.
%H E. Saias, <a href="https://doi.org/10.1007/BF02872766">Étude du graphe divisoriel 3</a>, Rend. Circ. Mat. Palermo (2) 52 no. 3, 481488, 2003.
%H G. Tenenbaum, <a href="https://doi.org/10.24033/asens.1710">Sur un problème de crible et ses applications. II. Corrigendum et étude du graphe divisoriel</a>, Ann. Sci. École Norm. Sup. (4) 28 (1995) 115127.
%F If p prime >= 5, a(p1) = a(p).  _Bernard Schott_, Dec 28 2020
%F 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
%e For n = 7, the divisor graph has the path 714263, with length 6, but it is not possible to include all 7 integers into a single path, so a(7) = 6.
%Y Cf. A034298 (the smallest possible value of the largest number in a divisor chain of length n).
%Y Cf. A035280 (divisor loops).
%Y Cf. A320536 (least number of paths required to cover the divisor graph).
%Y Cf. A339490 (number of longest paths).
%Y Cf. A339491 (lexicographically earliest longest path).
%K nonn,hard
%O 1,2
%A _Nathan McNew_, Aug 17 2020
%E a(74) corrected by _Rob Pratt_, Dec 28 2020
