# Graphs determined by sets of consecutive integers

Given a set of positive integers, its P-graph is the graph whose vertex set consists of those integers, two of which are joined by an edge if they have a common divisor greater than 1, that is, they are not relatively prime. How many distinct graphs can be the P-graph of a set of n consecutive integers?

The values for n =1, 2, 3,...17, as calculated jointly with Freddy Barrera using Sage Math, are 1, 1, 2, 2, 4, 4, 9, 16, 35, 32, 49, 73, 227, 546, 1109, 1562, 2398.

• A precise count may not be easy, but what about estimates? Feb 26, 2016 at 15:57
• A lower bound could be considered by looking at set systems induced by the divisibility relation among the primes at most n^r in size, where you vary the parameter r between 0 and 1. Part of elie520's formula may apply in this case. Gerhard "This Saves On Edge Drawing" Paseman, 2016.02.26. Feb 26, 2016 at 19:03
• for n=7, I get 8 because in one case a multiple of 15 "looks like" a multiple of 3 and not 5 in another case. I would like to see your specific results for n=7 to make sure I am not counting wrong. Gerhard "And Thanks For The Update" Paseman, 2016.02.28. Feb 28, 2016 at 22:54
• Here are the distinct P-graphs for small cases: (cloud.sagemath.com/projects/…) Feb 29, 2016 at 0:31
• How do you know that you have tested far enough for each $n$? Feb 29, 2016 at 1:12

I get the following pairs (n,g) by hand (corrections welcome): (1,1), (2,1), (3,2), (4,2), (5,4), (6,4), (7,8). If I label the graph edges with the smallest common prime factor, I get divergence starting at (7,9). It's unlikely that the answer to Bernardo's question is always a power of two.

Gerhard "Wouldn't That Be Really Amazing?" Paseman, 2016.02.26.

• It looks like I get (8,12) when I don't label the edges, and a lot more when I do. Unfortunately I see only rough bounds like $P_{\pi(n)}/2$, which is way high. Gerhard "Lower Bounds Aren't Any Better" Paseman, 2016.02.26. Feb 27, 2016 at 3:59

Edit, answer below is wrong because I didn't identify graphs issued from (1,2,3,4) and (2,3,4,5) to be the same for example (see comments). Only gives an upper bound.

$$\prod_{p\leq n/2}p\times\prod_{n/2 where $$p$$ and $$q$$ are restricted to be primes in the products.