OFFSET
1,2
COMMENTS
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
REFERENCES
Andrew Pollington, There is a long path in the divisor graph, Ars Combinatoria 16 (Jan. 1983), B, 303-304.
LINKS
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.
FORMULA
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
EXAMPLE
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)
CROSSREFS
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).
KEYWORD
nonn,hard
AUTHOR
Nathan McNew, Aug 17 2020
EXTENSIONS
a(74) corrected by Rob Pratt, Dec 28 2020
STATUS
approved