Is the notorious $n^2 + n + 41$ prime generator the last of its type?











up vote
72
down vote

favorite
32












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$?










share|cite|improve this question




















  • 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

















up vote
72
down vote

favorite
32












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$?










share|cite|improve this question




















  • 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















up vote
72
down vote

favorite
32









up vote
72
down vote

favorite
32






32





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$?










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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
















  • 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












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.






share|cite|improve this answer























  • 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


















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





share|cite|improve this answer






























    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.






    share|cite|improve this answer























    • 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




















    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






    share|cite|improve this answer






























      up vote
      4
      down vote













      See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html






      share|cite|improve this answer




























        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





        share|cite|improve this answer























        • $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










        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.






        share|cite|improve this answer























        • 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















        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.






        share|cite|improve this answer























        • 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













        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.






        share|cite|improve this answer














        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.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        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


















        • 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










        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





        share|cite|improve this answer



























          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





          share|cite|improve this answer

























            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





            share|cite|improve this answer














            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






            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Jan 29 '13 at 16:28

























            answered Jan 29 '13 at 1:40









            joriki

            170k10183342




            170k10183342






















                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.






                share|cite|improve this answer























                • 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

















                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.






                share|cite|improve this answer























                • 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















                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.






                share|cite|improve this answer














                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.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                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




















                • 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












                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






                share|cite|improve this answer



























                  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






                  share|cite|improve this answer

























                    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






                    share|cite|improve this answer














                    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







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited Jun 27 '16 at 14:00

























                    answered Jul 12 '14 at 19:40









                    Bill Dubuque

                    208k29189625




                    208k29189625






















                        up vote
                        4
                        down vote













                        See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html






                        share|cite|improve this answer

























                          up vote
                          4
                          down vote













                          See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html






                          share|cite|improve this answer























                            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






                            share|cite|improve this answer












                            See also the Mathworld page "Prime-Generating Polynomial" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered Jan 29 '13 at 0:18









                            Robert Israel

                            317k23206457




                            317k23206457






















                                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





                                share|cite|improve this answer























                                • $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















                                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





                                share|cite|improve this answer























                                • $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













                                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





                                share|cite|improve this answer














                                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






                                share|cite|improve this answer














                                share|cite|improve this answer



                                share|cite|improve this answer








                                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


















                                • $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





                                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?



                                Popular posts from this blog

                                Berounka

                                Fiat S.p.A.

                                Type 'String' is not a subtype of type 'int' of 'index'