Is the notorious $n^2 + n + 41$ prime generator the last of its type?
up vote
72
down vote
favorite
The polynomial $n^2+n+41$ famously takes prime values for all $0le nlt 40$. I have read that this is closely related to the fact that 163 is a Heegner number, although I don't understand the argument, except that the discriminant of $n^2+n+41$ is $-163$. The next smaller Heegner number is 67, and indeed $n^2+n+17$ shows the same behavior, taking prime values for $0le nlt 16$.
But 163 is the largest Heegner number, which suggests that this is the last such coincidence, and that there might not be any $k>41$ such that $n^2+n+k$ takes on an unbroken sequence of prime values.
Is this indeed the case? If not, why not?
Secondarily, is there a $k>41$, perhaps extremely large, such that $n^2+n+k$ takes on prime values for $0<n<j$ for some $j>39$?
number-theory
add a comment |
up vote
72
down vote
favorite
The polynomial $n^2+n+41$ famously takes prime values for all $0le nlt 40$. I have read that this is closely related to the fact that 163 is a Heegner number, although I don't understand the argument, except that the discriminant of $n^2+n+41$ is $-163$. The next smaller Heegner number is 67, and indeed $n^2+n+17$ shows the same behavior, taking prime values for $0le nlt 16$.
But 163 is the largest Heegner number, which suggests that this is the last such coincidence, and that there might not be any $k>41$ such that $n^2+n+k$ takes on an unbroken sequence of prime values.
Is this indeed the case? If not, why not?
Secondarily, is there a $k>41$, perhaps extremely large, such that $n^2+n+k$ takes on prime values for $0<n<j$ for some $j>39$?
number-theory
7
It is certainly last one. See if I can find references. It is the discriminant of $x^2 + x y + 41 y^2$ that is the important thing here.
– Will Jagy
Jan 28 '13 at 23:15
4
Problem 6 of the 28th IMO (Cuba) was: Let $n$ be an integer greater than or equal to $2$. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n/3$, then $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n − 2$. Too bad that $n=41$ is the largest one for which this holds.
– Andrés E. Caicedo
Jan 28 '13 at 23:23
1
Frequently cited in this connection is: "Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields" by R. A. Mollin. Acta Arithmetica 74 #1 (1996) matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7412.pdf
– MJD
Jan 29 '13 at 0:04
I edited in an elementary proof that class number larger than one (for binary form $x^2 + xy + p y^2$) implies that $x^2 + x + p$ represents a composite number with small $x.$
– Will Jagy
Jan 29 '13 at 5:51
2
n² + 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79, but it is trivially related to the euler one.
– wim
Jan 29 '13 at 7:51
add a comment |
up vote
72
down vote
favorite
up vote
72
down vote
favorite
The polynomial $n^2+n+41$ famously takes prime values for all $0le nlt 40$. I have read that this is closely related to the fact that 163 is a Heegner number, although I don't understand the argument, except that the discriminant of $n^2+n+41$ is $-163$. The next smaller Heegner number is 67, and indeed $n^2+n+17$ shows the same behavior, taking prime values for $0le nlt 16$.
But 163 is the largest Heegner number, which suggests that this is the last such coincidence, and that there might not be any $k>41$ such that $n^2+n+k$ takes on an unbroken sequence of prime values.
Is this indeed the case? If not, why not?
Secondarily, is there a $k>41$, perhaps extremely large, such that $n^2+n+k$ takes on prime values for $0<n<j$ for some $j>39$?
number-theory
The polynomial $n^2+n+41$ famously takes prime values for all $0le nlt 40$. I have read that this is closely related to the fact that 163 is a Heegner number, although I don't understand the argument, except that the discriminant of $n^2+n+41$ is $-163$. The next smaller Heegner number is 67, and indeed $n^2+n+17$ shows the same behavior, taking prime values for $0le nlt 16$.
But 163 is the largest Heegner number, which suggests that this is the last such coincidence, and that there might not be any $k>41$ such that $n^2+n+k$ takes on an unbroken sequence of prime values.
Is this indeed the case? If not, why not?
Secondarily, is there a $k>41$, perhaps extremely large, such that $n^2+n+k$ takes on prime values for $0<n<j$ for some $j>39$?
number-theory
number-theory
edited Feb 10 '13 at 5:45
asked Jan 28 '13 at 23:08
MJD
46.8k28205390
46.8k28205390
7
It is certainly last one. See if I can find references. It is the discriminant of $x^2 + x y + 41 y^2$ that is the important thing here.
– Will Jagy
Jan 28 '13 at 23:15
4
Problem 6 of the 28th IMO (Cuba) was: Let $n$ be an integer greater than or equal to $2$. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n/3$, then $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n − 2$. Too bad that $n=41$ is the largest one for which this holds.
– Andrés E. Caicedo
Jan 28 '13 at 23:23
1
Frequently cited in this connection is: "Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields" by R. A. Mollin. Acta Arithmetica 74 #1 (1996) matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7412.pdf
– MJD
Jan 29 '13 at 0:04
I edited in an elementary proof that class number larger than one (for binary form $x^2 + xy + p y^2$) implies that $x^2 + x + p$ represents a composite number with small $x.$
– Will Jagy
Jan 29 '13 at 5:51
2
n² + 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79, but it is trivially related to the euler one.
– wim
Jan 29 '13 at 7:51
add a comment |
7
It is certainly last one. See if I can find references. It is the discriminant of $x^2 + x y + 41 y^2$ that is the important thing here.
– Will Jagy
Jan 28 '13 at 23:15
4
Problem 6 of the 28th IMO (Cuba) was: Let $n$ be an integer greater than or equal to $2$. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n/3$, then $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n − 2$. Too bad that $n=41$ is the largest one for which this holds.
– Andrés E. Caicedo
Jan 28 '13 at 23:23
1
Frequently cited in this connection is: "Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields" by R. A. Mollin. Acta Arithmetica 74 #1 (1996) matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7412.pdf
– MJD
Jan 29 '13 at 0:04
I edited in an elementary proof that class number larger than one (for binary form $x^2 + xy + p y^2$) implies that $x^2 + x + p$ represents a composite number with small $x.$
– Will Jagy
Jan 29 '13 at 5:51
2
n² + 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79, but it is trivially related to the euler one.
– wim
Jan 29 '13 at 7:51
7
7
It is certainly last one. See if I can find references. It is the discriminant of $x^2 + x y + 41 y^2$ that is the important thing here.
– Will Jagy
Jan 28 '13 at 23:15
It is certainly last one. See if I can find references. It is the discriminant of $x^2 + x y + 41 y^2$ that is the important thing here.
– Will Jagy
Jan 28 '13 at 23:15
4
4
Problem 6 of the 28th IMO (Cuba) was: Let $n$ be an integer greater than or equal to $2$. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n/3$, then $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n − 2$. Too bad that $n=41$ is the largest one for which this holds.
– Andrés E. Caicedo
Jan 28 '13 at 23:23
Problem 6 of the 28th IMO (Cuba) was: Let $n$ be an integer greater than or equal to $2$. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n/3$, then $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n − 2$. Too bad that $n=41$ is the largest one for which this holds.
– Andrés E. Caicedo
Jan 28 '13 at 23:23
1
1
Frequently cited in this connection is: "Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields" by R. A. Mollin. Acta Arithmetica 74 #1 (1996) matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7412.pdf
– MJD
Jan 29 '13 at 0:04
Frequently cited in this connection is: "Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields" by R. A. Mollin. Acta Arithmetica 74 #1 (1996) matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7412.pdf
– MJD
Jan 29 '13 at 0:04
I edited in an elementary proof that class number larger than one (for binary form $x^2 + xy + p y^2$) implies that $x^2 + x + p$ represents a composite number with small $x.$
– Will Jagy
Jan 29 '13 at 5:51
I edited in an elementary proof that class number larger than one (for binary form $x^2 + xy + p y^2$) implies that $x^2 + x + p$ represents a composite number with small $x.$
– Will Jagy
Jan 29 '13 at 5:51
2
2
n² + 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79, but it is trivially related to the euler one.
– wim
Jan 29 '13 at 7:51
n² + 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79, but it is trivially related to the euler one.
– wim
Jan 29 '13 at 7:51
add a comment |
6 Answers
6
active
oldest
votes
up vote
42
down vote
accepted
See http://en.wikipedia.org/wiki/Heegner_number#Consecutive_primes
Here is a longer piece Rabinowitz published on the topic below
Rabinowitz showed, in 1913, that $x^2 + x + p$ represent the maximal number of consecutive primes if and only if $x^2 + x y + p y^2$ is the only (equivalence class of) positive binary quadratic form of its discriminant. This condition is called "class number one." For negative discriminants the set of such discriminants is finite, called Heegner numbers.
Note that if we take $x^2 + x + ab$ so that the constant term is composite, we get composite outcome both for $x=a$ and $x=b,$ so the thing quits early. In the terms of Rabinowitz, we would also have the form $a x^2 + x y + b y^2,$ which would be a distinct "class" in the same discriminant, thus violating class number one. So it all fits together. That is, it is "reduced" if $0 < a leq b,$ and distinct from the principal form if also $a > 1.$
For binary forms, I particularly like Buell, here is his page about class number one: BUELL. He does everything in terms of binary forms, but he also gives the relationship with quadratic fields. Furthermore, he allows both positive and indefinite forms, finally he allows odd $b$ in $a x^2 + b x y + c y^2.$ Note that I have often answered MSE questions about ideals in quadratic fields with these techniques, which are, quite simply, easy. Plus he shows the right way to do Pell's equation and variants as algorithms, which people often seem to misunderstand. Here I mean Lagrange's method mostly.
EEDDIITT: I decided to figure out the easier direction of the Rabinowitz result in my own language. So, we begin with the principal form, $langle 1,1,p rangle$ with some prime $p geq 3. $ It follows that $2p-4 geq p-1$ and
$$ p-2 geq frac{p-1}{2}. $$
Now, suppose we have another, distinct, reduced form of the same discriminant,
$$ langle a,b,c rangle. $$ There is no loss of generality in demanding $b > 0.$ So reduced means $$ 1 leq b leq a leq c $$ with $b$ odd, both $a,c geq 2,$ and
$$ 4ac - b^2 = 4 p - 1. $$ As $b^2 leq ac,$ we find $3 b^2 leq 4p-1 $ and, as $p$ is positive,
$ b leq p.$
Now, define $$ b = 2 beta + 1 $$ or $ beta = frac{b-1}{2}. $ From earlier we have
$$ beta leq p-2. $$
However, from $4ac - b^2 = 4p-1$ we get $4ac+1 = b^2 + 4 p,$ then
$ 4ac + 1 = 4 beta^2 + 4 beta + 1 + 4 p, $ then $4ac = 4 beta^2 + 4 beta + 4 p, $ then
$$ ac = beta^2 + beta + p, $$
with $0 leq beta leq p-2.$ That is, the presence of a second equivalence class of forms has forced $x^2 + x + p$ to represent a composite number ($ac$) with a small value $ x = beta leq p-2,$ thereby interrupting the supposed sequence of primes. $bigcirc bigcirc bigcirc bigcirc bigcirc$
EEDDIITTEEDDIITT: I should point out that the discriminants in question must actually be field discriminants, certain things must be squarefree. If I start with $x^2 + x + 7,$ the related $x^2 + x y + 7 y^2$ of discriminant $-27$ is of class number one, but there is the imprimitive form $ langle 3,3,3 rangle $ with the same discriminant. Then, as above, we see that $x^2 + x + 7 = 9$ with $x=1 =(3-1)/2.$
[ Rabinowitz, G. “Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern.” Proc. Fifth Internat. Congress Math. (Cambridge) 1, 418-421, 1913. ]
Edit October 30, 2013. Somebody asked at deleted question
Smallest positive integer $n$ s.t. f(n) = $n^2 + n + 41$ is composite?
about the other direction in Rabinowitz (1913), and a little fiddling revealed that I also know how to do that. We have a positive principal form $$ langle 1,1,p rangle $$ where $$ - Delta = 4 p - 1 $$ is also prime. Otherwise there is a second genus unless $ - Delta = 27 $ or $ - Delta = 343 $ or similar prime power, which is a problem I am going to ignore; our discriminant is minus a prime, $ Delta = 1- 4 p . $
We are interested in the possibility that $n^2 + n + p$ is composite for $0 leq n leq p-2.$ If so, let $q$ be the smallest prime that divides such a composite number. We have $n^2 + n + p equiv 0 pmod q.$ This means $(2n+1)^2 equiv Delta pmod q,$ so we know $Delta$ is a quadratic residue. Next $n^2 + n + p leq (p-1)^2 + 1.$ So, the smallest prime factor is smaller than $p-1,$ and $q < p,$ so $q < - Delta.$
Let's see, the two roots of $n^2 + n + p pmod q$ add up to $q-1.$ One may confirm that if $m = q-1-n,$ then $m^2 + m + p equiv 0 pmod q.$ However, we cannot have $n = (q-1)/2$ with $n^2 + n + p pmod q,$ because that implies $Delta equiv 0 pmod q,$ and we were careful to make $- Delta$ prime, with $q < - Delta.$ Therefore there are two distinct values of $n pmod q,$ the two values add to $q-1.$ As a result, there is a value of $n$ with $n^2 + n + p equiv 0 pmod q$ and $n < frac{q-1}{2}.$
Using the change of variable matrix
$$
left(
begin{array}{cc}
1 & n \
0 & 1
end{array}right)
$$
written on the right, we find that
$$ langle 1,1,p rangle sim langle 1,2n+1,qs rangle $$
where $n^2 + n + p = q s,$ with $2n+1 < q$ and $q leq s.$ As a result, the new form
$$ langle q,2n+1,s rangle $$
is of the same discriminant but is already reduced, and is therefore not equivalent to the principal form. Thus, the class number is larger than one.
Comment: by the rules for comparing $h(Delta)$ and $h(Delta p^2),$ the only prime power that might work is $27,$ and indeed $h(-27) = 1.$ But $h(-243) = 3.$ Theorem 7.4 on pages 117-118 in Buell, Binary Quadratic Forms (1989).
– Will Jagy
Oct 31 '13 at 7:47
add a comment |
up vote
12
down vote
To answer the second part of your question: The requirement that $n^2+n+k$ be prime for $0lt nlt40$ defines a prime constellation. The first Hardy–Littlewood conjecture, which is widely believed to be likely to hold, states that the asymptotic density of prime constellations is correctly predicted by a probabilistic model based on independently uniformly distributed residues with respect to all primes. Here's a Sage session that calculates the coefficient for your prime constellation:
sage: P = Primes ();
sage: coefficient = 1;
sage: for i in range (0,10000) :
... p = P.unrank (i);
... if (p < 39^2 + 39) :
... admissible = list (true for j in range (0,p));
... for n in range (1,40) :
... admissible [(n^2+n) % p] = false;
... count = 0;
... for j in range (0,p) :
... if (admissible [j]) :
... count = count + 1;
... else :
... count = p - 39;
... coefficient = coefficient * (count / p) / (1 - 1 / p)^39;
...
sage: coefficient.n ()
2.22848364649549e27
The change upon doubling the cutoff $10000$ is in the third digit, so the number of such prime constellations up to $N$ is expected to be asymptotically given approximately by $2cdot10^{27}N/log^{39}N$. This is $1$ for $Napprox4cdot10^{54}$, so although there are expected to be infinitely many, you'd probably have quite a bit of searching to do to find one. There are none except the one with $k=41$ up to $k=1000000$:
sage: P = Primes ();
sage: for k in range (0,1000000) :
... success = true;
... for n in range (1,40) :
... if not (n^2 + n + k) in P :
... success = false;
... break;
... if success :
... print k;
41
add a comment |
up vote
9
down vote
If we allow the more general polynomial $an^2+bn+c$, then,
$$P(n) = 9n^2-163,(3n-41)$$
also takes on prime values for ALL $1leq n leq 40$. This can be derived from Euler's polynomial, but has a sequence of $40$ primes that begin and end differently from his.
Very cool. $6683=41cdot163$ ($n=0$) isn't prime, though.
– Jonathan
Jan 29 '13 at 6:36
Oops, sorry. I forgot it starts with $n=1$. Has been corrected. Thanks, Jonathan.
– Tito Piezas III
Jan 29 '13 at 6:46
add a comment |
up vote
5
down vote
Yes, below is the key result.
Theorem $ $ $rm (x!-!alpha):(x!-!alpha') = x^2! + x + k $ is prime for $rm, 0 le x le k!-!2 iff mathbb Z[alpha], $ is a PID
Hint $, (Rightarrow) $ Show all primes $rm p le sqrt{n},; n = 1!-!4k $ satisfy $rm (n/p) = -1 $ so none split/ramify
For proofs, see e.g. Cohn, Advanced Number Theory, pp. 155-156, or Ribenboim, My numbers, my friends, 5.7 p.108. Note that both proofs employ the bound $rm p < sqrt{n} $ without explicitly mentioning that this is a consequence of the Minkowski bound - presumably assuming that is obvious to the reader based upon earlier results. Thus you'll need to read the prior sections on the Minkowski bound. Compare Stewart and Tall, Algebraic number theory and FLT, 3ed, Theorem 10.4 p.176 where the use of the Minkowski bound is mentioned explicitly.
Alternatively, see the self-contained paper [1] which proceeds a bit more simply, employing Dirichlet approximation to obtain a generalization of the Euclidean algorithm (the Dedekind-Rabinowitsch-Hasse criterion for a PID). If memory serves correct, this is close to the approach originally employed by Rabinowitsch when he first published this theorem in 1913.
[1] Daniel Fendel, Prime-Producing Polynomials and Principal Ideal Domains,
Mathematics Magazine, Vol. 58, 4, 1985, 204-210
add a comment |
up vote
4
down vote
See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
add a comment |
up vote
1
down vote
Probably, it's not the last one. I just discovered that some similar formulas, such as n^2 - n + 55661
, actually contain more primes than n^2 - n + 41
, tested with n=1 up to 10^7.
Here are some examples:
41 -> 2208197 primes
55661 -> 2478942 primes
333491 -> 2535780 primes
701147 -> 2587904 primes
Other similar formulas include:
n^2 - n + 361637
n^2 - n + 383681
n^2 - n + 601037
n^2 - n + 206807
$6^2+6+55661$ is divisible by 53.
– MJD
Jul 3 '15 at 21:44
3
The point is, not just more primes, but more consecutive primes. And this was tested up to a million by jorriki.
– Alex
Feb 1 '16 at 20:30
add a comment |
protected by MJD Jul 3 '15 at 21:44
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
42
down vote
accepted
See http://en.wikipedia.org/wiki/Heegner_number#Consecutive_primes
Here is a longer piece Rabinowitz published on the topic below
Rabinowitz showed, in 1913, that $x^2 + x + p$ represent the maximal number of consecutive primes if and only if $x^2 + x y + p y^2$ is the only (equivalence class of) positive binary quadratic form of its discriminant. This condition is called "class number one." For negative discriminants the set of such discriminants is finite, called Heegner numbers.
Note that if we take $x^2 + x + ab$ so that the constant term is composite, we get composite outcome both for $x=a$ and $x=b,$ so the thing quits early. In the terms of Rabinowitz, we would also have the form $a x^2 + x y + b y^2,$ which would be a distinct "class" in the same discriminant, thus violating class number one. So it all fits together. That is, it is "reduced" if $0 < a leq b,$ and distinct from the principal form if also $a > 1.$
For binary forms, I particularly like Buell, here is his page about class number one: BUELL. He does everything in terms of binary forms, but he also gives the relationship with quadratic fields. Furthermore, he allows both positive and indefinite forms, finally he allows odd $b$ in $a x^2 + b x y + c y^2.$ Note that I have often answered MSE questions about ideals in quadratic fields with these techniques, which are, quite simply, easy. Plus he shows the right way to do Pell's equation and variants as algorithms, which people often seem to misunderstand. Here I mean Lagrange's method mostly.
EEDDIITT: I decided to figure out the easier direction of the Rabinowitz result in my own language. So, we begin with the principal form, $langle 1,1,p rangle$ with some prime $p geq 3. $ It follows that $2p-4 geq p-1$ and
$$ p-2 geq frac{p-1}{2}. $$
Now, suppose we have another, distinct, reduced form of the same discriminant,
$$ langle a,b,c rangle. $$ There is no loss of generality in demanding $b > 0.$ So reduced means $$ 1 leq b leq a leq c $$ with $b$ odd, both $a,c geq 2,$ and
$$ 4ac - b^2 = 4 p - 1. $$ As $b^2 leq ac,$ we find $3 b^2 leq 4p-1 $ and, as $p$ is positive,
$ b leq p.$
Now, define $$ b = 2 beta + 1 $$ or $ beta = frac{b-1}{2}. $ From earlier we have
$$ beta leq p-2. $$
However, from $4ac - b^2 = 4p-1$ we get $4ac+1 = b^2 + 4 p,$ then
$ 4ac + 1 = 4 beta^2 + 4 beta + 1 + 4 p, $ then $4ac = 4 beta^2 + 4 beta + 4 p, $ then
$$ ac = beta^2 + beta + p, $$
with $0 leq beta leq p-2.$ That is, the presence of a second equivalence class of forms has forced $x^2 + x + p$ to represent a composite number ($ac$) with a small value $ x = beta leq p-2,$ thereby interrupting the supposed sequence of primes. $bigcirc bigcirc bigcirc bigcirc bigcirc$
EEDDIITTEEDDIITT: I should point out that the discriminants in question must actually be field discriminants, certain things must be squarefree. If I start with $x^2 + x + 7,$ the related $x^2 + x y + 7 y^2$ of discriminant $-27$ is of class number one, but there is the imprimitive form $ langle 3,3,3 rangle $ with the same discriminant. Then, as above, we see that $x^2 + x + 7 = 9$ with $x=1 =(3-1)/2.$
[ Rabinowitz, G. “Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern.” Proc. Fifth Internat. Congress Math. (Cambridge) 1, 418-421, 1913. ]
Edit October 30, 2013. Somebody asked at deleted question
Smallest positive integer $n$ s.t. f(n) = $n^2 + n + 41$ is composite?
about the other direction in Rabinowitz (1913), and a little fiddling revealed that I also know how to do that. We have a positive principal form $$ langle 1,1,p rangle $$ where $$ - Delta = 4 p - 1 $$ is also prime. Otherwise there is a second genus unless $ - Delta = 27 $ or $ - Delta = 343 $ or similar prime power, which is a problem I am going to ignore; our discriminant is minus a prime, $ Delta = 1- 4 p . $
We are interested in the possibility that $n^2 + n + p$ is composite for $0 leq n leq p-2.$ If so, let $q$ be the smallest prime that divides such a composite number. We have $n^2 + n + p equiv 0 pmod q.$ This means $(2n+1)^2 equiv Delta pmod q,$ so we know $Delta$ is a quadratic residue. Next $n^2 + n + p leq (p-1)^2 + 1.$ So, the smallest prime factor is smaller than $p-1,$ and $q < p,$ so $q < - Delta.$
Let's see, the two roots of $n^2 + n + p pmod q$ add up to $q-1.$ One may confirm that if $m = q-1-n,$ then $m^2 + m + p equiv 0 pmod q.$ However, we cannot have $n = (q-1)/2$ with $n^2 + n + p pmod q,$ because that implies $Delta equiv 0 pmod q,$ and we were careful to make $- Delta$ prime, with $q < - Delta.$ Therefore there are two distinct values of $n pmod q,$ the two values add to $q-1.$ As a result, there is a value of $n$ with $n^2 + n + p equiv 0 pmod q$ and $n < frac{q-1}{2}.$
Using the change of variable matrix
$$
left(
begin{array}{cc}
1 & n \
0 & 1
end{array}right)
$$
written on the right, we find that
$$ langle 1,1,p rangle sim langle 1,2n+1,qs rangle $$
where $n^2 + n + p = q s,$ with $2n+1 < q$ and $q leq s.$ As a result, the new form
$$ langle q,2n+1,s rangle $$
is of the same discriminant but is already reduced, and is therefore not equivalent to the principal form. Thus, the class number is larger than one.
Comment: by the rules for comparing $h(Delta)$ and $h(Delta p^2),$ the only prime power that might work is $27,$ and indeed $h(-27) = 1.$ But $h(-243) = 3.$ Theorem 7.4 on pages 117-118 in Buell, Binary Quadratic Forms (1989).
– Will Jagy
Oct 31 '13 at 7:47
add a comment |
up vote
42
down vote
accepted
See http://en.wikipedia.org/wiki/Heegner_number#Consecutive_primes
Here is a longer piece Rabinowitz published on the topic below
Rabinowitz showed, in 1913, that $x^2 + x + p$ represent the maximal number of consecutive primes if and only if $x^2 + x y + p y^2$ is the only (equivalence class of) positive binary quadratic form of its discriminant. This condition is called "class number one." For negative discriminants the set of such discriminants is finite, called Heegner numbers.
Note that if we take $x^2 + x + ab$ so that the constant term is composite, we get composite outcome both for $x=a$ and $x=b,$ so the thing quits early. In the terms of Rabinowitz, we would also have the form $a x^2 + x y + b y^2,$ which would be a distinct "class" in the same discriminant, thus violating class number one. So it all fits together. That is, it is "reduced" if $0 < a leq b,$ and distinct from the principal form if also $a > 1.$
For binary forms, I particularly like Buell, here is his page about class number one: BUELL. He does everything in terms of binary forms, but he also gives the relationship with quadratic fields. Furthermore, he allows both positive and indefinite forms, finally he allows odd $b$ in $a x^2 + b x y + c y^2.$ Note that I have often answered MSE questions about ideals in quadratic fields with these techniques, which are, quite simply, easy. Plus he shows the right way to do Pell's equation and variants as algorithms, which people often seem to misunderstand. Here I mean Lagrange's method mostly.
EEDDIITT: I decided to figure out the easier direction of the Rabinowitz result in my own language. So, we begin with the principal form, $langle 1,1,p rangle$ with some prime $p geq 3. $ It follows that $2p-4 geq p-1$ and
$$ p-2 geq frac{p-1}{2}. $$
Now, suppose we have another, distinct, reduced form of the same discriminant,
$$ langle a,b,c rangle. $$ There is no loss of generality in demanding $b > 0.$ So reduced means $$ 1 leq b leq a leq c $$ with $b$ odd, both $a,c geq 2,$ and
$$ 4ac - b^2 = 4 p - 1. $$ As $b^2 leq ac,$ we find $3 b^2 leq 4p-1 $ and, as $p$ is positive,
$ b leq p.$
Now, define $$ b = 2 beta + 1 $$ or $ beta = frac{b-1}{2}. $ From earlier we have
$$ beta leq p-2. $$
However, from $4ac - b^2 = 4p-1$ we get $4ac+1 = b^2 + 4 p,$ then
$ 4ac + 1 = 4 beta^2 + 4 beta + 1 + 4 p, $ then $4ac = 4 beta^2 + 4 beta + 4 p, $ then
$$ ac = beta^2 + beta + p, $$
with $0 leq beta leq p-2.$ That is, the presence of a second equivalence class of forms has forced $x^2 + x + p$ to represent a composite number ($ac$) with a small value $ x = beta leq p-2,$ thereby interrupting the supposed sequence of primes. $bigcirc bigcirc bigcirc bigcirc bigcirc$
EEDDIITTEEDDIITT: I should point out that the discriminants in question must actually be field discriminants, certain things must be squarefree. If I start with $x^2 + x + 7,$ the related $x^2 + x y + 7 y^2$ of discriminant $-27$ is of class number one, but there is the imprimitive form $ langle 3,3,3 rangle $ with the same discriminant. Then, as above, we see that $x^2 + x + 7 = 9$ with $x=1 =(3-1)/2.$
[ Rabinowitz, G. “Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern.” Proc. Fifth Internat. Congress Math. (Cambridge) 1, 418-421, 1913. ]
Edit October 30, 2013. Somebody asked at deleted question
Smallest positive integer $n$ s.t. f(n) = $n^2 + n + 41$ is composite?
about the other direction in Rabinowitz (1913), and a little fiddling revealed that I also know how to do that. We have a positive principal form $$ langle 1,1,p rangle $$ where $$ - Delta = 4 p - 1 $$ is also prime. Otherwise there is a second genus unless $ - Delta = 27 $ or $ - Delta = 343 $ or similar prime power, which is a problem I am going to ignore; our discriminant is minus a prime, $ Delta = 1- 4 p . $
We are interested in the possibility that $n^2 + n + p$ is composite for $0 leq n leq p-2.$ If so, let $q$ be the smallest prime that divides such a composite number. We have $n^2 + n + p equiv 0 pmod q.$ This means $(2n+1)^2 equiv Delta pmod q,$ so we know $Delta$ is a quadratic residue. Next $n^2 + n + p leq (p-1)^2 + 1.$ So, the smallest prime factor is smaller than $p-1,$ and $q < p,$ so $q < - Delta.$
Let's see, the two roots of $n^2 + n + p pmod q$ add up to $q-1.$ One may confirm that if $m = q-1-n,$ then $m^2 + m + p equiv 0 pmod q.$ However, we cannot have $n = (q-1)/2$ with $n^2 + n + p pmod q,$ because that implies $Delta equiv 0 pmod q,$ and we were careful to make $- Delta$ prime, with $q < - Delta.$ Therefore there are two distinct values of $n pmod q,$ the two values add to $q-1.$ As a result, there is a value of $n$ with $n^2 + n + p equiv 0 pmod q$ and $n < frac{q-1}{2}.$
Using the change of variable matrix
$$
left(
begin{array}{cc}
1 & n \
0 & 1
end{array}right)
$$
written on the right, we find that
$$ langle 1,1,p rangle sim langle 1,2n+1,qs rangle $$
where $n^2 + n + p = q s,$ with $2n+1 < q$ and $q leq s.$ As a result, the new form
$$ langle q,2n+1,s rangle $$
is of the same discriminant but is already reduced, and is therefore not equivalent to the principal form. Thus, the class number is larger than one.
Comment: by the rules for comparing $h(Delta)$ and $h(Delta p^2),$ the only prime power that might work is $27,$ and indeed $h(-27) = 1.$ But $h(-243) = 3.$ Theorem 7.4 on pages 117-118 in Buell, Binary Quadratic Forms (1989).
– Will Jagy
Oct 31 '13 at 7:47
add a comment |
up vote
42
down vote
accepted
up vote
42
down vote
accepted
See http://en.wikipedia.org/wiki/Heegner_number#Consecutive_primes
Here is a longer piece Rabinowitz published on the topic below
Rabinowitz showed, in 1913, that $x^2 + x + p$ represent the maximal number of consecutive primes if and only if $x^2 + x y + p y^2$ is the only (equivalence class of) positive binary quadratic form of its discriminant. This condition is called "class number one." For negative discriminants the set of such discriminants is finite, called Heegner numbers.
Note that if we take $x^2 + x + ab$ so that the constant term is composite, we get composite outcome both for $x=a$ and $x=b,$ so the thing quits early. In the terms of Rabinowitz, we would also have the form $a x^2 + x y + b y^2,$ which would be a distinct "class" in the same discriminant, thus violating class number one. So it all fits together. That is, it is "reduced" if $0 < a leq b,$ and distinct from the principal form if also $a > 1.$
For binary forms, I particularly like Buell, here is his page about class number one: BUELL. He does everything in terms of binary forms, but he also gives the relationship with quadratic fields. Furthermore, he allows both positive and indefinite forms, finally he allows odd $b$ in $a x^2 + b x y + c y^2.$ Note that I have often answered MSE questions about ideals in quadratic fields with these techniques, which are, quite simply, easy. Plus he shows the right way to do Pell's equation and variants as algorithms, which people often seem to misunderstand. Here I mean Lagrange's method mostly.
EEDDIITT: I decided to figure out the easier direction of the Rabinowitz result in my own language. So, we begin with the principal form, $langle 1,1,p rangle$ with some prime $p geq 3. $ It follows that $2p-4 geq p-1$ and
$$ p-2 geq frac{p-1}{2}. $$
Now, suppose we have another, distinct, reduced form of the same discriminant,
$$ langle a,b,c rangle. $$ There is no loss of generality in demanding $b > 0.$ So reduced means $$ 1 leq b leq a leq c $$ with $b$ odd, both $a,c geq 2,$ and
$$ 4ac - b^2 = 4 p - 1. $$ As $b^2 leq ac,$ we find $3 b^2 leq 4p-1 $ and, as $p$ is positive,
$ b leq p.$
Now, define $$ b = 2 beta + 1 $$ or $ beta = frac{b-1}{2}. $ From earlier we have
$$ beta leq p-2. $$
However, from $4ac - b^2 = 4p-1$ we get $4ac+1 = b^2 + 4 p,$ then
$ 4ac + 1 = 4 beta^2 + 4 beta + 1 + 4 p, $ then $4ac = 4 beta^2 + 4 beta + 4 p, $ then
$$ ac = beta^2 + beta + p, $$
with $0 leq beta leq p-2.$ That is, the presence of a second equivalence class of forms has forced $x^2 + x + p$ to represent a composite number ($ac$) with a small value $ x = beta leq p-2,$ thereby interrupting the supposed sequence of primes. $bigcirc bigcirc bigcirc bigcirc bigcirc$
EEDDIITTEEDDIITT: I should point out that the discriminants in question must actually be field discriminants, certain things must be squarefree. If I start with $x^2 + x + 7,$ the related $x^2 + x y + 7 y^2$ of discriminant $-27$ is of class number one, but there is the imprimitive form $ langle 3,3,3 rangle $ with the same discriminant. Then, as above, we see that $x^2 + x + 7 = 9$ with $x=1 =(3-1)/2.$
[ Rabinowitz, G. “Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern.” Proc. Fifth Internat. Congress Math. (Cambridge) 1, 418-421, 1913. ]
Edit October 30, 2013. Somebody asked at deleted question
Smallest positive integer $n$ s.t. f(n) = $n^2 + n + 41$ is composite?
about the other direction in Rabinowitz (1913), and a little fiddling revealed that I also know how to do that. We have a positive principal form $$ langle 1,1,p rangle $$ where $$ - Delta = 4 p - 1 $$ is also prime. Otherwise there is a second genus unless $ - Delta = 27 $ or $ - Delta = 343 $ or similar prime power, which is a problem I am going to ignore; our discriminant is minus a prime, $ Delta = 1- 4 p . $
We are interested in the possibility that $n^2 + n + p$ is composite for $0 leq n leq p-2.$ If so, let $q$ be the smallest prime that divides such a composite number. We have $n^2 + n + p equiv 0 pmod q.$ This means $(2n+1)^2 equiv Delta pmod q,$ so we know $Delta$ is a quadratic residue. Next $n^2 + n + p leq (p-1)^2 + 1.$ So, the smallest prime factor is smaller than $p-1,$ and $q < p,$ so $q < - Delta.$
Let's see, the two roots of $n^2 + n + p pmod q$ add up to $q-1.$ One may confirm that if $m = q-1-n,$ then $m^2 + m + p equiv 0 pmod q.$ However, we cannot have $n = (q-1)/2$ with $n^2 + n + p pmod q,$ because that implies $Delta equiv 0 pmod q,$ and we were careful to make $- Delta$ prime, with $q < - Delta.$ Therefore there are two distinct values of $n pmod q,$ the two values add to $q-1.$ As a result, there is a value of $n$ with $n^2 + n + p equiv 0 pmod q$ and $n < frac{q-1}{2}.$
Using the change of variable matrix
$$
left(
begin{array}{cc}
1 & n \
0 & 1
end{array}right)
$$
written on the right, we find that
$$ langle 1,1,p rangle sim langle 1,2n+1,qs rangle $$
where $n^2 + n + p = q s,$ with $2n+1 < q$ and $q leq s.$ As a result, the new form
$$ langle q,2n+1,s rangle $$
is of the same discriminant but is already reduced, and is therefore not equivalent to the principal form. Thus, the class number is larger than one.
See http://en.wikipedia.org/wiki/Heegner_number#Consecutive_primes
Here is a longer piece Rabinowitz published on the topic below
Rabinowitz showed, in 1913, that $x^2 + x + p$ represent the maximal number of consecutive primes if and only if $x^2 + x y + p y^2$ is the only (equivalence class of) positive binary quadratic form of its discriminant. This condition is called "class number one." For negative discriminants the set of such discriminants is finite, called Heegner numbers.
Note that if we take $x^2 + x + ab$ so that the constant term is composite, we get composite outcome both for $x=a$ and $x=b,$ so the thing quits early. In the terms of Rabinowitz, we would also have the form $a x^2 + x y + b y^2,$ which would be a distinct "class" in the same discriminant, thus violating class number one. So it all fits together. That is, it is "reduced" if $0 < a leq b,$ and distinct from the principal form if also $a > 1.$
For binary forms, I particularly like Buell, here is his page about class number one: BUELL. He does everything in terms of binary forms, but he also gives the relationship with quadratic fields. Furthermore, he allows both positive and indefinite forms, finally he allows odd $b$ in $a x^2 + b x y + c y^2.$ Note that I have often answered MSE questions about ideals in quadratic fields with these techniques, which are, quite simply, easy. Plus he shows the right way to do Pell's equation and variants as algorithms, which people often seem to misunderstand. Here I mean Lagrange's method mostly.
EEDDIITT: I decided to figure out the easier direction of the Rabinowitz result in my own language. So, we begin with the principal form, $langle 1,1,p rangle$ with some prime $p geq 3. $ It follows that $2p-4 geq p-1$ and
$$ p-2 geq frac{p-1}{2}. $$
Now, suppose we have another, distinct, reduced form of the same discriminant,
$$ langle a,b,c rangle. $$ There is no loss of generality in demanding $b > 0.$ So reduced means $$ 1 leq b leq a leq c $$ with $b$ odd, both $a,c geq 2,$ and
$$ 4ac - b^2 = 4 p - 1. $$ As $b^2 leq ac,$ we find $3 b^2 leq 4p-1 $ and, as $p$ is positive,
$ b leq p.$
Now, define $$ b = 2 beta + 1 $$ or $ beta = frac{b-1}{2}. $ From earlier we have
$$ beta leq p-2. $$
However, from $4ac - b^2 = 4p-1$ we get $4ac+1 = b^2 + 4 p,$ then
$ 4ac + 1 = 4 beta^2 + 4 beta + 1 + 4 p, $ then $4ac = 4 beta^2 + 4 beta + 4 p, $ then
$$ ac = beta^2 + beta + p, $$
with $0 leq beta leq p-2.$ That is, the presence of a second equivalence class of forms has forced $x^2 + x + p$ to represent a composite number ($ac$) with a small value $ x = beta leq p-2,$ thereby interrupting the supposed sequence of primes. $bigcirc bigcirc bigcirc bigcirc bigcirc$
EEDDIITTEEDDIITT: I should point out that the discriminants in question must actually be field discriminants, certain things must be squarefree. If I start with $x^2 + x + 7,$ the related $x^2 + x y + 7 y^2$ of discriminant $-27$ is of class number one, but there is the imprimitive form $ langle 3,3,3 rangle $ with the same discriminant. Then, as above, we see that $x^2 + x + 7 = 9$ with $x=1 =(3-1)/2.$
[ Rabinowitz, G. “Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern.” Proc. Fifth Internat. Congress Math. (Cambridge) 1, 418-421, 1913. ]
Edit October 30, 2013. Somebody asked at deleted question
Smallest positive integer $n$ s.t. f(n) = $n^2 + n + 41$ is composite?
about the other direction in Rabinowitz (1913), and a little fiddling revealed that I also know how to do that. We have a positive principal form $$ langle 1,1,p rangle $$ where $$ - Delta = 4 p - 1 $$ is also prime. Otherwise there is a second genus unless $ - Delta = 27 $ or $ - Delta = 343 $ or similar prime power, which is a problem I am going to ignore; our discriminant is minus a prime, $ Delta = 1- 4 p . $
We are interested in the possibility that $n^2 + n + p$ is composite for $0 leq n leq p-2.$ If so, let $q$ be the smallest prime that divides such a composite number. We have $n^2 + n + p equiv 0 pmod q.$ This means $(2n+1)^2 equiv Delta pmod q,$ so we know $Delta$ is a quadratic residue. Next $n^2 + n + p leq (p-1)^2 + 1.$ So, the smallest prime factor is smaller than $p-1,$ and $q < p,$ so $q < - Delta.$
Let's see, the two roots of $n^2 + n + p pmod q$ add up to $q-1.$ One may confirm that if $m = q-1-n,$ then $m^2 + m + p equiv 0 pmod q.$ However, we cannot have $n = (q-1)/2$ with $n^2 + n + p pmod q,$ because that implies $Delta equiv 0 pmod q,$ and we were careful to make $- Delta$ prime, with $q < - Delta.$ Therefore there are two distinct values of $n pmod q,$ the two values add to $q-1.$ As a result, there is a value of $n$ with $n^2 + n + p equiv 0 pmod q$ and $n < frac{q-1}{2}.$
Using the change of variable matrix
$$
left(
begin{array}{cc}
1 & n \
0 & 1
end{array}right)
$$
written on the right, we find that
$$ langle 1,1,p rangle sim langle 1,2n+1,qs rangle $$
where $n^2 + n + p = q s,$ with $2n+1 < q$ and $q leq s.$ As a result, the new form
$$ langle q,2n+1,s rangle $$
is of the same discriminant but is already reduced, and is therefore not equivalent to the principal form. Thus, the class number is larger than one.
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Jan 28 '13 at 23:29
Will Jagy
101k598198
101k598198
Comment: by the rules for comparing $h(Delta)$ and $h(Delta p^2),$ the only prime power that might work is $27,$ and indeed $h(-27) = 1.$ But $h(-243) = 3.$ Theorem 7.4 on pages 117-118 in Buell, Binary Quadratic Forms (1989).
– Will Jagy
Oct 31 '13 at 7:47
add a comment |
Comment: by the rules for comparing $h(Delta)$ and $h(Delta p^2),$ the only prime power that might work is $27,$ and indeed $h(-27) = 1.$ But $h(-243) = 3.$ Theorem 7.4 on pages 117-118 in Buell, Binary Quadratic Forms (1989).
– Will Jagy
Oct 31 '13 at 7:47
Comment: by the rules for comparing $h(Delta)$ and $h(Delta p^2),$ the only prime power that might work is $27,$ and indeed $h(-27) = 1.$ But $h(-243) = 3.$ Theorem 7.4 on pages 117-118 in Buell, Binary Quadratic Forms (1989).
– Will Jagy
Oct 31 '13 at 7:47
Comment: by the rules for comparing $h(Delta)$ and $h(Delta p^2),$ the only prime power that might work is $27,$ and indeed $h(-27) = 1.$ But $h(-243) = 3.$ Theorem 7.4 on pages 117-118 in Buell, Binary Quadratic Forms (1989).
– Will Jagy
Oct 31 '13 at 7:47
add a comment |
up vote
12
down vote
To answer the second part of your question: The requirement that $n^2+n+k$ be prime for $0lt nlt40$ defines a prime constellation. The first Hardy–Littlewood conjecture, which is widely believed to be likely to hold, states that the asymptotic density of prime constellations is correctly predicted by a probabilistic model based on independently uniformly distributed residues with respect to all primes. Here's a Sage session that calculates the coefficient for your prime constellation:
sage: P = Primes ();
sage: coefficient = 1;
sage: for i in range (0,10000) :
... p = P.unrank (i);
... if (p < 39^2 + 39) :
... admissible = list (true for j in range (0,p));
... for n in range (1,40) :
... admissible [(n^2+n) % p] = false;
... count = 0;
... for j in range (0,p) :
... if (admissible [j]) :
... count = count + 1;
... else :
... count = p - 39;
... coefficient = coefficient * (count / p) / (1 - 1 / p)^39;
...
sage: coefficient.n ()
2.22848364649549e27
The change upon doubling the cutoff $10000$ is in the third digit, so the number of such prime constellations up to $N$ is expected to be asymptotically given approximately by $2cdot10^{27}N/log^{39}N$. This is $1$ for $Napprox4cdot10^{54}$, so although there are expected to be infinitely many, you'd probably have quite a bit of searching to do to find one. There are none except the one with $k=41$ up to $k=1000000$:
sage: P = Primes ();
sage: for k in range (0,1000000) :
... success = true;
... for n in range (1,40) :
... if not (n^2 + n + k) in P :
... success = false;
... break;
... if success :
... print k;
41
add a comment |
up vote
12
down vote
To answer the second part of your question: The requirement that $n^2+n+k$ be prime for $0lt nlt40$ defines a prime constellation. The first Hardy–Littlewood conjecture, which is widely believed to be likely to hold, states that the asymptotic density of prime constellations is correctly predicted by a probabilistic model based on independently uniformly distributed residues with respect to all primes. Here's a Sage session that calculates the coefficient for your prime constellation:
sage: P = Primes ();
sage: coefficient = 1;
sage: for i in range (0,10000) :
... p = P.unrank (i);
... if (p < 39^2 + 39) :
... admissible = list (true for j in range (0,p));
... for n in range (1,40) :
... admissible [(n^2+n) % p] = false;
... count = 0;
... for j in range (0,p) :
... if (admissible [j]) :
... count = count + 1;
... else :
... count = p - 39;
... coefficient = coefficient * (count / p) / (1 - 1 / p)^39;
...
sage: coefficient.n ()
2.22848364649549e27
The change upon doubling the cutoff $10000$ is in the third digit, so the number of such prime constellations up to $N$ is expected to be asymptotically given approximately by $2cdot10^{27}N/log^{39}N$. This is $1$ for $Napprox4cdot10^{54}$, so although there are expected to be infinitely many, you'd probably have quite a bit of searching to do to find one. There are none except the one with $k=41$ up to $k=1000000$:
sage: P = Primes ();
sage: for k in range (0,1000000) :
... success = true;
... for n in range (1,40) :
... if not (n^2 + n + k) in P :
... success = false;
... break;
... if success :
... print k;
41
add a comment |
up vote
12
down vote
up vote
12
down vote
To answer the second part of your question: The requirement that $n^2+n+k$ be prime for $0lt nlt40$ defines a prime constellation. The first Hardy–Littlewood conjecture, which is widely believed to be likely to hold, states that the asymptotic density of prime constellations is correctly predicted by a probabilistic model based on independently uniformly distributed residues with respect to all primes. Here's a Sage session that calculates the coefficient for your prime constellation:
sage: P = Primes ();
sage: coefficient = 1;
sage: for i in range (0,10000) :
... p = P.unrank (i);
... if (p < 39^2 + 39) :
... admissible = list (true for j in range (0,p));
... for n in range (1,40) :
... admissible [(n^2+n) % p] = false;
... count = 0;
... for j in range (0,p) :
... if (admissible [j]) :
... count = count + 1;
... else :
... count = p - 39;
... coefficient = coefficient * (count / p) / (1 - 1 / p)^39;
...
sage: coefficient.n ()
2.22848364649549e27
The change upon doubling the cutoff $10000$ is in the third digit, so the number of such prime constellations up to $N$ is expected to be asymptotically given approximately by $2cdot10^{27}N/log^{39}N$. This is $1$ for $Napprox4cdot10^{54}$, so although there are expected to be infinitely many, you'd probably have quite a bit of searching to do to find one. There are none except the one with $k=41$ up to $k=1000000$:
sage: P = Primes ();
sage: for k in range (0,1000000) :
... success = true;
... for n in range (1,40) :
... if not (n^2 + n + k) in P :
... success = false;
... break;
... if success :
... print k;
41
To answer the second part of your question: The requirement that $n^2+n+k$ be prime for $0lt nlt40$ defines a prime constellation. The first Hardy–Littlewood conjecture, which is widely believed to be likely to hold, states that the asymptotic density of prime constellations is correctly predicted by a probabilistic model based on independently uniformly distributed residues with respect to all primes. Here's a Sage session that calculates the coefficient for your prime constellation:
sage: P = Primes ();
sage: coefficient = 1;
sage: for i in range (0,10000) :
... p = P.unrank (i);
... if (p < 39^2 + 39) :
... admissible = list (true for j in range (0,p));
... for n in range (1,40) :
... admissible [(n^2+n) % p] = false;
... count = 0;
... for j in range (0,p) :
... if (admissible [j]) :
... count = count + 1;
... else :
... count = p - 39;
... coefficient = coefficient * (count / p) / (1 - 1 / p)^39;
...
sage: coefficient.n ()
2.22848364649549e27
The change upon doubling the cutoff $10000$ is in the third digit, so the number of such prime constellations up to $N$ is expected to be asymptotically given approximately by $2cdot10^{27}N/log^{39}N$. This is $1$ for $Napprox4cdot10^{54}$, so although there are expected to be infinitely many, you'd probably have quite a bit of searching to do to find one. There are none except the one with $k=41$ up to $k=1000000$:
sage: P = Primes ();
sage: for k in range (0,1000000) :
... success = true;
... for n in range (1,40) :
... if not (n^2 + n + k) in P :
... success = false;
... break;
... if success :
... print k;
41
edited Jan 29 '13 at 16:28
answered Jan 29 '13 at 1:40
joriki
170k10183342
170k10183342
add a comment |
add a comment |
up vote
9
down vote
If we allow the more general polynomial $an^2+bn+c$, then,
$$P(n) = 9n^2-163,(3n-41)$$
also takes on prime values for ALL $1leq n leq 40$. This can be derived from Euler's polynomial, but has a sequence of $40$ primes that begin and end differently from his.
Very cool. $6683=41cdot163$ ($n=0$) isn't prime, though.
– Jonathan
Jan 29 '13 at 6:36
Oops, sorry. I forgot it starts with $n=1$. Has been corrected. Thanks, Jonathan.
– Tito Piezas III
Jan 29 '13 at 6:46
add a comment |
up vote
9
down vote
If we allow the more general polynomial $an^2+bn+c$, then,
$$P(n) = 9n^2-163,(3n-41)$$
also takes on prime values for ALL $1leq n leq 40$. This can be derived from Euler's polynomial, but has a sequence of $40$ primes that begin and end differently from his.
Very cool. $6683=41cdot163$ ($n=0$) isn't prime, though.
– Jonathan
Jan 29 '13 at 6:36
Oops, sorry. I forgot it starts with $n=1$. Has been corrected. Thanks, Jonathan.
– Tito Piezas III
Jan 29 '13 at 6:46
add a comment |
up vote
9
down vote
up vote
9
down vote
If we allow the more general polynomial $an^2+bn+c$, then,
$$P(n) = 9n^2-163,(3n-41)$$
also takes on prime values for ALL $1leq n leq 40$. This can be derived from Euler's polynomial, but has a sequence of $40$ primes that begin and end differently from his.
If we allow the more general polynomial $an^2+bn+c$, then,
$$P(n) = 9n^2-163,(3n-41)$$
also takes on prime values for ALL $1leq n leq 40$. This can be derived from Euler's polynomial, but has a sequence of $40$ primes that begin and end differently from his.
edited Nov 29 at 3:20
answered Jan 29 '13 at 2:40
Tito Piezas III
26.7k364169
26.7k364169
Very cool. $6683=41cdot163$ ($n=0$) isn't prime, though.
– Jonathan
Jan 29 '13 at 6:36
Oops, sorry. I forgot it starts with $n=1$. Has been corrected. Thanks, Jonathan.
– Tito Piezas III
Jan 29 '13 at 6:46
add a comment |
Very cool. $6683=41cdot163$ ($n=0$) isn't prime, though.
– Jonathan
Jan 29 '13 at 6:36
Oops, sorry. I forgot it starts with $n=1$. Has been corrected. Thanks, Jonathan.
– Tito Piezas III
Jan 29 '13 at 6:46
Very cool. $6683=41cdot163$ ($n=0$) isn't prime, though.
– Jonathan
Jan 29 '13 at 6:36
Very cool. $6683=41cdot163$ ($n=0$) isn't prime, though.
– Jonathan
Jan 29 '13 at 6:36
Oops, sorry. I forgot it starts with $n=1$. Has been corrected. Thanks, Jonathan.
– Tito Piezas III
Jan 29 '13 at 6:46
Oops, sorry. I forgot it starts with $n=1$. Has been corrected. Thanks, Jonathan.
– Tito Piezas III
Jan 29 '13 at 6:46
add a comment |
up vote
5
down vote
Yes, below is the key result.
Theorem $ $ $rm (x!-!alpha):(x!-!alpha') = x^2! + x + k $ is prime for $rm, 0 le x le k!-!2 iff mathbb Z[alpha], $ is a PID
Hint $, (Rightarrow) $ Show all primes $rm p le sqrt{n},; n = 1!-!4k $ satisfy $rm (n/p) = -1 $ so none split/ramify
For proofs, see e.g. Cohn, Advanced Number Theory, pp. 155-156, or Ribenboim, My numbers, my friends, 5.7 p.108. Note that both proofs employ the bound $rm p < sqrt{n} $ without explicitly mentioning that this is a consequence of the Minkowski bound - presumably assuming that is obvious to the reader based upon earlier results. Thus you'll need to read the prior sections on the Minkowski bound. Compare Stewart and Tall, Algebraic number theory and FLT, 3ed, Theorem 10.4 p.176 where the use of the Minkowski bound is mentioned explicitly.
Alternatively, see the self-contained paper [1] which proceeds a bit more simply, employing Dirichlet approximation to obtain a generalization of the Euclidean algorithm (the Dedekind-Rabinowitsch-Hasse criterion for a PID). If memory serves correct, this is close to the approach originally employed by Rabinowitsch when he first published this theorem in 1913.
[1] Daniel Fendel, Prime-Producing Polynomials and Principal Ideal Domains,
Mathematics Magazine, Vol. 58, 4, 1985, 204-210
add a comment |
up vote
5
down vote
Yes, below is the key result.
Theorem $ $ $rm (x!-!alpha):(x!-!alpha') = x^2! + x + k $ is prime for $rm, 0 le x le k!-!2 iff mathbb Z[alpha], $ is a PID
Hint $, (Rightarrow) $ Show all primes $rm p le sqrt{n},; n = 1!-!4k $ satisfy $rm (n/p) = -1 $ so none split/ramify
For proofs, see e.g. Cohn, Advanced Number Theory, pp. 155-156, or Ribenboim, My numbers, my friends, 5.7 p.108. Note that both proofs employ the bound $rm p < sqrt{n} $ without explicitly mentioning that this is a consequence of the Minkowski bound - presumably assuming that is obvious to the reader based upon earlier results. Thus you'll need to read the prior sections on the Minkowski bound. Compare Stewart and Tall, Algebraic number theory and FLT, 3ed, Theorem 10.4 p.176 where the use of the Minkowski bound is mentioned explicitly.
Alternatively, see the self-contained paper [1] which proceeds a bit more simply, employing Dirichlet approximation to obtain a generalization of the Euclidean algorithm (the Dedekind-Rabinowitsch-Hasse criterion for a PID). If memory serves correct, this is close to the approach originally employed by Rabinowitsch when he first published this theorem in 1913.
[1] Daniel Fendel, Prime-Producing Polynomials and Principal Ideal Domains,
Mathematics Magazine, Vol. 58, 4, 1985, 204-210
add a comment |
up vote
5
down vote
up vote
5
down vote
Yes, below is the key result.
Theorem $ $ $rm (x!-!alpha):(x!-!alpha') = x^2! + x + k $ is prime for $rm, 0 le x le k!-!2 iff mathbb Z[alpha], $ is a PID
Hint $, (Rightarrow) $ Show all primes $rm p le sqrt{n},; n = 1!-!4k $ satisfy $rm (n/p) = -1 $ so none split/ramify
For proofs, see e.g. Cohn, Advanced Number Theory, pp. 155-156, or Ribenboim, My numbers, my friends, 5.7 p.108. Note that both proofs employ the bound $rm p < sqrt{n} $ without explicitly mentioning that this is a consequence of the Minkowski bound - presumably assuming that is obvious to the reader based upon earlier results. Thus you'll need to read the prior sections on the Minkowski bound. Compare Stewart and Tall, Algebraic number theory and FLT, 3ed, Theorem 10.4 p.176 where the use of the Minkowski bound is mentioned explicitly.
Alternatively, see the self-contained paper [1] which proceeds a bit more simply, employing Dirichlet approximation to obtain a generalization of the Euclidean algorithm (the Dedekind-Rabinowitsch-Hasse criterion for a PID). If memory serves correct, this is close to the approach originally employed by Rabinowitsch when he first published this theorem in 1913.
[1] Daniel Fendel, Prime-Producing Polynomials and Principal Ideal Domains,
Mathematics Magazine, Vol. 58, 4, 1985, 204-210
Yes, below is the key result.
Theorem $ $ $rm (x!-!alpha):(x!-!alpha') = x^2! + x + k $ is prime for $rm, 0 le x le k!-!2 iff mathbb Z[alpha], $ is a PID
Hint $, (Rightarrow) $ Show all primes $rm p le sqrt{n},; n = 1!-!4k $ satisfy $rm (n/p) = -1 $ so none split/ramify
For proofs, see e.g. Cohn, Advanced Number Theory, pp. 155-156, or Ribenboim, My numbers, my friends, 5.7 p.108. Note that both proofs employ the bound $rm p < sqrt{n} $ without explicitly mentioning that this is a consequence of the Minkowski bound - presumably assuming that is obvious to the reader based upon earlier results. Thus you'll need to read the prior sections on the Minkowski bound. Compare Stewart and Tall, Algebraic number theory and FLT, 3ed, Theorem 10.4 p.176 where the use of the Minkowski bound is mentioned explicitly.
Alternatively, see the self-contained paper [1] which proceeds a bit more simply, employing Dirichlet approximation to obtain a generalization of the Euclidean algorithm (the Dedekind-Rabinowitsch-Hasse criterion for a PID). If memory serves correct, this is close to the approach originally employed by Rabinowitsch when he first published this theorem in 1913.
[1] Daniel Fendel, Prime-Producing Polynomials and Principal Ideal Domains,
Mathematics Magazine, Vol. 58, 4, 1985, 204-210
edited Jun 27 '16 at 14:00
answered Jul 12 '14 at 19:40
Bill Dubuque
208k29189625
208k29189625
add a comment |
add a comment |
up vote
4
down vote
See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
add a comment |
up vote
4
down vote
See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
add a comment |
up vote
4
down vote
up vote
4
down vote
See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
answered Jan 29 '13 at 0:18
Robert Israel
317k23206457
317k23206457
add a comment |
add a comment |
up vote
1
down vote
Probably, it's not the last one. I just discovered that some similar formulas, such as n^2 - n + 55661
, actually contain more primes than n^2 - n + 41
, tested with n=1 up to 10^7.
Here are some examples:
41 -> 2208197 primes
55661 -> 2478942 primes
333491 -> 2535780 primes
701147 -> 2587904 primes
Other similar formulas include:
n^2 - n + 361637
n^2 - n + 383681
n^2 - n + 601037
n^2 - n + 206807
$6^2+6+55661$ is divisible by 53.
– MJD
Jul 3 '15 at 21:44
3
The point is, not just more primes, but more consecutive primes. And this was tested up to a million by jorriki.
– Alex
Feb 1 '16 at 20:30
add a comment |
up vote
1
down vote
Probably, it's not the last one. I just discovered that some similar formulas, such as n^2 - n + 55661
, actually contain more primes than n^2 - n + 41
, tested with n=1 up to 10^7.
Here are some examples:
41 -> 2208197 primes
55661 -> 2478942 primes
333491 -> 2535780 primes
701147 -> 2587904 primes
Other similar formulas include:
n^2 - n + 361637
n^2 - n + 383681
n^2 - n + 601037
n^2 - n + 206807
$6^2+6+55661$ is divisible by 53.
– MJD
Jul 3 '15 at 21:44
3
The point is, not just more primes, but more consecutive primes. And this was tested up to a million by jorriki.
– Alex
Feb 1 '16 at 20:30
add a comment |
up vote
1
down vote
up vote
1
down vote
Probably, it's not the last one. I just discovered that some similar formulas, such as n^2 - n + 55661
, actually contain more primes than n^2 - n + 41
, tested with n=1 up to 10^7.
Here are some examples:
41 -> 2208197 primes
55661 -> 2478942 primes
333491 -> 2535780 primes
701147 -> 2587904 primes
Other similar formulas include:
n^2 - n + 361637
n^2 - n + 383681
n^2 - n + 601037
n^2 - n + 206807
Probably, it's not the last one. I just discovered that some similar formulas, such as n^2 - n + 55661
, actually contain more primes than n^2 - n + 41
, tested with n=1 up to 10^7.
Here are some examples:
41 -> 2208197 primes
55661 -> 2478942 primes
333491 -> 2535780 primes
701147 -> 2587904 primes
Other similar formulas include:
n^2 - n + 361637
n^2 - n + 383681
n^2 - n + 601037
n^2 - n + 206807
edited Jul 3 '15 at 19:08
answered Jul 3 '15 at 18:50
Trizen
114
114
$6^2+6+55661$ is divisible by 53.
– MJD
Jul 3 '15 at 21:44
3
The point is, not just more primes, but more consecutive primes. And this was tested up to a million by jorriki.
– Alex
Feb 1 '16 at 20:30
add a comment |
$6^2+6+55661$ is divisible by 53.
– MJD
Jul 3 '15 at 21:44
3
The point is, not just more primes, but more consecutive primes. And this was tested up to a million by jorriki.
– Alex
Feb 1 '16 at 20:30
$6^2+6+55661$ is divisible by 53.
– MJD
Jul 3 '15 at 21:44
$6^2+6+55661$ is divisible by 53.
– MJD
Jul 3 '15 at 21:44
3
3
The point is, not just more primes, but more consecutive primes. And this was tested up to a million by jorriki.
– Alex
Feb 1 '16 at 20:30
The point is, not just more primes, but more consecutive primes. And this was tested up to a million by jorriki.
– Alex
Feb 1 '16 at 20:30
add a comment |
protected by MJD Jul 3 '15 at 21:44
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
7
It is certainly last one. See if I can find references. It is the discriminant of $x^2 + x y + 41 y^2$ that is the important thing here.
– Will Jagy
Jan 28 '13 at 23:15
4
Problem 6 of the 28th IMO (Cuba) was: Let $n$ be an integer greater than or equal to $2$. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n/3$, then $k^2 + k + n$ is prime for all integers $k$ such that $0le kle n − 2$. Too bad that $n=41$ is the largest one for which this holds.
– Andrés E. Caicedo
Jan 28 '13 at 23:23
1
Frequently cited in this connection is: "Quadratic polynomials producing consecutive, distinct primes and class groups of complex quadratic fields" by R. A. Mollin. Acta Arithmetica 74 #1 (1996) matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7412.pdf
– MJD
Jan 29 '13 at 0:04
I edited in an elementary proof that class number larger than one (for binary form $x^2 + xy + p y^2$) implies that $x^2 + x + p$ represents a composite number with small $x.$
– Will Jagy
Jan 29 '13 at 5:51
2
n² + 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79, but it is trivially related to the euler one.
– wim
Jan 29 '13 at 7:51