A291465 - OEIS

A291465

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

1, 2, 4, 9, 14, 25, 36, 45, 52, 61, 62, 89, 90, 95, 98, 123, 140, 155, 162, 171, 172, 177, 216, 217, 226, 243, 244, 255, 264, 283, 318, 321, 340, 345, 374, 383, 384, 395, 400, 403, 422, 449, 456, 465, 478, 531, 546, 551, 552, 557, 562, 567, 594, 599, 604, 605

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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.

LINKS

Paul Tabatabai, Table of n, a(n) for n = 1..75

Adam H. Berliner, N. Dean, J. Hook, A. Marr, and A. Mbirika, Coprime and prime labelings of graphs, arXiv:1604.07698 [math.CO], 2016; Journal of Integer Sequences, Vol. 19 (2016), #16.5.8.

FORMULA

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

EXAMPLE

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

CROSSREFS

Cf. A104272, A213273, A213806, A284875.

Sequence in context: A078671 A119637 A169762 * A355606 A227377 A341959

Adjacent sequences: A291462 A291463 A291464 * A291466 A291467 A291468

KEYWORD