4

この質問はTopCoder-SRM 577で出されました。が与えられたとき、 2 つの連続する数が 1 より大きい正の約数を共有しないように&1 <= a < b <= 1000000の間に挿入される数の最小数はいくつですか。ab

例：

  1. a = 2184; b = 2200. 条件が成り立つように、2 つの数値2195&を挿入する必要があります。2199( 2184、2195、2199、2200 )
  2. a = 7; b= 42. それらの間に挿入するには、1 つの数字で十分です。数は11です。
  3. a = 17; b = 42. GCD はすでに 1 であるため、数値を挿入する必要はありません。

ここで興味深いのは、指定された範囲[1,1000000]aに対して、 と の間に2 つ以上の要素を挿入する必要がないことですb。さらに、2 つの数字は推測されてa+1いb-1ますが、まだ証明されていません。

  1. 誰でもこれを証明できますか？
  2. より大きな範囲の数値にも拡張できますか? と言う[1,10^18]など
4

4 に答える 4

1

各数値には因数分解があります。a、bそれぞれに少数の異なる素因数( DPF ) があり、それらの間の距離が大きい場合、それらの間に少なくとも 1 つの数が存在し、そのDPF のセットが 2 つと共通の要素を持たないことは確実です。したがって、これは と のような 1 つの数字の選択nにgcd(a,n) == 1なりgcd(n,b) == 1ます。上に行けば行くほど、より多くの素因数が存在する可能性があり、偶数の確率はますます高くなり、中間の数の解の確率もgcd(a,b)==1高くなります。

1 桁の解決策が不可能になるのはいつですか? aとbが非常に複合的である場合(それぞれに多数のDPF があり)、互いにあまり離れていないため、各中間数にはそれらの 1 つまたは 2 つと共通するいくつかの素因数があります。しかしgcd(n,n+1)==1、いつnでも; したがって、a+1またはの 1 つを選択すると、具体的にはDPFb-1の量が最も少ないものを選択すると、結合されたDPFセット のサイズが減少するため、それらの間で 1 つの数値を選択することが可能になります。（... ただし、これは厳密ではありません）。

これは完全な答えではなく、例のようなものです。これを試してみましょう。

-- 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 の間で1 つの数字を選ぶ可能性はたくさんあります。

Main> gg 2184 2200
[]

それらの間に入れる数字は1つもありません。しかし明らかに、gcd (n,n+1) === 1:

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

したがって、隣接する数字を 1 つ選択したので、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)ません)。

したがって、と として2 つの高度に合成された数が得られた場合、どちらか一方に隣接する数を選択するaとb役立ちます。

于 2013-05-03T07:10:11.297 に答える
0

この回答は、{a,a+1,b-1,b} のサブセットが常に機能するという証明を求める質問の部分に対応しています。質問には次のように書かれています。誰かこれを証明できますか？」この答えは、そのような証拠が存在しないことを示しています。

{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、b}; {a、a+1、b}; {a、b-1、b}; {a, a+1, b-1,b} は失敗します。

この例は、次の推論の結果です。{a,a+1,b-1,b} のすべてのサブセットが失敗するような a,b を見つけたい。具体的には、次の 4 つの gcd が 1 より大きい必要があります: (a,b)、(a,b-1)、(a+1,b-1)、(a+1,b)。これを行うには、偶数 a+1 を割る e,f を見つけ、奇数 b が f と a の因数で割り切れ、偶数 b-1 が e で割り切れるように b を構成します。この場合、e=2 および f=53 です (a=3.5.7 を任意に取り、a がいくつかの小さな奇素因数を持つようにした結果)。

于 2013-05-03T07:27:03.833 に答える