ClearAll[NextInSequence, EKGSequence]
NextInSequence[seq_List] := Module[{last, new = 1, holes, max, sel, found, i},
  last = Last[seq];
  max = Max[seq];
  holes = Complement[Range[max], seq];
  sel = SelectFirst[holes, Not[CoprimeQ[last, #]] &];
  If[MissingQ[sel],
   i = max;
   found = False;
   While[! found,
    i++;
    If[Not[CoprimeQ[last, i]],
     found = True
     ]
    ];
   Append[seq, i]
   ,
   Append[seq, sel]
  ]
 ]
EKGSequence[start_Integer, n_] := Nest[NextInSequence, {1, start}, n - 2]

Table[EKGSequence[s, 10], {s, {2, 5, 7, 9, 10}}] // Grid

s = Reverse[Transpose[{EKGSequence[5, 1000], EKGSequence[7, 1000]}]];
len = LengthWhile[s, Apply[Equal]];
s //= Reverse[Drop[#, len]] &;
Length[s] + 1