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,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).

Sequence in context: A243069 A342496 A061984 * A063208 A343912 A262265

Adjacent sequences: A337122 A337123 A337124 * A337126 A337127 A337128

Keyword

nonn,hard

Author

Nathan McNew, Aug 17 2020

Extensions

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

Status

approved