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.

  • $\begingroup$ A precise count may not be easy, but what about estimates? $\endgroup$ – Bernardo Recamán Santos Feb 26 '16 at 15:57
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Feb 26 '16 at 19:03
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Feb 28 '16 at 22:54
  • $\begingroup$ Here are the distinct P-graphs for small cases: (cloud.sagemath.com/projects/…) $\endgroup$ – Bernardo Recamán Santos Feb 29 '16 at 0:31
  • $\begingroup$ How do you know that you have tested far enough for each $n$? $\endgroup$ – Brendan McKay Feb 29 '16 at 1:12

The answer should be
$\prod_{p\leq n/2}p\times\prod_{n/2<q\leq n-1}(n+1-q)$ where $p$ and $q$ are restricted to be primes in the products.
This answer can be found using the chinese remainder theorem, you have to be careful though and verify that you are not constructing the same graph twice with the aformentioned theorem.

Edit, this formula 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.

  • $\begingroup$ That is the trouble. It is not easy to count duplications. $\endgroup$ – Bernardo Recamán Santos Feb 26 '16 at 15:10
  • $\begingroup$ You can show that there are no duplication. Thus giving the formula. $\endgroup$ – elie520 Feb 26 '16 at 18:23
  • $\begingroup$ For n=4, your formula gives 4. I only count 2 such graphs. Perhaps you can tell me where I went wrong? Gerhard "Or Where You Went Left?" Paseman, 2016.02.26. $\endgroup$ – Gerhard Paseman Feb 26 '16 at 18:50
  • $\begingroup$ If i'm not mistaking, the graphs issued from the first integer beeing respectively 3, 4, 5 and 6 give the four possible graphs. $\endgroup$ – elie520 Feb 26 '16 at 20:18
  • $\begingroup$ 4, 5, 6, 7 has just one edge, and 5, 6, 7, 8 has just one edge. Are you counting those isomorphic graphs as different? $\endgroup$ – Gerry Myerson Feb 26 '16 at 21:53

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.

  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Feb 27 '16 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.