Минимальное количество чисел, которые нужно вставить в [a, b], чтобы GCD из двух последовательных чисел 1

Question

Этот вопрос задали в TopCoder - SRM 577. Принимая во внимание 1 <= a < b <= 1000000, каков минимальный подсчет чисел, которые будут вставлены между a & b таким образом, что никакие два последовательных числа не будет делить положительный делитель больше 1.

Пример:

1. a = 2184; b = 2200. Нам нужно вставить 2 номера 2195 & 2199 так, чтобы выполнялось условие. (2184, 2195,2199, 2200)
2. a = 7; b= 42. Одного номера достаточно, чтобы вставить между ними. Номер может быть .
3. a = 17; b = 42. GCD уже 1, поэтому нет необходимости вставлять какое-либо число.

Теперь самое интересное в том, что для данного диапазона [1,1000000] мы никогда не требуют более 2-х элементов, которые будут вставлены между a и b. Более того, 2 числа предположительно являются a+1 и b-1, хотя это еще предстоит доказать.

1. Может ли кто-нибудь доказать это?
2. Может ли он быть расширен до большего диапазона чисел? Скажем, [1,10^18] и т.д.

Answer 1

Каждый номер имеет некоторые факторизации. Если a, b имеют небольшое количество различных простых факторов (DPF), а расстояние между ними велико, он уверен, что будет по крайней мере одно число между ними, у которого множество DPF & thinsp; s не имеет общих элементов с этими двумя. Таким образом, это будет наш номер номер n, такой как gcd(a,n) == 1 и gcd(n,b) == 1. Чем выше мы продвигаемся, тем больше факторов есть, потенциально, и вероятность того, что даже gcd(a,b)==1 будет выше и выше, а также для решение с одним номером между.

Когда будет возможно одноединое решение? Когда и bвысококомпонентные - имеют много DPF & thinsp; каждый - и расположены не слишком далеко друг от друга, поэтому каждое промежуточное число имеет некоторые основные факторы, общие с одним или двумя из них. Но gcd(n,n+1)==1 для любых n, всегда; поэтому выбор одного из a+1 или b-1 - в частности, с наименьшим количеством DPF & thinsp; s - уменьшит размер комбинированного набора DPF, и поэтому выбор одного номера между ними будет возможен. (... это далеко не строго).

---

Это не полный ответ, скорее как иллюстрация. Давайте попробуем это.

-- find a number between the two, that fulfills the condition 
gg a b = let fs=union (fc a) (fc b) 
     in filter (\n-> null $ intersect fs $ fc n) [a..b] 

fc = factorize 

Попробуйте:

Main> gg 5 43 
[6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,28,29,31,32,33,34,36,37,38,39 
,41,42] 

Main> gg 2184 2300 
[2189,2201,2203,2207,2209,2213,2221,2227,2237,2239,2243,2251,2257,2263,2267,2269 
,2273,2279,2281,2287,2291,2293,2297,2299] 

много возможностей для всего один номер, чтобы выбрать между 5 и 43, или между 2184 и 2300. Но что о данной паре, 2184 и 2200?

Main> gg 2184 2200 
[] 

Между ними нет ни одного номера. Но, очевидно, gcd (n,n+1) === 1:

Main> gg 2185 2200 
[2187,2191,2193,2197,2199] 
Main> gg 2184 2199 
[2185,2189,2195] 

Так подобрав один смежный номер, у нас действительно много возможностей для 2-го числа. Ваш вопрос заключается в том, чтобы доказать, что это всегда так.

Давайте посмотрим на их факторизации:

Main> mapM_ (print.(id&&&factorize)) [2184..2200] 
(2184,[2,2,2,3,7,13]) 
(2185,[5,19,23]) 
(2186,[2,1093]) 
(2187,[3,3,3,3,3,3,3]) 
(2188,[2,2,547]) 
(2189,[11,199]) 
(2190,[2,3,5,73]) 
(2191,[7,313]) 
(2192,[2,2,2,2,137]) 
(2193,[3,17,43]) 
(2194,[2,1097]) 
(2195,[5,439]) 
(2196,[2,2,3,3,61]) 
(2197,[13,13,13]) 
(2198,[2,7,157]) 
(2199,[3,733]) 
(2200,[2,2,2,5,5,11]) 

Очевидно, что чем выше диапазон, тем легче удовлетворять условию, так как разнообразие вклад простых делителей больше.

(a+1) не всегда будет работать сама по себе - рассмотреть 2185, 2200 случай (аналогично для 2184,2199(b-1) не будет работать).

Так что, если нам случится получить два высоко составных чисел, как наши a и b, выбирая соседний номер, чтобы любой из них поможет, потому что обычно она будет иметь только несколько факторов.

Answer 2

Этот ответ рассматривает ту часть вопроса, которая требует доказательства того, что подмножество {a, a + 1, b-1, b} всегда будет работать. Вопрос гласит: «Более того, 2 числа предположительно являются + 1 и b-1, хотя это еще предстоит доказать. Может ли кто-нибудь доказать это? ». Этот ответ показывает, что такое доказательство не может существовать.

Пример, который опровергает то, что подмножество {a, a + 1, b-1, b} всегда работает {105, 106, 370, 371} = {3 · 5 · 7, 2 · 53, 2 · 5 · 37, 7 · 53}. Пусть (x, y) обозначает gcd (x, y). Для этого примера (a, b) = 7, (a, b-1) = 5, (a + 1, b-1) = 2, (a + 1, b) = 53, поэтому все множества { а, б}; {a, a + 1, b}; {А, б-1, б}; и {a, a + 1, b-1, b} терпят неудачу.

Этот пример является результатом следующих рассуждений: Мы хотим найти a, b, чтобы каждое подмножество {a, a + 1, b-1, b} терпит неудачу. В частности, нам нужно, чтобы следующие четыре gcd были больше 1: (a, b), (a, b-1), (a + 1, b-1), (a + 1, b). Мы можем это сделать, найдя некоторые е, f, которые делят четное число а + 1, а затем построят Ь так, что нечетный Ь делится на/и некоторым коэффициентом а, а даже Ь-1 делится на е. В этом случае e = 2 и f = 53 (вследствие произвольного принятия a = 3 · 5 · 7, так что a имеет несколько малых нечетных простых факторов).

Answer 3

a=3199611856032532876288673657174860 
b=3199611856032532876288673657174960 

похоже, контрпример.

Answer 4

Doh, извините.Контрпример у меня есть

a=3199611856032532876288673657174760 
b=3199611856032532876288673657174860 

(Было бы хорошо, если бы этот глупый сайт позволил каждому редактировать свои сообщения)