4

TopCoder-SRM 577中提出了这个问题。给定，要在&1 <= a < b <= 1000000之间插入的最小数字是多少，这样没有两个连续的数字将共享一个大于 1 的正除数。ab

例子：

  1. a = 2184; b = 2200. 我们需要插入 2 个数字2195&2199使得条件成立。(2184, 2195,2199,2200 )
  2. a = 7; b= 42. 在它们之间插入一个数字就足够了。数量可以是11。
  3. a = 17; b = 42. GCD 已经是 1，所以不需要插入任何数字。

现在，有趣的是，对于给定的范围[1,1000000]a ，我们从不需要在和之间插入超过 2 个元素b。更重要的是，这两个数字被推测为a+1，b-1尽管尚未得到证实。

  1. 谁能证明这一点？
  2. 它也可以扩展到更大的数字范围吗？说[1,10^18]等
4

4 回答 4

2

呵呵，对不起。我的反例是

a=3199611856032532876288673657174760
b=3199611856032532876288673657174860

（如果这个愚蠢的网站允许每个人都编辑它的帖子就好了）

于 2013-06-12T08:22:13.313 回答
1

每个数字都有一些因式分解。如果a,b每个都有少量不同的质因数( DPF )，并且它们之间的距离很大，则可以肯定它们之间至少会有一个数，其DPF 的集合与两者没有共同的元素。所以这将是我们的一号选择n，例如gcd(a,n) == 1和gcd(n,b) == 1。我们走得越高，可能存在的素数越多，偶数的概率gcd(a,b)==1越来越高，中间一数解的概率也越来越高。

一号解决方案何时不可能？当a和b是高度复合的- 每个都有很多DPF  s - 并且彼此之间的距离不太远，因此每个中间数都有一些与其中一个或两个相同的素数。但gcd(n,n+1)==1对于任何n，总是；因此选择其中一个a+1或- 特别是DPFb-1数量最少的 那个 - 将减小组合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]

因此，在选择了一个相邻的数字后，我们确实有很多可能选择第二个数字。你的问题是，证明它总是如此。

让我们看看他们的因式分解：

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，选择一个与其中一个相邻的数字会有所帮助，因为通常它只有很少的因数。

于 2013-05-03T07:10:11.297 回答
0 
a=3199611856032532876288673657174860
b=3199611856032532876288673657174960

似乎是一个反例。

于 2013-06-12T08:13:56.907 回答
0

该答案解决了问题的一部分，该部分要求证明 {a,a+1,b-1,b} 的子集将始终有效。问题是：“更重要的是，这两个数字被推测为 a+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}; {a,b-1,b}; {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)。我们可以通过找到一些 e,f 来整除偶数 a+1，然后构造 b，使得奇数 b 可以被 f 和 a 的某个因子整除，而偶数 b-1 可以被 e 整除。在这种情况下，e=2 和 f=53（作为任意取 a=3·5·7 的结果，因此 a 有几个小的奇素数因子）。

于 2013-05-03T07:27:03.833 回答