I have run:
on a 1GHz Athlon for about ten days; for x = 2 upto 10,000,000,001
and found 527,345,506 probable primes and no "counterexample".
The program tests "f|x^f-x=>5 times Miller-Rabin probable prime where
f=x^3-x-1 and x>1". The probability of a composite f:f|x^f-x getting
through 5 Miller Rabin rounds is less than 4^-5.
341 is the smallest base 2 Fermat pseudoprime.
561 is the smallest Carmichael number.
705 is the smallest pseudoprime n for the test "the sum of the nth
powers of the roots of x^2-x-1 is congruent to 1 modulo n".
124 is the smallest x for which the test "f|x^f-x where f=x^2-x-1"
produces a pseudoprime f.
19802 is the smallest x for which the test "f|x^f-x where f=x^2-x-1"
produces a Carmichael number f.
271441 is the smallest Perrin pseudoprime. (The nth term in the
Perrin Sequence is equal to the sum of the nth powers of the roots of
27664033 is the smallest symmetric pseudoprime relative to the
elementary symmetric functions of the roots of x^3-x-1.
7045248121 is the smallest Perrin pseudoprime that is also a
What is the smallest composite f:f|x^f-x where f=x^3-x-1? David
Broadhurst reckons Erdos' Carmichael conjecture implies x ~ 10^13 for
a Carmichael number ;-)
- please see OP:
I have tested 1<x<=10^11 (4,772,369,646 PrPs). Many thanks to Michael
Angel who tested 10^11<x<=223,490,000,000. We found no composite x-
PrP x^3-x-1. The computations took some 250 GHz days in total.