In the problem topcoder Problem, we are asked to find minimum count of numbers to be inserted between two numbers such that in the final list, consecutive elements are coprime. For all the test cases ( both the numbers <= 100000) , the answer is <=2. Is it always true? In other words, Is it always true that For any two numbers x & y, x<y , we can find a & b such that x<a<b<y and gcd(x,a) = gcd(a,b)=gcd(b,y)=1 ?
Some simple observation: if there is a prime number p between x and y, then the answer is 1 or 2:
So, we have a solution at least when y ≥ 2x (see http://en.wikipedia.org/wiki/Bertrand%27s_postulate ).
Nice observation :)
If p divides y there is another prime p1 : p < p1 < 2p ≤ y
We can do this while pi divides y
So the answer will be exactly 1.
What if there is no prime between x & y.Any proof that in that case still numbers to be inserted will be maximum upto two.