[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)

[Thomas Klemm]

(02-16-2019 05:39 PM)Gerald H Wrote:  Set at random

N := 803189 * 485909

the product of two primes, how many bases are actually witnesses?

It could very well be that this number has no strong liars.

(02-16-2019 06:18 PM)Gerald H Wrote:  Have you actually had a look at or used the programme on the 35s?

I had a look at the program but wasn't able to follow.
Even if the batteries of my HP-35s weren't dead I doubt I would enter an 850 line program just to figure that out by myself.

Quote:Should you inspect the programme you'll find the largest small factor that is tested for is

999999

Not sure if I understood that correctly but I checked products \(n = p \cdot q\) of primes \(p, q > 1000\).
So they shouldn't be detected by testing small factors.

Code:

      r      n       k
      417.11 1102837 2644
     1012.01 1018081 1006
     1016.01 1026169 1010
     1022.01 1038361 1016
     1024.01 1042441 1018
     1034.01 1062961 1028
     1036.01 1067089 1030
     1042.01 1079521 1036
     1052.01 1100401 1046
     1054.01 1104601 1048
     1064.01 1125721 1058
     1066.01 1129969 1060
     1072.01 1142761 1066
     1090.01 1181569 1084
     1094.01 1190281 1088
     1096.01 1194649 1090
     1100.01 1203409 1094
     1205.06 1060459 880
     1305.39 1148743 880
     2395.24 1073071 448
     5317.83 1042297 196
     6703.52 1072567 160
     7319.45 1083281 148
…

Chances might be small with \(1102837=1009×1093\) to hit a strong liar but they are not 0.
I was only aware of the upper bound of the probability \(p<\frac{1}{4}\) but not of the exact distribution.

Cheers
Thomas