2
$\begingroup$

Given a set of positive integers, its common divisor graph ( CD-graph) is the graph whose vertices are the integers, two of which are joined by an edge if (and only if) they have a common divisor greater than 1.

Given the same set of integers, its nth Collatz iterate is the set resulting of applying the Collatz recipe (multiply by 3, and add 1 if odd; divide by 2 if even) to each of its elements.

Does a set of four integers exist such that the CD-graph of itself and that of its first ten iterates are precisely the 11 graphs on 4 vertices?

Notice that the set {7,10,13} does the trick for graphs on 3 vertices: all four graphs are generated.

Improve this question
$\endgroup$
6
  • $\begingroup$ Do all 11 graphs occur as CD-graphs (regardless of whether or not in this particular way)? When the Collatz map is not injective, do you regard it as collapsing the number of vertices in the CD-graph, or do you allow multiple vertices with the same label (then presumably connected)? $\endgroup$
    – LSpice
    Commented Feb 20, 2020 at 14:30
  • $\begingroup$ @LSpice: All graphs are the CD graph of some set. No collapsing. $\endgroup$
    – Bernardo Recamán Santos
    Commented Feb 20, 2020 at 15:09
  • 1
    $\begingroup$ So {5, 32} goes to a 2-vertex graph, not a 1-vertex graph? $\endgroup$
    – LSpice
    Commented Feb 20, 2020 at 15:21
  • 1
    $\begingroup$ Have you done any computer searching? It seems like it would be straightforward to test all ~4 million quartets of distinct numbers less than a hundred, for instance... $\endgroup$
    – Steven Stadnicki
    Commented Feb 20, 2020 at 18:06
  • 1
    $\begingroup$ @Steven Stadnicki: My collegue Freddy Barrera has done some computer search which so far has yielded at most 9 distinct graphs. $\endgroup$
    – Bernardo Recamán Santos
    Commented Feb 20, 2020 at 18:27

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .