RE: [math-fun] Re: Polynomial primogeniture
I (well, OK, a C program) factored Q(N) = N^2+N+1 for 10000 <= N < 11000, and found there to be 128 primes among these 1000 numbers. Note: x/ln(x) at Q(10^4) is ~ 5429194, whereas x/ln(x) at Q(10^4) + 1000 ~ 5429245. So the Prime Number theorem estimates about 51 primes for that run of 1000 consecutive numbers. This should be an upper bound, with high probability, for the # of primes among 1000 integers K selected randomly with Q(10^4) <= K < Q(10^4+10^3). But the actual count is 128, about 5/2 that number. Can the absence of prime factors of the form 6k-1 adequately explain such a high number of primes? --Dan A. -------------------------------------------------------------------- Don Reble djr@nk.ca writes: I wrote:
... factorization of Q(N) = N^2+N+1 ... there appears to be an unusually high frequency of Q(N)'s being prime. And also when Q(N) is composite, it appears as though there tend to be unusually few factors (and unusually large ones).
Is there a theory that would confirm these suspicions?
I might know a little bit about that...
Q is the third cyclotomic polynomial, a factor of N^3-1, and Q(N) can't be divisible by a 6k-1 prime. Since there are fewer prime factors to choose from, you get fewer factors, and more primes. See also http://www.asahi-net.or.jp/~KC2H-MSM/cn
Well, the probability of a randomly chosen [in some range] ODD integer being prime is going to be twice the probability for a randomly chosen integer [in that range]. So maybe you're really only trying to explain 5/4. --ms Dan Asimov wrote:
I (well, OK, a C program) factored Q(N) = N^2+N+1 for 10000 <= N < 11000, and found there to be 128 primes among these 1000 numbers.
Note: x/ln(x) at Q(10^4) is ~ 5429194, whereas x/ln(x) at Q(10^4) + 1000 ~ 5429245.
So the Prime Number theorem estimates about 51 primes for that run of 1000 consecutive numbers. This should be an upper bound, with high probability, for the # of primes among 1000 integers K selected randomly with Q(10^4) <= K < Q(10^4+10^3).
But the actual count is 128, about 5/2 that number.
Can the absence of prime factors of the form 6k-1 adequately explain such a high number of primes?
--Dan A.
-------------------------------------------------------------------- Don Reble djr@nk.ca writes:
I wrote:
... factorization of Q(N) = N^2+N+1 ... there appears to be an unusually high frequency of Q(N)'s being prime. And also when Q(N) is composite, it appears as though there tend to be unusually few factors (and unusually large ones).
Is there a theory that would confirm these suspicions?
I might know a little bit about that...
Q is the third cyclotomic polynomial, a factor of N^3-1, and Q(N) can't be divisible by a 6k-1 prime. Since there are fewer prime factors to choose from, you get fewer factors, and more primes. See also http://www.asahi-net.or.jp/~KC2H-MSM/cn
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
My latest Math Games column contains some interesting methods for multiplication. Nyles Heise showed how EF4E75E7×EFA03229 could be calculated in a 22×93 rectangle with WireWorld logic. I had no idea that multiplication could be done so efficiently. The full article is here: http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html The column includes a very nice article by Brian Silverman, The Virtual Computer. At http://www.mathpuzzle.com/, I show a new crossword discovery ... an 8×9 grid of french words reading across and down, found by Jean-Charles Meyrignac: D E C R O C H E S E C O E U R A N T R O N F L A N T E A T T R I S T E R P A R A P H E R A E M A C I E R A S R E I T E R A I S A S S E N A S S E I recently heard from Don Albers about the Martin Gardner Mathematical Games collection. They had to secure an enormous number of permissions, which delayed things, but he fully expects maa.org will be able to release the collection in late summer. --Ed Pegg Jr
http://www.primepuzzles.net/problems/prob_012.htm mentions the record-holding prime-producing polynomials for consecutive X f(X) = 36 X^2 - 810 X + 2753 for which |f(X)|, 0 <= X <= 44 is prime (36X^2-2358X+36809 produces the same primes in reverse order!) and f(X) = 47 X^2 - 1701 X + 10181 for which f(X) is prime for 0 <= X <= 42 -- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039
Here are some excerpts from A17 of UPINT3. Comments welcome. R. --------------------------- We have already mentioned (in {\bf A1}) Euler's famous formula $n^2+n+41$. In some sense this is best possible, but quadratic expressions with positive discriminant can yield even longer sequences of prime values (though some of them may be negative). Gilbert Fung gives $47n^2-1701n+10181$, $0\leq n\leq 42$, $\Delta = 979373$ and Russell Ruby $36n^2-810n+2753$, $0\leq n\leq 44$, $\Delta=2^23^27213$. The first 1000 values of Euler's formula include 581 primes. Edgar Karst beats this with 598 values of $2n^2-199$ and in a 91-01-01 letter, Stephen Williams announces 602 prime values of $2n^2-1000n-2609$. The corresponding numbers among the first 10000 values are 4148, 4373 and 4151. However, what is significant is not the actual density over the first so many values, which clearly has to tend to zero in all cases, but the {\bf asymptotic} density, which, if we believe Hardy \& Littlewood (see {\bf A1}), is always $c\sqrt n/\ln n$, and the best that can be done \hGidx{asymptotic density} is to make the value of $c$ as large as possible. Shanks has calculated $c=3.3197732$ for Euler's formula and $c=3.6319998$ for a polynomial $x^2+x+27941$ found by Beeger. Fung \& Williams (see reference at {\bf A1} and the references they give) have achieved $c=5.0870883$ with the formula $x^2+x+132874279528931$. Nigel Boston \& Marshall L.~Greenwood, Quadratics representing primes, {\it Amer.\ Math.\ Monthly}, {\bf102}(1995) 595--599; {\it MR} {\bf96g}:11154. Gilbert W.~Fung \& Hugh Cowie Williams, Quadratic polynomials which have a high density of prime values, {\it Math.\ Comput.}, {\bf 55}(1990) 345--353; {\it MR} {\bf 90j}:11090. Betty Garrison, Polynomials with large numbers of prime values, {\it Amer.\ Math.\ Monthly}, {\bf 97}(1990) 316--317; {\it MR} {\bf 91i}:11124. P.~Goetgheluck, On cubic polynomials giving many primes, {\it Elem.\ Math.}, {\bf 44}(1989) 70--73; {\it MR} {\bf 90j}:11014. Masaki Kobayashi, Prime producing quadratic polynomials and class-number one problem for real quadratic fields, {\it Proc.\ Japan Acad.\ Ser.\ A Math.\ Sci.}, {\bf 66}(1990) 119--121; {\it MR} {\bf 91i}:11140. D.~H.~Lehmer, On the function $x^2+x+A$, {\it Sphinx}, {\bf 6}(1936) 212--214; {\bf 7}(1937) 40. S.~Louboutin, R.~A.~Mollin \& H.~C.~Williams, Class numbers of real quadratic fields, continued fractions, reduced ideals, prime-producing polynomials and quadratic residue covers, {\it Canad.\ J.\ Math.}, {\bf44}(1992) 1--19. Richard A.~Mollin, Prime-producing quadratics, {\it Amer.\ Math.\ Monthly}, {\bf104}(1997) 529--544; {\it MR} {\bf98h}:11113. Richard A.~Mollin \& Hugh Cowie Williams, Quadratic nonresidues and prime-producing polynomials, {\it Canad.\ Math.\ Bull.}, {\bf 32}(1989) 474--478; {\it MR} {\bf 91a}:11009. [see also {\it Number Theory}, de Gruyter, 1989, 654--663 and {\it Nagoya Math.\ J.}, {\bf112}(1988) 143--151.] Joe L.~Mott \& Kermit Rose, Prime-producing cubic polynomials, {\it Ideal theoretic methods in commutative algebra $($Columbia MO} 1999) 281--317, {\it Lecture Notes in Pure and Appl.\ Math.}, {\bf220} Dekker, New York, 2001; {\it MR} {\bf2002c}:11140. ----------------------------- On Wed, 26 May 2004, M. Stay wrote:
http://www.primepuzzles.net/problems/prob_012.htm mentions the record-holding prime-producing polynomials for consecutive X
f(X) = 36 X^2 - 810 X + 2753 for which |f(X)|, 0 <= X <= 44 is prime (36X^2-2358X+36809 produces the same primes in reverse order!)
and f(X) = 47 X^2 - 1701 X + 10181 for which f(X) is prime for 0 <= X <= 42 -- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Any minute now. R. On Tue, 25 May 2004, Jud McCranie wrote:
At 06:48 PM 5/25/2004, Richard Guy wrote:
Here are some excerpts from A17 of UPINT3.
When is the third edition coming out?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (6)
-
Dan Asimov -
Ed Pegg Jr -
Jud McCranie -
M. Stay -
Mike Speciner -
Richard Guy