|
%I #24 May 04 2021 18:10:30
%S 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,
%T 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,
%U 12,12,13,12,13,13,13,13,14,14,15,15,14,14,15,14,15,15,15,15,16,16
%N a(n) is the least cardinal of a partition of {1..n} into simple paths of its divisorial graph.
%C 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]
%H Paul Revenant, <a href="/A320536/b320536.txt">Table of n, a(n) for n = 1..3210</a>
%H P. Erdos, and E. Saias, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa73/aa7324.pdf">Sur le graphe divisoriel</a>, Acta Arithmetica 73, 2 (1995), 189-198.
%H Paul Melotti and Eric Saias, <a href="https://arxiv.org/abs/1807.07783">On path partitions of the divisor graph</a>, arXiv:1807.07783 [math.NT], 2018.
%H Carl Pomerance, <a href="https://math.dartmouth.edu/~carlp/divisorgraph.pdf">On the longest simple path in the divisor graph</a>, Proc. Southeastern Conf. Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, 1983, Cong. Num. 40 (1983), 291-304.
%H Eric Saias, <a href="https://www.lpsm.paris//mathdoc/textes/PMA-849.pdf">Etude Du Graphe Divisoriel 3</a>, Preprint 849, Laboratoire de Probabilités et Modèles Aléatoires, October 2003.
%H Eric Saias, <a href="https://doi.org/10.1007/BF02872766">Etude Du Graphe Divisoriel 3</a>, Rend. Circ. Mat. Palermo (2003) 52: 481.
%F a(n) = floor((n+1)/2) - floor(n/3) for n <=35.
%e 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).
%K nonn
%O 1,5
%A _Michel Marcus_, Oct 15 2018
%E More terms from _Paul Revenant_, Jul 08 2019
|
