The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A337125 Length of the longest simple path in the divisor graph of {1,...,n}. 4


%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, 303-304.

%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/s10998-008-6227-3">Sur les partitions en chaînes du graphe divisoriel</a>, Period. Math. Hungar. 56(2), 227-239, 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, 189-200, 2001.

%H Paul Erdős and Éric Saias, <a href="https://doi.org/10.4064/AA-73-2-189-198">Sur le graphe divisoriel</a>, Acta Arith. 73(2), 189-198, 1995.

%H Erich Friedman, <a href="https://erich-friedman.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/aa180711-26-4"> On path partitions of the divisor graph</a>, Acta Arith. 192, 329-339, 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), 291-304.

%H O. Roeder, <a href="https://fivethirtyeight.com/features/is-this-bathroom-occupied/">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), 225-240.

%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, 481-488, 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) 115-127.

%F If p prime >= 5, a(p-1) = 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 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.

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 26 01:49 EDT 2021. Contains 346294 sequences. (Running on oeis4.)