# Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$

I recently got asked the following question:

A set of $$n$$ cities are numbered from 1 to $$n$$. Given a positive integer $$g$$, two cities are connected if their greatest common divisor is greater than $$g$$. The number $$n$$ may be as large as $$10^5$$.

Alice has a list of $$q$$ cities that she'd like to visit. Given Alice's list of $$q$$ origin cities and $$q$$ destination cities, return a boolean vector with a 1 in the $$i$$th position indicating that it's possible to reach the $$i$$th destination city from the $$i$$th origin city, and 0 if not. The length of the list $$q$$ may be as large as $$10^5$$ as well.

I solved this problem with a quadratic time solution. However, the large upper bound for $$n$$ and $$q$$ clearly implies there is a better runtime. I haven't yet seen a way to speed up the creation of the graph, however.

My solution builds the graph in quadratic time, using a union find data structure to handle the component merging, and Euclid's algorithm for computing gcd's.

The fundamental question is whether there exists a faster than $$O(n^2)$$ algorithm to construct and query an undirected graph, when edges are defined by a pairwise rule, and it appears that every pair $$(i, j)$$ for $$1 \leq i,j \leq n$$ needs to be looked at.

• Can you edit the question to credit the source of this problem? (See cs.stackexchange.com/help/referencing.)
– D.W.
Jan 2 '18 at 2:09
• I encourage you to replace the code with a description of ideas and concise pseudocode. Not everyone where reads Python, and we're not a coding site -- algorithms are on-topic, but code isn't really.
– D.W.
Jan 2 '18 at 2:10
• @D.W. The question came up during an interview, I'd prefer not to say where. Jan 2 '18 at 3:14
• @D.W. Python strikes me as almost psudocode already. Is there a specific thing in the code that is confusing? Jan 2 '18 at 3:17
• Our site policy is that we want questions to be understandable without having to know a particular programming language. One has to know a bit of Python to understand this code (e.g., zip, list comprehensions; I make no claim that's an exhaustive list). And there seems to be no point in including code for gcd or SetUnion, whatever that is -- that just takes up space without providing any illumination about the algorithmic ideas you have in mind.
– D.W.
Jan 2 '18 at 6:05

Given parameters $n$ and $g$, you want to find the connected components of the graph on $[n] := \{1,\ldots,n\}$ whose edges are $\{(i,j) \in [n] : (i,j) > g\}$. Let us write these edges in a different way: $$\bigcup_{d=g+1}^n \{(i,j) \in [n]: d \mid (i,j) \} = \bigcup_{d=g+1}^n \{(dI,dJ) : 1 \leq I,J \leq n/d \}.$$ For each $d$, we have a clique on $\lfloor n/d \rfloor$ vertices. We can preserve the same connectivity properties by replacing it with a path: $$\bigcup_{d=g+1}^n \{(dI,d(I+1)) : 1 \leq I < \lfloor n/d \rfloor \}.$$ The number of edges in the new graph is $$\sum_{d=g+1}^n \lfloor n/d \rfloor \leq n \sum_{d=g+1}^n \frac{1}{d} = O(n\log n).$$ You can find the connected components using BFS/DFS in time $O(n\log n)$, a large improvement over your quadratic time algorithm.

• Hi Yuval, thank you for the answer! I'm still trying to understand it -- is there a reference you can point me at for this technique? Does it have a name? Jan 2 '18 at 21:31
• I'm still working through understanding this, but this seems really cool. : D Jan 2 '18 at 21:35
• I can't think of any references, or of any name for this optimization. Jan 2 '18 at 21:36
• This is really cool. @Yuval Filmus, can you offer any insights into how you go to this solution? Jan 2 '18 at 21:46
• When you get more experienced, you will be able to come up with such tricks yourself. Jan 2 '18 at 21:48

Pseudo code for finding the minimum connected edges.

    n=100
lst = range(1,101)
g=10
ans = list(tuple())
for d in range(g+1,n+1):
for i in range(1,n/d):
ans.append((d*i,d*(i+1)))
print ans
print "size="+str(len(ans))


Output:

   [(11, 22), (22, 33), (33, 44), (44, 55), (55, 66), (66, 77), (77, 88), (88, 99), (12, 24), (24, 36), (36, 48), (48, 60), (60, 72), (72, 84), (84, 96), (13, 26), (26, 39), (39, 52), (52, 65), (65, 78), (78, 91), (14, 28), (28, 42), (42, 56), (56, 70), (70, 84), (84, 98), (15, 30), (30, 45), (45, 60), (60, 75), (75, 90), (16, 32), (32, 48), (48, 64), (64, 80), (80, 96), (17, 34), (34, 51), (51, 68), (68, 85), (18, 36), (36, 54), (54, 72), (72, 90), (19, 38), (38, 57), (57, 76), (76, 95), (20, 40), (40, 60), (60, 80), (80, 100), (21, 42), (42, 63), (63, 84), (22, 44), (44, 66), (66, 88), (23, 46), (46, 69), (69, 92), (24, 48), (48, 72), (72, 96), (25, 50), (50, 75), (75, 100), (26, 52), (52, 78), (27, 54), (54, 81), (28, 56), (56, 84), (29, 58), (58, 87), (30, 60), (60, 90), (31, 62), (62, 93), (32, 64), (64, 96), (33, 66), (66, 99), (34, 68), (35, 70), (36, 72), (37, 74), (38, 76), (39, 78), (40, 80), (41, 82), (42, 84), (43, 86), (44, 88), (45, 90), (46, 92), (47, 94), (48, 96), (49, 98), (50, 100)]
size=101


We can see that edges like (11,33), (11, 44) etc are not part of the set even though they are directly connected.

After we get the minimum number of connected edges we can apply disjoints sets to solve the above question.

• What does ans = list(tuple()) do? When writing pseudocode, try to keep things obvious to the reader and avoid things like that, and like assuming that things must be converted to string type before print can handle them. Feb 20 '19 at 17:23

Hint: to determine whether there is a path from source $s$ to destination $t$, factor both $s$ and $t$. What properties need to hold true about their factorization, for such a path to exist?