This thread explores some useful and fun statistical estimation one can do with respect to the number sequences described in post #19 and several followon posts
in this thread (which started on an entirely different topic, meandered thither and yon and has since devolved into silliness). Rather than immediately trotting out hifalutin maths such as class numbers, I thought it might be useful  especially to our nonexpert but interested readers  to see what one can deduce (or deem as probable) using just the most basic tools of number theory, nothing more involved than the prime number theorem (PNT).
Quote:
Originally Posted by R. Gerbicz
Quote:
Originally Posted by davar55
Regarding your example, expanding the polynomial x^2 + x + 41.
Is there any way to PROOVE this is prime for
all integers x between 0 and 39 inclusive,
without actually testing or enumerating the range?

Good question, it was an olympiad problem in 1987, see: http://www.artofproblemsolving.com/w...lems/Problem_6
So if we know that the above f(x)=x^2+x+41 is prime for f(0),f(1),f(2),f(3) then we know that it is also prime for f(4),..,f(39).
As I can remember there is a proof that there is only a finitely many such n value for that we can apply the statement, and we know all of them.

Didn't follow the link (yet), because for problems like this I first prefer to see if I can find a simple solution, i.e. of the 'could a bright 6th grader quickly grasp this?' variety. So, consider quadratic polys n^2 + n + p, n natural and p an odd prime (for obvious reasons). Observe:
[1] The smallest such offset, for n = 1, is 2, thus p must be the smaller of a twinprime pair for f(n;p) to be prime for n = 1;
[2] Starting from n = 0 we are adding n*(n+1) to p, thus as long as neither n nor n+1 has p as a factor, then either f(n;p) is prime, or it is a composite with no factors in common with those of n, n+1 or p;
[3] Thus the maximal primesequence length is p1 (n = 0 through p2), since for n = p1, n+1 = p and thus p divides f(n).
Let's consider the possible values of p < 1000 satisfying [1] (we include p = 2, which satisfies the length = p1 condition all by istelf) and examine the resulting primesequence lengths, with asterisks indicating maximallength ones:
p #prime
 
2 1*
3 2*
5 4*
11 10*
17 16*
29 2
41 40*
59 2
71 2
101 4
107 3
137 2
149 2
179 2
191 3
197 2
227 4
269 2
281 2
311 3
347 5
419 2
431 2
461 3
521 2
569 2
599 2
617 2
641 5
659 2
809 2
821 3
827 2
857 3
881 3
Notes:
o The smallest p for which we get less than a maximallength prime sequence is p = 29, for which f(n=2) = 35 = 5*7.
(In fact that is the minimallength prime sequence which is possible under our constructionstartingwithtwinprimepair.)
o We see that maximallength prime sequences are the rule rather than the exception for small p. But after one last hurrah (Euler's p = 41), there are no more maximallength sequences for p < 1000, and the average primesequence length plunges, especially relative to p.
o Looking at the numbers it certainly appears that the odds of a maximallength sequence falls off a cliff for p > 41. But it does not automatically follow that the number of such is finite. However, consider the 'double whammy' (the 2nd part of which is by far the dominant one) of decaying statistical probabilities at work as p increases:
[a] The primes thin out (albeit slowly, as embodied in the PNT), meaning that the odds of each number along the 'lucky string' being prime drops;
[b] Intuitively, for such a 'lucky sequence' to occur, we need not only for p and p+2 to be a twinprime pair, but in fact we need to 'land on' a whole string of primes offset from each other by 2,4,6,8,10,...,2*(p1). And the length of this string increases linearly with p, meaning the odds of hitting such intuitively drop off much faster than (say) the odds of finding a twin pair as p gets larger. Rather we must find first a twin pair, whose larger term is the smaller of a 4offset pair (a socalled
cousinprime pair), whose larger term is the smaller of a 6offset pair, all the way through the terminating 2*(p1)  offset pair, thus the probability for the whole shebang is the product of O(p) individual probabilities each of which decays as p > oo in similar fashion as the odds of finding the twinprime pair which opens the sequence.
Whether there are infinitely many twinprime pairs is of course one of the great open problems in number theory  it is generally believed that there are  but irrespective of this, we do know that they thin out asymptotically faster than the primes:
Brun's famous theorem (100 years old this year, though the first proof didn't come until 1919) proved that the sum of reciprocals of twin primes is finite. As the wikipedia page on twin primes adds, whereas the primes thin out as the inverse of (log N), the twins thin out as the inverse *square* of (log N), which reflects the conditional pairedevent probability "N odd prime and (N + [fixed even offset]) also prime":
"The modern version of Brun's argument can be used to show that the number of twin primes less than N does not exceed
C*N / (log N)^2
for some absolute constant C > 0."
Generalizing to the analogous the odds of a maximallength 'lucky sequence' starting with prime N decay as the inverse of (log N)^N, i.e. decay faster than any finite inverse power of the logarithm.
We can easily prove convergence of the resulting sum (looping over integers from 2 upward) by noting that as soon as N is large enough that log N >= 2, each remaining term can be bounded above by 1/2^N, i.e. by the term of a sequence with knownconvergent sum. As far as the actual limit, a simple Pari loop shows the sum converges to a limiting value of ~3.2426..., as follows:
~ 4 decimal digits after 10 terms;
~10 decimal digits after 20 terms;
~16 decimal digits after 30 terms;
~23 decimal digits after 40 terms;
~30 decimal digits after 50 terms.
As the
Mathworld entry (which somewhat oddly gives the Euler poly as n^2  n + p, which is equivalent to n^2 + n + p modulo a unit increment in n, i.e. the minussign version produces distinct primes for n = 1,...,p1) linked by R. Gerbicz in post #34 of the above thread notes, it has indeed been proven that not only are there finitely many such p, but that Euler's p = 41 is the largest prime yielding a maximallength sequence.
The above 3andchange estimate is in the same ballpark as the 6 'lucky numbers' (2,3,5,11,17,41) found in practice; moreover we have not considered what the constant of proportionality in our O(1/(log N)^N) estimate may be. If we note that Brun's constant for the twinprimeassociated sum is just a little less than 2, and crudehandwavingly assume a similar constant for the generalized sequence, we get something quite close to the 6 lucky numbers which actually exist.