harrypotter192's blog

Genralisation of a number theory problem
By harrypotter192, 11 years ago, In English

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 ?

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +21 Vote: I do not like it

Some simple observation: if there is a prime number p between x and y, then the answer is 1 or 2:

  • if p does not divide y, then (x, p, y) is ok.
  • if p divides y, then (x, p, y - 1, y) is ok.

So, we have a solution at least when y ≥ 2x (see http://en.wikipedia.org/wiki/Bertrand%27s_postulate ).

→ Reply