Каждый номер имеет некоторые факторизации. Если 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
, выбирая соседний номер, чтобы любой из них поможет, потому что обычно она будет иметь только несколько факторов.
кажись, связанные с [близнецом премьер-гипотезой] (http://en.wikipedia.org/ вики/Twin_prime). Я чувствую, что вы можете удовлетворить определенные ограничения для этого диапазона, но вы не сможете обобщить результаты. –