Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: six strong pseudoprimes, one degree 4096 polynomial
Posted:
Jun 21, 2013 12:46 PM


On 06/20/2013 07:04 AM, David Bernier wrote: > On 06/12/2013 12:19 AM, Graham Cooper wrote: >> On Jun 1, 8:36 am, David Bernier <david...@videotron.ca> wrote: >>> If I start with the polynomial function: >>> g(x) = x^4  x^2 +1 then >>> >>> P(x) := g(g(g(g(g(g(x)))))) is also a polynomial function of x. >>> >>> The degree of P in x is: 4*4*4*4*4*4 = 4^6 = 2^12 = 4096. >>> >>> Letting 'x' go from 2 to 14,845 >>> 6 values of 'x' give that P(x) is a strong pseudoprime, >>> passing the RabinMiller test with 60 random bases in each >>> case. >>> >>> x= 55, 1948, 3269, 3981, 7341, 14845 >>> are those 6 values. >>> >>> Beyond ~= 3269, I was only testing x with exactly >>> two prime factors, so there could possibly be >>> more x with P(x) a strong psudoprime and >>> x <= 14845. >>> >>> P(14845) has about 17000 digits, and >>> 17000digit numbers are prime once in >>> 2.5 *17000 or one time in 42500. >>> >>> With x in {55, 1948, 3269, 3981, 7341, 14845} >>> each yielding a probable prime for P(x), the >>> (with "high probability"), the primality >>> statistics for the P(x), heuristics, seem to >>> be out of whack. >> >> >> How many were you expecting? > > I redid the tests. Now I find > 8 probable primes up to k= 14900. > I was expecting 0.43 using 1/log(x) > heuristics as the likelihood a > somesuch integer x > 1. > > Here's a small table: > > > > [===========================] > [ 1 55 7128 ] > [ 2 1948 13474 ] > [ 3 3269 14395 ] > [ 4 3981 14746 ] > [ 5 6942 15735 ] > [ 6 7341 15834 ] > [ 7 10141 16409 ] > [ 8 14845 17087 ] > [===========================] > > > 8 probable primes up to 'arg' as in > g^6(arg) > a large number that I test for probable > primeness. > > Reminder that g(X):= X^4X^2+1. > > Naive expectation for how many primes > for this range of arguments to g^6 > is then 0.4312 but we may have 8, which > is 18.55 times the naive expectation. > [...]
Update on testing up to 25000 exhaustively: now, about 11 probable primes. It's still running mind you.
The PARI/gp code:
? count=0;for(W=2,25000,count=count+1;for(Z=6,6,par=Z;new=W;for(X=1,par,new=new^4new^2+1);if(ispseudoprime(new),print(W," ",round(log(new)/log(10))))))
Here's the output, meaning a value 'k' such that g^6 (k) is a probable prime, followed by the number of decimal digits in g^6 (k), within a margin of error of +/ 1 digit.
g(X):= X^4 X^2 + 1 , as always.
Extended table:
55 7128 1948 13474 3269 14395 3981 14746 6942 15735 7341 15834 10141 16409 14845 17087 15476 17161 20913 17696 23360 17893
dave  On Hypnos, http://messagenetcommresearch.com/myths/bios/hypnos.html



