主题
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)。

另请参阅

布尼亚科夫斯基猜想, 类数, 欧拉多项式, 欧拉素数, 黑格纳数, 欧拉幸运数, 素数算术级数, 素数丢番图方程, 辛泽尔假设

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

素数生成多项式

引用为

Weisstein, Eric W. "素数生成多项式。" 来自 MathWorld-- Wolfram Web 资源。 https://mathworld.net.cn/Prime-GeneratingPolynomial.html

学科分类