cp's OEIS Frontend

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

%I A337125 #65 Oct 12 2021 14:17:08
%S A337125 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 A337125 23,24,24,26,26,27,28,28,29,30,30,30,31,32,32,34,34,36,37,37,37,39,39,
%U A337125 41,42,43,43,44,45,46,47,47,47,49,49,49,50,51,51,53,53,54
%N A337125 Length of the longest simple path in the divisor graph of {1,...,n}.
%C A337125 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 A337125 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 A337125 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 A337125 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 A337125 Andrew Pollington, There is a long path in the divisor graph, Ars Combinatoria 16 (Jan. 1983), B, 303-304.
%H A337125 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 A337125 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 A337125 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 A337125 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 A337125 Erich Friedman, <a href="https://erich-friedman.github.io/mathmagic/1198.html"> Divisor chains (Problem of the Month (November 1998))</a>.
%H A337125 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 A337125 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 A337125 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 A337125 O. Roeder, <a href="https://fivethirtyeight.com/features/is-this-bathroom-occupied/">Solution to last week’s Riddler Classic</a>, FiveThirtyEight.
%H A337125 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 A337125 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 A337125 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 A337125 If p prime >= 5, a(p-1) = a(p). - _Bernard Schott_, Dec 28 2020
%F A337125 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 A337125 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.
%e A337125 Other examples for small n (from _N. J. A. Sloane_, Oct 12 2021):
%e A337125 1: 1 (1)
%e A337125 2: 1-2 (2)
%e A337125 3: 2-1-3 (3)
%e A337125 4: 3-1-2-4 (4)
%e A337125 5: 3-1-2-4 (4)
%e A337125 6: 5-1-3-6-2-4 (6)
%e A337125 8: 5-1-3-6-2-4-8 (7)
%e A337125 9: insert 9 between 1 and 3 (8)
%e A337125 10: add 10 to the start (9)
%Y A337125 Cf. A034298 (the smallest possible value of the largest number in a divisor chain of length n).
%Y A337125 Cf. A035280 (divisor loops).
%Y A337125 Cf. A320536 (least number of paths required to cover the divisor graph).
%Y A337125 Cf. A339490 (number of longest paths).
%Y A337125 Cf. A339491 (lexicographically earliest longest path).
%Y A337125 A347698 gives n - a(n).
%K A337125 nonn,hard
%O A337125 1,2
%A A337125 _Nathan McNew_, Aug 17 2020
%E A337125 a(74) corrected by _Rob Pratt_, Dec 28 2020