View Single Post
2015-10-18, 01:37   #1
ewmayer
2ω=0

Sep 2002
República de California

1157110 Posts
Fun with the Lucky Numbers of Euler

This thread explores some useful and fun statistical estimation one can do with respect to the number sequences described in post #19 and several follow-on 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 non-expert 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 twin-prime 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 prime-sequence length is p-1 (n = 0 through p-2), since for n = p-1, 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 = p-1 condition all by istelf) and examine the resulting prime-sequence lengths, with asterisks indicating maximal-length 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 maximal-length prime sequence is p = 29, for which f(n=2) = 35 = 5*7.
(In fact that is the minimal-length prime sequence which is possible under our construction-starting-with-twin-prime-pair.)

o We see that maximal-length 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 maximal-length sequences for p < 1000, and the average prime-sequence length plunges, especially relative to p.

o Looking at the numbers it certainly appears that the odds of a maximal-length 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 twin-prime 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*(p-1). 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 4-offset pair (a so-called cousin-prime pair), whose larger term is the smaller of a 6-offset pair, all the way through the terminating 2*(p-1) - 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 twin-prime pair which opens the sequence.

Whether there are infinitely many twin-prime 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 paired-event 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 maximal-length '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 known-convergent 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 minus-sign version produces distinct primes for n = 1,...,p-1) 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 maximal-length sequence.

The above 3-and-change 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 twin-prime-associated sum is just a little less than 2, and crude-hand-wavingly assume a similar constant for the generalized sequence, we get something quite close to the 6 lucky numbers which actually exist.

Last fiddled with by ewmayer on 2015-10-18 at 01:39