cp's OEIS Frontend

A320536 a(n) is the least cardinal of a partition of {1..n} into simple paths of its divisorial graph.

%I A320536 #24 May 04 2021 18:10:30
%S A320536 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 A320536 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 A320536 12,12,13,12,13,13,13,13,14,14,15,15,14,14,15,14,15,15,15,15,16,16
%N A320536 a(n) is the least cardinal of a partition of {1..n} into simple paths of its divisorial graph.
%C A320536 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 A320536 Paul Revenant, <a href="/A320536/b320536.txt">Table of n, a(n) for n = 1..3210</a>
%H A320536 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 A320536 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 A320536 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 A320536 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 A320536 Eric Saias, <a href="https://doi.org/10.1007/BF02872766">Etude Du Graphe Divisoriel 3</a>, Rend. Circ. Mat. Palermo (2003) 52: 481.
%F A320536 a(n) = floor((n+1)/2) - floor(n/3) for n <=35.
%e A320536 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 A320536 nonn
%O A320536 1,5
%A A320536 _Michel Marcus_, Oct 15 2018
%E A320536 More terms from _Paul Revenant_, Jul 08 2019