Блог пользователя harrypotter192

Genralisation of a number theory problem
Автор harrypotter192, 10 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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 ).

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nice observation :)

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить