# Longest Increasing Co-Prime Subsequence?

This is a made up question not seen somewhere so I am not sure if a good solution exists but here it is anyways.

Given an array $$A$$ of $$N$$ non-negative integers, find the longest non-decreasing subsequence of this array such that every adjacent pair in the subsequence is co-prime, ie. $$gcd(a_{i}, a_{i + 1}) = 1 \space \forall \space 0 <= i < K - 1$$ where $$K$$ is length of subsequence.

Would it be possible to have a solution better than $$O(N^2)$$ if each number is in range $$0$$ to $$10^5$$?

I was exploring solutions using segment trees but it's very tricky, compared to a different version where adjacent pairs should be strictly non-coprime which would be trivial.

If there is some way to make it more efficient I would like to know.

• What goes wrong if you try adapting a standard algorithm for longest increasing subsequence?
– D.W.
Commented Jun 16, 2023 at 19:09
• @InuyashaYagami yes, non-negative integers, so $0$ to $10^5$ Commented Jun 16, 2023 at 19:53
• @D.W. Usual DP solution is $O(N^2)$ which works easily here, but the optimal $O(n \log n)$ solution is difficult to adapt, one uses Binary Search which can't enforce co-prime condition, other uses Segment tree to find longest sequence ending at a smaller value, that too is difficult to adapt as we need to do range maximum query where index is co-prime to some number, I am not sure if that's doable. Commented Jun 16, 2023 at 19:57

I think there is a slightly better algorithm, depending on the relative sizes on the upper bound $$B=10^5$$ and $$N$$.

The proposed algorithm proceeds like the usual DP algorithm, scanning the array from left to right, and at each array position $$i$$ you it computes what is the array position $$j < i$$ that maximizes the value of $$\text{dp}[j]$$ subject to $$A_j < A_i$$ and $$\gcd(A_j, A_i) = 1$$.

To compute $$\text{dp}[i]$$ you don't actually need to compute $$j$$, it suffices to compute $$\text{dp}[j]$$. So we will find it using binary search. The binary search condition is, is there a $$j < i$$ such that $$i$$ can connect to $$j$$ and $$dp[j] \geq k$$?

We will actually count the number of such $$j$$ (and then check if its $$0$$ or $$1$$) doing inclusion exclusion. The formula for that number is $$\#\big\{j Where $$M_d^i(k)$$ is the number of indices $$j such that $$d | A_j$$, $$A_j < A_i$$ and $$\text{dp}[j] \geq k$$, and $$\mu$$ is the Mobius function.

If for each index $$j$$ such that $$d | A_j$$ we consider the 2d point $$(A_j, \text{dp}[j])$$ then $$M_d^i(k)$$ is a query of the form "How many points are there in this (shifted) quadrant of the plane?", which can be solved in $$O(\log N \log B)$$ using lazy creation 2d segment trees. We need to store a segment tree like this for each possible $$d$$ (which are the divisors of elements of the array). And each time we compute a new value of the DP, we need to insert a point in all the required datastructures (which correspond to all divisors of the value $$A_i$$).

If $$D$$ is a bound on the number of divisors for numbers less than $$B$$, then the complexity of this solution would be

$$O(N D \log^2 N \log B)$$

Note that $$D$$ grows slower than any polynomial with respect to $$B$$. In particular, for $$B = 10^5$$, $$D < 240$$.