0
$\begingroup$

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.

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

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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, 2016 at 3:59
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ That is the trouble. It is not easy to count duplications. $\endgroup$
    – Bernardo Recamán Santos
    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$
    – Gerhard Paseman
    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$
    – Gerry Myerson
    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.