VOOZH about

URL: https://oeis.org/A320536

⇱ A320536 - OEIS

login
A320536
a(n) is the least cardinal of a partition of {1..n} into simple paths of its divisorial graph.
2
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, 5, 6, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 8, 9, 9, 9, 9, 10, 9, 10, 9, 9, 9, 10, 10, 11, 11, 11, 11, 12, 11, 12, 12, 12, 12, 13, 12, 13, 13, 13, 13, 14, 14, 15, 15, 14, 14, 15, 14, 15, 15, 15, 15, 16, 16
OFFSET
1,5
COMMENTS
Saias proves that n/6 <= a(n) for all positive integers, and a(n) < n/4 for n large enough. [clarified by Paul Revenant, Jul 08 2019]
LINKS
P. Erdos, and E. Saias, Sur le graphe divisoriel, Acta Arithmetica 73, 2 (1995), 189-198.
Paul Melotti and Eric Saias, On path partitions of the divisor graph, arXiv:1807.07783 [math.NT], 2018.
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.
Eric Saias, Etude Du Graphe Divisoriel 3, Preprint 849, Laboratoire de Probabilités et Modèles Aléatoires, October 2003.
Eric Saias, Etude Du Graphe Divisoriel 3, Rend. Circ. Mat. Palermo (2003) 52: 481.
FORMULA
a(n) = floor((n+1)/2) - floor(n/3) for n <=35.
EXAMPLE
a(30) = 5 with (13, 26, 1, 11, 22, 2, 14, 28, 7, 21, 3, 27, 9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 30, 15, 5, 25), (17), (19), (23) and (29).
CROSSREFS
Sequence in context: A103221 A026806 A261348 * A347698 A338336 A298783
KEYWORD
nonn
AUTHOR
Michel Marcus, Oct 15 2018
EXTENSIONS
More terms from Paul Revenant, Jul 08 2019
STATUS
approved