是否存在一不等於0的完全平方數，使得它成為連續質數個整數之積？

設有一質數p，是否存在

x*(x+1)*(x+2)*…*(x+p-1)=m^2.

x,m∈Z; m≠0

http://www.renyi.hu/~p_erdos/1939-03.pdf

Erdos在1939年證明了更強的命題, a product of positive consecutive integers is never a square.

昨天看到了上面王某魚的回答。。。

本來想用時間寫其它東西，但是有點小好奇。。。：- /

結果從昨天晚上八點到今天早上九點，至少十三個小時，一直都在思考。：- O

根本意識不到時間流逝。估計用掉了一百多張紙。其它事情都忘了，好慘。

下午到辦公室，還一直都在想這個題，然後跟同事討論了好久。（他也有國際奧賽背景，我們都超喜歡這樣的題）

---

問題如下：

x(x+1)(x+2)(x+3)。。。(x+N) = t^2

【x、t、N 都是整數，大於零】

先說簡單的case（小N），比較有意思；

（N = 1）

--&> x(x+1) = t^2

x 和 x+1 不能含有任何重複的素數元素，（中文好像叫「互素」）

所以 x 和 x+1 本身只能是平方數。

不存在兩個（大於0）的相鄰平方數，沒辦法。

（N = 2）

--&> (x-1)x(x+1) = t^2

所以 x(x^2 - 1) = t^2。

如上，x 和 x^2 - 1 也是互素關係。只能是兩個獨立平方數。

x^2 - 1 是平方數的話，又是兩個相鄰的，還是沒辦法。（經常可以用到這個道理）

（N = 3）

--&> x(x+1)(x+2)(x+3) = t^2

設 X = 2x+3

(X - 3)(X - 1)(X + 1)(X + 3) = 16t^2

(X^2 -1)(X^2 - 9) = 16t^2

(X^2 - 5)^2 - 4^2 = 16t^2

X 是奇數，所以 X^2 = 1 mod 4，所以 (X^2 - 5) = 0 mod 4，所以 (X^2 - 5)^2 = 0 mod 16

再往下推理，16a^2 - 16 = 16b^2。

怎麼又是 a^2 - b^2 = 1 這種情況。再一次說明沒辦法。

（N = 4）

--&> (x-2)(x-1)x(x+1)(x+2) = t^2

x(x^2 - 1)(x^2 - 4) = t^2

這裡有類似快速的方法解決。但是有點麻煩。

所以接下來就開始正式回答。

我們要把所有數字轉成一個集合。集合裡面的元素都是一些素數。

x = p1 ^ a1 * p2 ^ a2 * p3^a3 * ... * pK ^ aK。p1...pK 代表這個整數裡面所含有的素數。

如果 aJ 是偶數，忽略，就不放到 x 的對應集合。

aJ 是奇數的話，就把 pJ 放進 x 的那個集合。

就是把我們的 N 個 數字轉成 N 個（有順序）的集合（列表）。

也可以視為一種二進位角度：

（例如 x = 19, N = 17）

為什麼這麼做？

因為這些集合的規模和複雜程度降低了很多。這種角度大大簡化了問題。

1）兩個集合的product，是兩個二進位的 xor。比如 10101 * 10110 = 00011。

（或者說，保留了乘法的核心邏輯意義）

2）如果一行（全部xor起來的一個素數位置）= 1，也就是說最後成果有個奇數頻率的素數，所以不可能是一個平方。這一點很重要。

（在上面就能看得出來：3、5、7、13、17、19、23、29、31 這幾行都是奇數頻率，所以肯定失敗了。只要任何一行是基數綜合，也就不行了。很符合這個題了吧？）

3）還有其它用途，比如利用這些數字的距離，可以判斷出每一行（或總共）存在最多少個1。

4）最後，如果把順序切成兩段（或三段），轉成看作三個數字/三個集合。。。不能存在兩個完全一樣或完全獨立不重複的。因為這樣說明有更小的 N 已經滿足條件。

（這一點不一定要用到，但是計算小N的情況，就有這麼一些shortcut）

OK，上面的 N&<4 的情況也都可以用這樣的方法分析。不成立了。

N = 4 的邏輯呢，是這樣的：

總共就五個數字。但是大於 4 的素數不能出現。（因為最多只能出現一次，又是奇數）

所以只剩下 2 和 3。兩個素數，無論是什麼，也就可以看作 A 和 B。

兩個元素，有多少個不同的集合呢？四個！

{empty}，{A}，{B}，{A、B}

（也可以這樣理解：這五個數字可以歸類為：n1^2，2 * n2^2 * 2，3 * n3^2, 6 * n4^2）

so？

五個數字，四個類別。必須有一個類別包含兩個數字。(pigeonhole principle)

兩個數字在一個類別裡面。這就存在 Ap^2 - Aq^2 = kA 的情況。

p ^2 - q^2 = k。兩個平方相差指定的距離。至少解答數量有限。

k = 0,1,2 都不行。跟上面的道理一樣。沒有平方數相鄰這麼近。k &> 2 也不行了，因為 kA &> 4，五個距離這麼近的數字，肯定不存在。

所以。。。N = 4 不可能滿足了呀。

---

在往上，N=5,6,7...，我相信知友都可以用類似的方法證明。證明解答其不存在。昨天我也一直算到 N = 12左右。每次都極大限制 x。

有時候，a^2 - b^2 = 4,5,8,9 之類的，確實可以成立。然後呢？這樣的情況可以讓你直接得出特定的x。測試一下，也都不成立，總存在另外一行的單獨元素。

---

如何證明所有N都不存在結果？這就比較難了。

我們可以轉換一下問題；需要找到一個表格。。。（上面那種表格），滿足所有以上條件，又得符合「任意一對集合都不相等」的要求。。。

為什麼所有表格都不可能滿足？

1） 制定 N 的「表格」，至少存在 N/5 個「元素數量 &<=1」 的集合（列、數字）。

我的很二的證明法（有點 hand-wavy）：

X = 1/2 + 1/3 + 1/5 + 1/7 + ... （1/素數）... 長得很慢，但仍然接近於無線，這一點很容易證明。

【這就是元素數量的最大比例】

"X - X^2 + X^3 - ..."，再排除重複的，這類東西呢？

比如：

1/2+1/3-1/4+1/5-1/6+1/7+1/8-1/9-1/10+1/11+1/12+1/13-1/14-1/15-1/16+1/17-1/18 ...

意思就是扣除所有的重複偶數factors，代表二元以上的"列數"。真正的「一元素列」數量肯定少於這個比例。（研究這個series可能是這類問題的本身）

然後這個東西永遠不能超過1。具體等於什麼我不知道。也非常好奇。也可能漸漸接近零。但是絕對少於0.8。

2）也就是說，無論N多大，永遠存在 &> N/5 個 「集合元素數量 &<2 的數字」。

這時候，我們可以完全忽略順序。

只要在意 &< N 的素數數量。如果比N/5大，那沒辦法了。不一定存在重複的。

但是，最起碼，N &> 100 的時候，素數數量開始少於 N/5，【是 N / log(N) 這樣的】。

3）多元素的集合（數字）的數量 &< 4/5，剩下的也只有單個元素或無元素的集合。

只要表格內素數數量 &< 1/5，也就是說明存在兩個重複的集合。

無論N多大，包括小N，也都存在這種情況。

---

存在兩個重複的集合呢，正好說明 x 的範圍 被固定住了。只有finite solutions。

也不算徹底證明，但至少提供了一個「任意N、finite解答」的結論。

或者說，提供了一個尋找解答的簡單演算法。你選擇一個N，把上面的 4/5 和 1/5 具體比例算清楚。每次都至少有一個。因此得到重複元素的數量最小值。再搜索分析這些情況就得了。

（N達到了一定的兩級，也可以證明重複二元集合的存在，更有限）。

（如果要徹底證明，估計要用到更抽象的素數頻率理論）