harrypotter192's blog

Genralisation of a number theory problem
By harrypotter192, 10 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

»
10 years ago, # |
← 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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice observation :)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply