為什麼 y=x^2-x-1 中包含質數出現得比較多？

02-05

我在無意中搗騰數學時，發現了一個方法，可以很容易找到很大的質數。
只看上圖應該已能明白原理。
以公式 y=x^2-x-1 能求得一個數組，常出現質數。

一個多項式里素數多不多

不僅要看數字小時的素數數量

也要考慮上達無窮時的素數密度

$Tiny{(其實一般這兩者是正相關的)}$

根據 Bateman–Horn 猜想

我們說對於單個多項式素數密度的估計可以寫成:

$box[#EFF,5px,border:2px solid red]{ pi_{P(x)}sim {frac {1}{mathfrak{D}}}prod _{pinmathbb{P}}^infty{frac {p-mathfrak{R}(p)}{p-1}} int _{2}^{x}{frac {mathrm{d}t}{log t}} }$

其中 $mathfrak{D}$ 表示多項式的次數, $mathfrak{R}(p)$ 表示給定多項式在模 $p$ 的根的個數.

可以看到增長速度其實都是

$ext{li}(x)= ext{li}(2)+int_2^x frac{mathrm{d}t}{log (t)}simfrac{x left(log x left(log x left(log ^2x+log x+2 ight)+6 ight)+24 ight)}{log ^5x}+Oleft(frac{1}{x^2} ight)$

所以關鍵在於前面的一堆係數.

但是這個無窮級數的計算在技術上是不可能的

無法計算一般多項式所有模 $p$ 的根 (數學上也不行, 據我所知)

好在這個級數收斂性還說得過去

一般算個10^4項差不多了

f=n^2-n-1; Rm[p_]:=Length[Solve[f==0,n,Modulus-&>p]]; cc=(#-Rm[#])/(#-1)/@Prime@Range[10^4]; Times@@cc/Exponent[f,n]//N

計算結果表明 $pi_{x^2-x-1}sim 1.32982 int _{2}^{x}{frac {mathrm{d}t}{log t}}$

這個成績可不夠好

不過至少比 $f(x)=x$ 密度高...

根據定義 $pi_{x}simint _{2}^{x}{frac {mathrm{d}t}{log t}}$ ....

其實沒有比這個低的了, 這是下限....

一次函數確實很佔優勢, 因為不用除次數

$pi_{2xpm1}sim2int _{2}^{x}{frac {mathrm{d}t}{log t}}$ ,達到上限了, 一次函數最高才2.

一次函數很容易達到上限, 隨便舉個例子 $2n+1,4n+1,8n+1$ 的素數密度其實都是一樣的.

大數學家歐拉, 他發現的 $x^2 - x + 41$ ,能連續產生40個素數啊.

同時 ${pi}_{x^2-x+41}sim 3.30206 int _{2}^{x}{frac {mathrm{d}t}{log t}}$

幾百年來無人能破

Update:

其實近年來藉助計算機才發現了更好的二次函數

${pi}_{36 x^2 - 810 x + 2753}sim 3.90825 int _{2}^{x}{frac {mathrm{d}t}{log t}}$

已經相當的接近4了, 不過要是數論沒有大的突破要達到 4 我想還是不可能的...

Update × 2:

應知乎小管家的要求修改措辭...

瀉藥，如果你想證明這個函數是獨特的話，你得證明其它的函數沒有這麼多素數。

給我幾分鐘寫個代碼對比下

=====================================

利用MATLAB代碼，比較公式y=x^2-x-1 和 y=2x-1 還有 y=2x+1 在 x=15000000後1001位數的素數比率如下

y=x^2-x-1： 0.1089

y=2x-1：0.1199

y=2x+1： 0.1189

可見題主你找到的這個公式，和隨便一個簡單的公式比起來都沒有優勢。所以這個問題的答案應該是質數普遍存在於大部分的函數里。

另外翻了翻答案修改記錄，題主有自己的想法很不錯，既然是高中生，那麼建立自己的知識儲備才是最重要的，自己的想法對錯其實並不關鍵，因為在你現在這個水平幾乎沒可能提出一個重大的發現，過多在意這類東西只會分散你的精力。就拿這個問題來說，其實代碼幾分鐘能解決的事情，卻可以浪費你很多時間，這就是自己的能力不足所導致的。每個有用的想法往往伴隨著上百個無用的想法，當你學的足夠多的時候，有足夠強的基礎可以快速驗證大部分不靠譜的想法的時候，再做這類事情才有可能從一堆糟粕中發現有意義的東西。

附上MATLAB代碼，你可以看到相比於你手工做，代碼的效率有多高：

x=15000000:15001000 y=x.^2-x-1; prime=isprime(y); mean(prime)


y=2*x-1;

prime=isprime(y);

mean(prime)

y=2*x+1; prime=isprime(y); mean(prime)

================================================

有些答主通過數學已經描述的很好了，這裡再提供些計算機硬算的結果吧。評論中有人提示應該按照y的範圍來算密度而不是按照x的範圍，所以我把代碼改了下。題主找的函數確實素數密度還不錯，手動想找個超過他的不太容易，所以直接上了循環，y的範圍取100000~10000000，結果如下（函數素數密度）：

x^2-x-1 0.233

x^2-99*x+1 0.2895

x^2-93*x+1 0.268

x^2-89*x+1 0.2437

x^2-87*x+1 0.2549

x^2-81*x+1 0.3411

x^2-49*x+1 0.3223

x^2-39*x+1 0.2833

x^2-33*x+1 0.246

x^2-21*x+1 0.3777

x^2+21*x+1 0.3777

x^2+33*x+1 0.246

x^2+39*x+1 0.2833

x^2+49*x+1 0.3223

x^2+81*x+1 0.3411

x^2+87*x+1 0.2549

x^2+89*x+1 0.2437

x^2+93*x+1 0.268

x^2+99*x+1 0.2895

可見超過題主的函數還是有不少的，當然分布比較廣泛，手動找比較難遇到。

附上MATLAB代碼

limit=[100000,10000000]; x=100:10000; y=x.^2-x-1; y=y(y&>limit(1)y&limit(1)y&


孿生素數猜想是有一個推廣的： 即 Schinzels hypothesis H 。如下：
這個猜想告訴你什麼時候一組多項式能取到無限個素數（給出了充要條件)。並且這樣的素數增長率也被猜了， 叫  Bateman–Horn conjecture  如下

 
這兩個猜想到現在沒有反例，當然也沒有被證明。
如果你相信這兩個猜想，那麼
（1） 你這個方程可以取無數個素數；
（2） 你可以算出你這個方程有多大概率取到素數。
PS: Schinzels Hypothesis 在丟番圖幾何中有很多應用，參見
O. Wittenberg, Y. Harpaz: On the fibration method for zero-cycles and rational points, Annals of Mathematics 183 (2016), no. 1, 229–295.
這篇文章第9節.

在素數這件事上，有很多情況下只是運氣好而已。
比如費馬數

函數y=x更厲害，它包含了所有的質數呢

 
這個說法是不對的
要找一個包含質數最多的函數，那就是y=x

給個簡單解釋。這個函數當 x 較小時確實多多給出素數，原因是：
        y=x(x-1)-1. 
舉例，考慮把x=6帶進去，由於2，3，5都整除 x(x-1), 所以得到素數。類似的，如果 x 以比他小的所有質數為因數，那麼 y 給出素數。這個原因得這個函數在 x 較小時給出許多素數。當 x 較大時，這個原因幾乎不起作用了，給出素數多不多我就不知道了。

謝邀。
很多公式(就借用這個詞吧)都包含無窮多個質數。
例如，最簡單的 y=2x+1
事實上，除了少數如y=2x之類的公式，
可能對於大多數公式，想證明其不包含無窮多個質數，是不 trivial的。
／／
另外，你提到你的公式很容易找到大的質數，但我沒有發現這一點。
你的公式在構造上並不能保證公式的第幾項一定是質數。
也就是說，對於任何一個你找到的大數，你仍需要驗證它是否是質數。
／／以上

請先查閱一下已發現的素數，再來掂量一下怎樣的素數才叫「很大」。

學術界有民間科學一說，
您可以百度一下。
學術研究中，民間科學不是不好，但常常犯一些令人啼笑皆非的錯誤。
您的成果可以查新，公布，或請專業數論專家看一下，是否屬於已有成果，還是重大創新？
數論發展到今天，用傳統手段，創新非常困難。希望您的成果是個天才創意。
我是做方程的，對數論不大懂，請專業人士指教。

巧了，我也發現了一個方法，可以很容易找到很大的質數。比你的還大一點。
列兩個質數，以示不假。

實際上，按照現在的演算法與計算機性能與已知結果，找到（或者說生成）一個幾百位的素數並不困難。
和大素數相關的加密演算法的重點，一般核心在大數分解上。
簡單地說，生成兩個大素數，很簡單。
把它們乘起來，超簡單。
但是，如果只知道乘積結果，需要反過來倒推兩個質因子，就比較困難了。
比如，試試分解質因數： 

  推薦閱讀：


TAG:數學 | 科研 | 程序 | 科學 |