login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A090659 Odd composites with increasing proportion of nontrivial non-witnesses of compositeness by the Miller-Rabin primality test. 1

%I

%S 25,91,703,1891,12403,38503,79003,88831,146611,188191,218791,269011,

%T 286903,385003,497503,597871,736291,765703,954271,1056331,1314631,

%U 1869211,2741311,3270403,3913003,4255903,4686391,5292631,6186403,6969511,8086231,9080191

%N Odd composites with increasing proportion of nontrivial non-witnesses of compositeness by the Miller-Rabin primality test.

%C Rabin has shown that the proportion has an upper bound of 0.25. If the trivial non-witnesses are counted, this upper bound is reached at 9. If the conjecture is true that the later terms are always the product of two primes p and (2*p-1), then the sequence continues 188191 218791 269011 286903 385003 497503 597871 736291 765703 954271 1056331 1314631 1869211 2741311 3270403 3913003 4255903 4686391 5292631.

%C Dickson's conjecture implies that this sequence is infinite. Can this be proved unconditionally? - _Charles R Greathouse IV_, Mar 10 2011

%C Higgins' conjecture 2 is implied by his conjecture 1, which is true by the general form of the number of non-witnesses of an odd number. - _Charles R Greathouse IV_, Mar 10 2011

%D S. Narayanan, Improving the Speed and Accuracy of the Miller-Rabin Primality Test 2015; http://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf

%H Charles R Greathouse IV, <a href="/A090659/b090659.txt">Table of n, a(n) for n = 1..5411</a>

%H Brian C. Higgins, <a href="http://www.ma.iup.edu/MAA/proceedings/vol1/higgins.pdf">The Rabin-Miller Primality Test: Some Results on the Number of Non-witnesses to Compositeness</a>

%H Michael O. Rabin, <a href="http://dx.doi.org/10.1016/0022-314X(80)90084-0">Probabilistic algorithm for testing primality</a>, Journal of Number Theory 12:1 (1980), pp. 128-138.

%e 25 has 2 nontrivial non-witnesses (NTNW), namely (7,18), for a proportion of 2/22=0.0909. The denominator is 22 because the non-witnesses are selected from 2..23 (as 1 and 24 are trivial non-witnesses).

%e 49 has 4 NTNW, namely (18,19,30,31) for a proportion of 4/46=0.0870. This is a smaller proportion than 0.0909 for 25.

%e 91=7*13 has 16 NTNW in the range [2..89], namely [9, 10, 12, 16, 17, 22, 29, 38, 53, 62, 69, 74, 75, 79, 81, 82], for a proportion of 16/88=0.182. It also has two trivial non-witnesses 1 and 90, which are not counted. The next integer with a higher proportion is 703, with 160 nontrivial non-witnesses and proportion 0.229.

%Y Subsequence of A141768.

%K nonn

%O 1,1

%A _Ken Takusagawa_, Dec 14 2003

%E Extended and edited by _Charles R Greathouse IV_, Mar 09 2011

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 7 11:56 EDT 2020. Contains 336276 sequences. (Running on oeis4.)