主题
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.net.cn/Prime-GeneratingPolynomial.html

学科分类