主題
Search

素數生成多項式

下載 Mathematica 筆記本下載 Wolfram 筆記本

勒讓德證明了不存在總是給出素數的有理代數函式。1752 年，哥德巴赫證明了，對於所有整數值，沒有具有整數係數的多項式可以給出素數（Nagell 1951, p. 65; Hardy and Wright 1979, pp. 18 和 22）。然而，存在一個 10 個變數的多項式，其係數為整數，使得素數的集合等於這個多項式的正值集合，當變數取遍所有非負整數時獲得，儘管它實際上是一組偽裝的丟番圖方程（Ribenboim 1991）。Jones、佐藤、和田和維恩斯也找到了一個 26 個變數的 25 次多項式，其正值恰好是素數（Flannery and Flannery 2000, p. 51）。

PrimeGeneratingPolynomials

上面的圖可視化了形如 x^2+ax+b 的二次多項式生成的素數數量，對於 a 和 b 從 -200 到 200 (M. Trott, 私人通訊)。

最著名的僅生成（可能在絕對值上）素數的多項式是

n^2+n+41,
(1)

由尤拉提出（Euler 1772; Nagell 1951, p. 65; Gardner 1984, p. 83; Ball and Coxeter 1987），它為 40 個連續整數 n=0 到 39 給出了不同的素數。（n^2-n+41，由勒讓德在 1798 年提出，對於 n=1 到 40 給出了相同的 40 個素數。這些數字被 Flannery 和 Flannery (2000, p. 47) 稱為“尤拉數”，並且其中是素數的集合在本工作中被稱為尤拉素數。透過將公式轉換為

n^2-79n+1601=(n-40)^2+(n-40)+41,
(2)

對於 80 個連續整數獲得了素數，對應於上述公式給出的 40 個素數，每個取兩次（Hardy and Wright 1979, p. 18）。如果 p(x) 對於 0<=x<=n 是素數生成的，那麼 p(n-x) 也是。

下表給出了一些低階多項式，它們對於前幾個非負值僅生成（可能在絕對值上）素數（Mollin 和 Williams 1990）。透過替換從其他多項式獲得的多項式，例如，勒讓德和哈代和賴特的 n^2-n+41 的變體，未包括在內。在表格中，d.p. 表示當插入從 0 到 n 的值時，多項式生成的不同素數的數量。

多項式從 0 到 n 的素數不同素數OEIS參考文獻
1/4(n^5-133n^4+6729n^3-158379n^2+1720294n-6823316)5657Dress 和 Landreau (2002), Gupta (2006)
1/(36)(n^6-126n^5+6217n^4-153066n^3+1987786n^2-13055316n+34747236)5455Wroblewski 和 Meyrignac (2006)
n^4-97n^3+3294n^2-45458n+2135894949Beyleveld (2006)
n^5-99n^4+3588n^3-56822n^2+348272n-2863974647Wroblewski 和 Meyrignac (2006)
-66n^3+3845n^2-60897n+2518314546Kazmenko 和 Trofimov (2006)
36n^2-810n+27534445A050268Fung 和 Ruby
3n^3-183n^2+3318n-187574643S. M. Ruiz (私人通訊, 2005 年 11 月 20 日)
47n^2-1701n+101814243A050267Fung 和 Ruby
103n^2-4707n+503834243Speiser (私人通訊, 2005 年 6 月 14 日)
n^2-n+414040A005846尤拉
42n^3+270n^2-26436n+2507033940Wroblewski 和 Meyrignac
43n^2-537n+29713435J. Brox (私人通訊, 2006 年 3 月 27 日)
8n^2-488n+72436131F. Gobbo (私人通訊, 2005 年 12 月 27 日)
6n^2-342n+49035729J. Brox (私人通訊, 2006 年 3 月 27 日)
2n^2+292829A007641勒讓德 (1798)
7n^2-371n+48712324F. Gobbo (私人通訊, 2005 年 12 月 26 日)
3n^2+3n+232122R. Frame (私人通訊, 2018 年 12 月 30 日)
n^4+29n^2+1011920E. Pegg, Jr. (私人通訊, 2005 年 6 月 14 日)
3n^2+39n+371718A. Bruno (私人通訊, 2009 年 6 月 12 日)
n^2+n+171516A007635勒讓德
4n^2+4n+591314A048988Honaker
2n^2+111011A050265
n^3+n^2+171011A050266

一個特別差的多項式是 n^6+1091，對於 n=1, ..., 3905 不是素數，但是對於 n=3906, 4620, 5166, 5376, 5460, ... 是素數 (OEIS A066386; Shanks 1971, 1993; Wells 1997, p. 151)。其他這種型別的多項式包括 n^6+29450922301244534，這是 Carmody 在 2006 年發現的 (Rivera)，並且對於 63693, 64785, 70455, 90993, 100107, ... 是素數 (OEIS A119276)，以及 x^(12)+488669，對於 616980, 764400, 933660, ... 是素數 (OEIS A122131)。

Le Lionnais (1983) 將數字 p 命名為尤拉幸運數，這樣尤拉式多項式

n^2+n+p
(3)

對於 n=0, 1, ..., p-2 是素數 (其中 p=41 的情況對應於尤拉公式)。Rabinowitz (1913) 表明，對於一個素數 p>0，尤拉多項式對於 n in [0,p-2] 表示一個素數 (排除平凡情況 p=3) 當且僅當 域 Q(sqrt(1-4p)) 具有類數 h=1 時 (Rabinowitz 1913, Le Lionnais 1983, Conway and Guy 1996)。正如 Stark (1967) 確定的，只有九個數字 -d 使得 h(-d)=1 (黑格納數 -1, -2, -3, -7, -11, -19, -43, -67, 和 -163)，並且在這些數中，只有 7, 11, 19, 43, 67 和 163 是所需的形式。因此，唯一的尤拉幸運數是 2, 3, 5, 11, 17 和 41 (le Lionnais 1983, OEIS A014556)，並且不存在更好的尤拉形式的素數生成多項式。透過顯式地寫出，可以看到數字 163 和 43 與上面列出的一些富含素數的多項式之間的聯絡

x^2+x+41=(x+1/2)^2+(163)/4
(4)
x^2+x+11=(x+1/2)^2+(43)/4,
(5)

等等。

尤拉還考慮了形如

2x^2+p
(6)

的二次方程，並表明這對於 素數 p>0 在 x in [0,p-1] 中給出素數 當且僅當 Q(sqrt(-2p)) 具有類數 2 時，這僅允許 p=3, 5, 11 和 29。Baker (1971) 和 Stark (1971) 表明，對於 p>29，不存在這樣的域。對於形如

px^2+px+n
(7)

的多項式也發現了類似的結果 (Hendy 1974)。

另請參閱

布尼亞科夫斯基猜想, 類數, 尤拉多項式, 尤拉素數, 黑格納數, 尤拉幸運數, 素數算術級數, 素數丟番圖方程, 辛澤爾假設

使用 探索

參考文獻

Abel, U. and Siebert, H. "Sequences with Large Numbers of Prime Values." Am. Math. Monthly 100, 167-169, 1993.Baker, A. "Linear Forms in the Logarithms of Algebraic Numbers." Mathematika 13, 204-216, 1966.Baker, A. "Imaginary Quadratic Fields with Class Number Two." Ann. Math. 94, 139-152, 1971.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 60, 1987.Boston, N. and Greenwood, M. L. "Quadratics Representing Primes." Amer. Math. Monthly 102, 595-599, 1995.Conway, J. H. and Guy, R. K. "The Nine Magic Discriminants." In The Book of Numbers. New York: Springer-Verlag, pp. 224-226, 1996.Courant, R. and Robbins, H. What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, p. 26, 1996.Dudley, U. "History of Formula for Primes." Amer. Math. Monthly 76, 23-28, 1969.Euler, L. Nouveaux Mémoires de l'Académie royale des Sciences. Berlin, p. 36, 1772.Flannery, S. and Flannery, D. In Code: A Mathematical Journey. London: Profile Books, p. 47, 2000.Forman, R. "Sequences with Many Primes." Amer. Math. Monthly 99, 548-557, 1992.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 83-84, 1984.Garrison, B. "Polynomials with Large Numbers of Prime Values." Amer. Math. Monthly 97, 316-317, 1990.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Hendy, M. D. "Prime Quadratics Associated with Complex Quadratic Fields of Class Number 2." Proc. Amer. Math. Soc. 43, 253-260, 1974.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 108-109, 1998.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, pp. 88 and 144, 1983.Mollin, R. A. and Williams, H. C. "Class Number Problems for Real Quadratic Fields." Number Theory and Cryptology; LMS Lecture Notes Series 154, 1990.Nagell, T. "Primes in Special Arithmetical Progressions." §44 in Introduction to Number Theory. New York: Wiley, pp. 60 and 153-155, 1951.Pegg, E. Jr. "Al Zimmermann's Programming Contests: Prime Generating Polynomials." Mar. 13, 2006. http://www.recmath.org/contest/description.php.Pegg, E. Jr. "Math Games: Prime Generating Polynomials." Jul. 17, 2006. http://www.maa.org/editorial/mathgames/mathgames_07_17_06.html.Rabinowitz, G. "Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern." Proc. Fifth Internat. Congress Math. (Cambridge) 1, 418-421, 1913.Ribenboim, P. The Little Book of Big Primes. New York: Springer-Verlag, 1991.Rivera, C. "Highly Composite Polynomials." http://www.primepuzzles.net/puzzles/puzz_275.htm.Shanks, D. "A Low Density of Primes." J. Recr. Math. 5, 272-275, 1971.Shanks, D. Ex. 162 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 222, 1993.Sloane, N. J. A. Sequences A005846/M5273, A007635, A007641, A014556, A048988, A050265, A050266, A050267, A050268, A066386, A119276, and A122131 in "The On-Line Encyclopedia of Integer Sequences."Stark, H. M. "A Complete Determination of the Complex Quadratic Fields of Class Number One." Michigan Math. J. 14, 1-27, 1967.Stark, H. M. "An Explanation of Some Exotic Continued Fractions Found by Brillhart." In Computers in Number Theory, Proc. Science Research Council Atlas Symposium No. 2 held at Oxford, from 18-23 August, 1969 (Ed. A. O. L. Atkin and B. J. Birch). London: Academic Press, 1971.Stark, H. M. "A Transcendence Theorem for Class Number Problems." Ann. Math. 94, 153-173, 1971.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, 1997.

在 上引用

素數生成多項式

引用為

Weisstein, Eric W. "素數生成多項式。" 來自 -- 資源。 https://mathworld.tw/Prime-GeneratingPolynomial.html

學科分類