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$ Feb 26, 2016 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$ Feb 26, 2016 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$ Feb 28, 2016 at 22:54
  • $\begingroup$ Here are the distinct P-graphs for small cases: (cloud.sagemath.com/projects/…) $\endgroup$ Feb 29, 2016 at 0:31
  • $\begingroup$ How do you know that you have tested far enough for each $n$? $\endgroup$ Feb 29, 2016 at 1:12

2 Answers 2


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$ 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.

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.

  • $\begingroup$ That is the trouble. It is not easy to count duplications. $\endgroup$ Feb 26, 2016 at 15:10
  • $\begingroup$ You can show that there are no duplication. Thus giving the formula. $\endgroup$
    – elie520
    Feb 26, 2016 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$ Feb 26, 2016 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, 2016 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$ Feb 26, 2016 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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