A339491 -id:A339491 - cp's OEIS frontend

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

Nathan McNew, Aug 17 2020

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

			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)

Andrew Pollington, There is a long path in the divisor graph, Ars Combinatoria 16 (Jan. 1983), B, 303-304.

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.

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

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

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

A339489 T(n, k) = Product(divisors(k) union {k*j : j = 2..floor(n/k)}). Triangle read by rows.

Original entry on oeis.org

1, 2, 2, 6, 2, 3, 24, 8, 3, 8, 120, 8, 3, 8, 5, 720, 48, 18, 8, 5, 36, 5040, 48, 18, 8, 5, 36, 7, 40320, 384, 18, 64, 5, 36, 7, 64, 362880, 384, 162, 64, 5, 36, 7, 64, 27, 3628800, 3840, 162, 64, 50, 36, 7, 64, 27, 100, 39916800, 3840, 162, 64, 50, 36, 7, 64, 27, 100, 11

Offset: 1

Peter Luschny, Dec 31 2020

For the connection with paths in the divisor graph of {1,...,n} see the comment in A339492.

			The triangle starts:
[1]                            1;
[2]                           2, 2;
[3]                         6, 2, 3;
[4]                       24, 8, 3, 8;
[5]                     120, 8, 3, 8, 5;
[6]                  720, 48, 18, 8, 5, 36;
[7]                5040, 48, 18, 8, 5, 36, 7;
[8]             40320, 384, 18, 64, 5, 36, 7, 64;
[9]          362880, 384, 162, 64, 5, 36, 7, 64, 27;
[10]      3628800, 3840, 162, 64, 50, 36, 7, 64, 27, 100;

T(n, 1) = A000142(n), T(n, n) = A007955(n).

Cf. A339491, A339492, A339496.

t := (n, k) -> NumberTheory:-Divisors(k) union {seq(k*j, j=2..n/k)}:
T := (n, k) -> mul(j, j = t(n, k)):
for n from 1 to 10 do seq(T(n, k), k=1..n) od;

A339492 T(n, k) = tau(k) + floor(n/k) - 1, where tau = A000005. Triangle read by rows.

Original entry on oeis.org

1, 2, 2, 3, 2, 2, 4, 3, 2, 3, 5, 3, 2, 3, 2, 6, 4, 3, 3, 2, 4, 7, 4, 3, 3, 2, 4, 2, 8, 5, 3, 4, 2, 4, 2, 4, 9, 5, 4, 4, 2, 4, 2, 4, 3, 10, 6, 4, 4, 3, 4, 2, 4, 3, 4, 11, 6, 4, 4, 3, 4, 2, 4, 3, 4, 2, 12, 7, 5, 5, 3, 5, 2, 4, 3, 4, 2, 6, 13, 7, 5, 5, 3, 5, 2, 4, 3, 4, 2, 6, 2

Offset: 1

Peter Luschny, Dec 31 2020

A simple path in the divisor graph of {1,...,n} is a sequence of distinct numbers between 1 and n such that if m immediately follows k, then either m divides k or k divides m. Let S(n, k) = divisors(k) union {k*j : j = 2..floor(n/k)}. A path p is only valid if the elements of the path p(k-1) are in S(n, p(k)), for k = 2..n.

			Row 6 lists the cardinalities of the sets {1, 2, 3, 4, 5, 6}, {1, 2, 4, 6}, {1, 3, 6}, {1, 2, 4}, {1, 5}, {1, 2, 3, 6}.
The triangle starts:
[1]                       1;
[2]                      2, 2;
[3]                    3, 2, 2;
[4]                   4, 3, 2, 3;
[5]                 5, 3, 2, 3, 2;
[6]                6, 4, 3, 3, 2, 4;
[7]              7, 4, 3, 3, 2, 4, 2;
[8]             8, 5, 3, 4, 2, 4, 2, 4;
[9]           9, 5, 4, 4, 2, 4, 2, 4, 3;
[10]        10, 6, 4, 4, 3, 4, 2, 4, 3, 4.

T(n, 1) = A000027(n), T(n, n) = A000005(n), T(2n, n) = A334954(n).

Cf. A339491, A339496, A339489.

T := (n, k) -> NumberTheory:-tau(k) + iquo(n, k) - 1:
seq(seq(T(n, k), k = 1..n), n = 1..13);

T(n, k) = card(divisors(k) union {k*j : j = 2..floor(n/k)}).

A339496 T(n, k) = Sum(divisors(k) union {k*j : j = 2..floor(n/k)}). Triangle read by rows.

Original entry on oeis.org

1, 3, 3, 6, 3, 4, 10, 7, 4, 7, 15, 7, 4, 7, 6, 21, 13, 10, 7, 6, 12, 28, 13, 10, 7, 6, 12, 8, 36, 21, 10, 15, 6, 12, 8, 15, 45, 21, 19, 15, 6, 12, 8, 15, 13, 55, 31, 19, 15, 16, 12, 8, 15, 13, 18, 66, 31, 19, 15, 16, 12, 8, 15, 13, 18, 12, 78, 43, 31, 27, 16, 24, 8, 15, 13, 18, 12, 28

Offset: 1

Peter Luschny, Dec 31 2020

For the connection with paths in the divisor graph of {1,...,n} see the comment in A339492.

			The triangle starts:
[1]                       1;
[2]                      3, 3;
[3]                    6, 3, 4;
[4]                  10, 7, 4, 7;
[5]                15, 7, 4, 7, 6;
[6]              21, 13, 10, 7, 6, 12;
[7]            28, 13, 10, 7, 6, 12, 8;
[8]          36, 21, 10, 15, 6, 12, 8, 15;
[9]        45, 21, 19, 15, 6, 12, 8, 15, 13;
[10]     55, 31, 19, 15, 16, 12, 8, 15, 13, 18.

T(n, 1) = A000217(n), T(n, n) = A000203(n), T(2n, n) = A224880(n).

Cf. A339491, A339492, A339489.

t := (n, k) -> NumberTheory:-Divisors(k) union {seq(k*j,j=2..n/k)}:
T := (n, k) -> add(j, j = t(n, k)):
for n from 1 to 10 do seq(T(n, k), k=1..n) od;

A339490 Number of longest simple paths in the divisor graph of {1,...,n}.

Original entry on oeis.org

1, 2, 2, 4, 8, 4, 8, 16, 16, 40, 40, 8, 12, 24, 88, 176, 192, 48, 64, 224, 704, 896, 896, 32, 140, 72, 72, 312, 312, 88, 88, 176

Offset: 1

Peter Luschny, Dec 27 2020

			The longest paths for n = 13. The ones marked with (*) are also the longest paths for n = 12.
[5, 10, 2,  8, 4, 12, 6,  3, 9,  1,  7], (*)
[5, 10, 2,  8, 4, 12, 6,  3, 9,  1, 11], (*)
[5, 10, 2,  8, 4, 12, 6,  3, 9,  1, 13],
[7,  1, 5, 10, 2,  8, 4, 12, 6,  3,  9], (*)
[7,  1, 9,  3, 6, 12, 4,  8, 2, 10,  5], (*)
[9,  3, 6, 12, 4,  8, 2, 10, 5,  1,  7], (*)
[9,  3, 6, 12, 4,  8, 2, 10, 5,  1, 11], (*)
[9,  3, 6, 12, 4,  8, 2, 10, 5,  1, 13],
[11, 1, 5, 10, 2,  8, 4, 12, 6,  3,  9], (*)
[11, 1, 9,  3, 6, 12, 4,  8, 2, 10,  5], (*)
[13, 1, 5, 10, 2,  8, 4, 12, 6,  3,  9],
[13, 1, 9,  3, 6, 12, 4,  8, 2, 10,  5].

Cf. A337125, A339491.

a(14)-a(32) from Pontus von Brömssen, Dec 29 2020

A340114 Table T(n,k), n>=1, k>=1, row n being the lexicographically earliest of the longest sequences of distinct positive integers in which the k-th term does not exceed n*k and the smaller of adjacent terms divides the larger, giving a prime.

Original entry on oeis.org

1, 2, 1, 3, 6, 2, 4, 8, 1, 2, 4, 12, 6, 18, 9, 3, 15, 30, 10, 5, 35, 7, 21, 42, 14, 28, 56, 8, 16, 48, 24, 72, 36, 2, 1, 3, 9, 18, 6, 12, 24, 8, 40, 20, 10, 5, 55, 11, 33, 66, 22, 44, 4, 52, 26, 78, 39, 13, 91, 7, 49, 98, 14, 42, 126, 63, 21, 105, 15, 45, 135, 27, 81

Offset: 1

Peter Munn, Dec 28 2020

The longest sequence is finite for all n. We can deduce this, because we know from the work of Saias that A337125(m)/m * log m is bounded, where A337125(m) is the length of the longest simple path in the divisor graph of {1,...,m}. See the comment in A337125 giving constraints on its terms.

The sequence of row lengths starts 2, 6, 25, 97.

			For n = 1, the only sequences of distinct positive integers that have their k-th term not exceeding 1*k = k, are those whose n-th term is k. The longest such sequence in which the smaller of adjacent terms divides the larger, giving a prime, is (1, 2), since 3/2 is 1.5. So row 1 has length 2, with T(1,1) = 1, T(1,2) = 2.
Table begins:
1, 2;
1, 3, 6, 2, 4, 8;
1, 2, 4, 12, 6, 18, 9, 3, 15, 30, 10, 5, 35, 7, 21, 42, 14, 28, 56, 8, 16, 48, 24, 72, 36;
...

Peter Munn, Rows n = 1..4 of triangle, flattened
E. Saias, Applications des entiers à diviseurs denses, Acta Arithmetica, 83, 3 (1998), 225-240.

Cf. A000040, A300012, A337125, A339491.

For n >= 1, 1 <= k <= row length(n), T(n,k) <= n * k.

For n >= 1, 1 <= k < row length(n), max(T(n,k+1)/T(n,k), T(n,k)/T(n,k+1)) is in A000040.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A339489 T(n, k) = Product(divisors(k) union {k*j : j = 2..floor(n/k)}). Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

A339492 T(n, k) = tau(k) + floor(n/k) - 1, where tau = A000005. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A339496 T(n, k) = Sum(divisors(k) union {k*j : j = 2..floor(n/k)}). Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

A339490 Number of longest simple paths in the divisor graph of {1,...,n}.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A340114 Table T(n,k), n>=1, k>=1, row n being the lexicographically earliest of the longest sequences of distinct positive integers in which the k-th term does not exceed n*k and the smaller of adjacent terms divides the larger, giving a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula