login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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
25, 91, 703, 1891, 12403, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1056331, 1314631, 1869211, 2741311, 3270403, 3913003, 4255903, 4686391, 5292631, 6186403, 6969511, 8086231, 9080191 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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.

Dickson's conjecture implies that this sequence is infinite. Can this be proved unconditionally? [Charles R Greathouse IV, Mar 10, 2011]

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]

REFERENCES

M. O. Rabin. Probabilistic algorithms for testing primality. J. Number Theory, 12:128-138, 1980.

LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 1..5411

Brian C. Higgins, The Rabin-Miller Primality Test: Some Results on the Number of Non-witnesses to Compositeness

EXAMPLE

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).

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.

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.

CROSSREFS

Subsequence of A141768.

Sequence in context: A087240 A044212 A044593 * A010013 A063769 A099771

Adjacent sequences:  A090656 A090657 A090658 * A090660 A090661 A090662

KEYWORD

nonn

AUTHOR

Ken Takusagawa, Dec 14 2003

EXTENSIONS

Extended and edited by Charles R Greathouse IV, Mar 09 2011

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified September 1 19:46 EDT 2014. Contains 246317 sequences.