A337125 -id:A337125 - cp's OEIS frontend

A347698 a(n) = n - A337125(n).

0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 4, 4, 4, 5, 4, 5, 5, 5, 6, 6, 6, 7, 8, 8, 8, 9, 8, 9, 8, 8, 9, 10, 9, 10, 9, 9, 9, 10, 10, 10, 10, 10, 11, 12, 11, 12, 13, 13, 13, 14, 13, 14, 14, 14, 13, 14, 14, 15, 16, 16, 16, 16, 15, 16, 16, 16, 17, 18

Offset: 1

N. J. A. Sloane, Oct 12 2021

nonn

The graph of A337125 is typical of many that look like a straight line with small irregularities. So much of the information is in the sequence of irregularities, which are shown here. This also shows that the original sequence was not as close to the line y=x as it appeared. (Of course this is explained by the asymptotic bounds given in A337125.)

N. J. A. Sloane, Table of n, a(n) for n = 1..200

Cf. A337125.

A339491 Lexicographically earliest longest simple path in the divisor graph of {1,...,n}. Irregular triangle read by rows.

Original entry on oeis.org

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

Offset: 1

Peter Luschny, Dec 29 2020

A simple path in the divisor graph of {1,...,n} is a sequence of distinct numbers between 1 and n such that if k immediately follows m, then either k divides m or m divides k. For more information, references and links see A337125.

			1:                     [1],
2:                    [1, 2],
3:                  [2, 1, 3],
4:                 [2, 4, 1, 3],
5:                 [2, 4, 1, 3],
6:              [3, 6, 2, 4, 1, 5],
7:              [3, 6, 2, 4, 1, 5],
8:             [3, 6, 2, 4, 8, 1, 5],
9:            [4, 8, 2, 6, 3, 9, 1, 5],
10:         [4, 8, 1, 5, 10, 2, 6, 3, 9],
11:         [4, 8, 1, 5, 10, 2, 6, 3, 9],
12:      [5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7],
13:      [5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7],
14:     [5, 10, 1, 7, 14, 2, 8, 4, 12, 6, 3, 9],
15:   [6, 12, 4, 8, 1, 7, 14, 2, 10, 5, 15, 3, 9],
16:  [6, 12, 4, 8, 16, 1, 7, 14, 2, 10, 5, 15, 3, 9].

Cf. A337125 (row length), A339490.
Cf. A339492, A339489, A339496.
Cf. A340114 (a variant problem).

with(Iterator):
DivisorPath := proc(n, k) local c, p, w, isok;
    isok := proc(A) local e, i, di; e := nops(A) - 1;
       di := (n, k) -> evalb(irem(n, k) = 0 or irem(k, n) = 0):
       for i from 1 to e while di(A[i], A[i+1]) do od;
       return evalb(i = e + 1) end:
    for c in Combination(n, k) do
       for p in Permute([seq(j + 1, j in c)], k) do
           w := convert(p, list);
           if isok(w) then return w fi:
od  od  end:
A337125 := [1, 2, 3, 4, 4, 6, 6, 7, 8, 9, 9]:
for n from 1 to 9 do DivisorPath(n, A337125[n]) od;

Signposting added to first comment by Peter Munn, Mar 12 2021

A034298 a(n) = min_S max_i b_i where S={b_i} (1 <= i <= n), b_i > 0, b_i distinct and either b_i|b_{i-1} or b_{i-1}|b_i.

Original entry on oeis.org

1, 2, 3, 4, 6, 6, 8, 9, 10, 12, 12, 14, 15, 16, 18, 18, 20, 21, 22, 24, 24, 26, 27, 28, 30, 30, 32, 33, 35, 36, 39, 40, 42, 42, 44, 44, 45, 48, 48, 50, 50, 51, 52, 54, 55, 56, 57, 60, 60, 63, 64, 66, 66, 68, 69, 70, 70, 72, 75, 76, 77, 78, 78, 80, 81, 84, 87, 88

Offset: 1

Erich Friedman

			For example, a(12)=14 because of {9, 3, 6, 12, 4, 8, 2, 10, 5, 1, 7, 14} and the fact that no sequence of 12 distinct positive integers < 14 has this division property.
a(32) = 40 because of {22, 11, 33, 3, 39, 13, 26, 2, 34, 17, 1, 10, 20, 40, 8, 16, 32, 4, 28, 14, 7, 35, 5, 15, 30, 6, 24, 12, 36, 18, 9, 27};
a(34) = 42 because of {22, 11, 33, 3, 39, 13, 26, 2, 34, 17, 1, 10, 20, 40, 8, 16, 32, 4, 28, 14, 42, 21, 7, 35, 5, 15, 30, 6, 24, 12, 36, 18, 9, 27};
a(37) = 45 because of {17, 34, 2, 38, 19, 1, 26, 13, 39, 3, 33, 11, 22, 44, 4, 16, 32, 8, 24, 6, 12, 36, 18, 9, 45, 15, 30, 10, 20, 40, 5, 35, 7, 21, 42, 14, 28}.

E. J. Friedman, Problem of the Month (November 1998), Math. Magic.

Cf. A035280, A337125.

a(31)-a(37) from Xavier Martres, Apr 26 2019

More terms from Jinyuan Wang, Aug 02 2022

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

A347698 a(n) = n - A337125(n).

Views

Author

Keywords

Comments

Links

Crossrefs

A339491 Lexicographically earliest longest simple path in the divisor graph of {1,...,n}. Irregular triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Extensions

A034298 a(n) = min_S max_i b_i where S={b_i} (1 <= i <= n), b_i > 0, b_i distinct and either b_i|b_{i-1} or b_{i-1}|b_i.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

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