cp's OEIS Frontend

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

%I A090659 #30 May 11 2023 03:11:48
%S A090659 25,91,703,1891,12403,38503,79003,88831,146611,188191,218791,269011,
%T A090659 286903,385003,497503,597871,736291,765703,954271,1056331,1314631,
%U A090659 1869211,2741311,3270403,3913003,4255903,4686391,5292631,6186403,6969511,8086231,9080191
%N A090659 Odd composites with increasing proportion of nontrivial non-witnesses of compositeness by the Miller-Rabin primality test.
%C A090659 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 A090659 Dickson's conjecture implies that this sequence is infinite. Can this be proved unconditionally? - _Charles R Greathouse IV_, Mar 10 2011
%C A090659 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
%H A090659 Charles R Greathouse IV, <a href="/A090659/b090659.txt">Table of n, a(n) for n = 1..5411</a>
%H A090659 Brian C. Higgins, <a href="https://web.archive.org/web/20100331175654/http://www.ma.iup.edu:80/MAA/proceedings/vol1/higgins.pdf">The Rabin-Miller Primality Test: Some Results on the Number of Non-witnesses to Compositeness</a>, ALLEMO Spring 1996 Meeting at IUP, Proceedings Volume 1.
%H A090659 S. Narayanan, <a href="http://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf">Improving the Speed and Accuracy of the Miller-Rabin Primality Test</a>, MIT PRIMES-USA, 2015.
%H A090659 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 A090659 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 A090659 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 A090659 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 A090659 Subsequence of A141768.
%K A090659 nonn
%O A090659 1,1
%A A090659 _Ken Takusagawa_, Dec 14 2003
%E A090659 Extended and edited by _Charles R Greathouse IV_, Mar 09 2011