login
a(n) is the least m >= n for which the complete bipartite graph K_{m,n} has a prime labeling.
5

%I #28 Mar 03 2024 08:35:19

%S 1,2,4,9,14,25,36,45,52,61,62,89,90,95,98,123,140,155,162,171,172,177,

%T 216,217,226,243,244,255,264,283,318,321,340,345,374,383,384,395,400,

%U 403,422,449,456,465,478,531,546,551,552,557,562,567,594,599,604,605

%N a(n) is the least m >= n for which the complete bipartite graph K_{m,n} has a prime labeling.

%C A prime labeling of K_{m,n} is a pair of sets A and B whose union is {1,2,...,m+n} such that |A| = m, |B| = n, and gcd(a,b) = 1 for all a in A and b in B. For an equivalent definition, the data above, and the formula below involving R_{n-1}, see Berliner, Dean, Hook, Marr, Mbirika (2016) Section 3.2.

%H Paul Tabatabai, <a href="/A291465/b291465.txt">Table of n, a(n) for n = 1..75</a>

%H Adam H. Berliner, N. Dean, J. Hook, A. Marr, and A. Mbirika, <a href="http://arxiv.org/abs/1604.07698">Coprime and prime labelings of graphs</a>, arXiv:1604.07698 [math.CO], 2016; <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Mbirika/mbi3.pdf">Journal of Integer Sequences, Vol. 19 (2016), #16.5.8</a>.

%F n+1 <= a(n) <= R_{n-1} - n for n > 2, where R_{n-1} is a Ramanujan prime A104272.

%e A = {1,3} and B = {2,4} is a prime labeling of K_{2,2}, so a(2) = 2.

%Y Cf. A104272, A213273, A213806, A284875.

%K nonn,more

%O 1,2

%A _Jonathan Sondow_, Aug 24 2017

%E a(14) onward from _Paul Tabatabai_, Apr 29 2019