Talk:Find largest left truncatable prime in a given base

Unclear text in page

Could someone make the example where it says "in base 10 candidates are 2,3,5,7. Putting a digit in the range 1 to base-1 in front of each candidate must result in a prime. So 2 and 5, like the whale and the petunias in The Hitchhiker's Guide to the Galaxy, come into existance only to be extinguished" clearer? I thought it was about 12 and 15, but it is not.

Thanks. Can I remove this whole item? Or is it supposed to remain for some sort of historical documentation?

Hint for base 10, 12, 14 etc

Where the maximum left truncatable prime in a base is say 24 digits or more, to solve this task fully, try using a quick test for probable primality. Then only test for total compliance with your final candidate.--Nigel Galloway 11:50, 15 September 2012 (UTC)

Note, that setting the confidence too low will increase the number of composites which will need to be tested and so may not lead to optimal performance.

Using java.math.BigInteger.new(candidate).isProbablePrime(confidence):

At 1 I found that the number of candidates at some levels increased over that achieved at 100.

At 5 I have found the number of candidates at each level to be the same as the number found at 100 (where I have been able to determine the 100 number).

--Nigel Galloway 11:56, 21 September 2012 (UTC)

It's fascinating that when I compare the number of primes at different stages using different levels of reliability testing, the difference with one Miller-Rabin round is only about 1% larger than the count with 5, and often rather less than that. This means that as the number of candidates narrows back down again as the prime size increases, the bad candidates seem to be being removed. Fascinating, that. Also, if you've not got a good MR implementation, you really need a decent modpow() function/operator; it makes a gigantic difference. (Now, to find a faster computer…) –Donal Fellows 09:09, 8 October 2012 (UTC)

Yes, why is this task so easy? Richard G.E. Pinch records his personal research on strong psudoprimes here. Analysis of the data presented there indicates that the Largest Left Truncatable Prime algorithm is a bad generator of strong pseudoprimes, orders of magnitude worse than a random number generator. I have added a task here which introduces the subject to Rosetta Code.--Nigel Galloway 13:17, 30 November 2012 (UTC)

Number of left truncatable primes in a given base

You nay wish to keep a count of the number of left truncatable primes in a given base.--Nigel Galloway 11:50, 15 September 2012 (UTC)

Using the JRuby example to print the number of left truncatable primes by digit count produces:

1 1 1
The largest left truncatable prime in base 3 is 23

2 2 3 3 3 3
The largest left truncatable prime in base 4 is 4091

2 4 4 3 1 1
The largest left truncatable prime in base 5 is 7817

3 4 12 25 44 54 60 62 59 51 35 20 12 7 3 2 1
The largest left truncatable prime in base 6 is 4836525320399

3 6 6 4 1 1 1
The largest left truncatable prime in base 7 is 817337

4 12 29 50 66 77 61 51 38 27 17 8 3 2 1
The largest left truncatable prime in base 8 is 14005650767869

4 9 15 17 24 16 9 6 5 3
The largest left truncatable prime in base 9 is 1676456897

4 11 39 99 192 326 429 521 545 517 448 354 276 212 117 72 42 24 13 6 5 4 3 1
The largest left truncatable prime in base 10 is 357686312646216567629137

4 8 15 18 15 8 4 2 1
The largest left truncatable prime in base 11 is 2276005673

5 23 119 409 1124 2496 4733 7711 11231 14826 17341 18787 19001 17567 15169 12085 9272 6606 4451 2882 1796 1108 601 346 181 103 49 19 8 2 1 1
The largest left truncatable prime in base 12 is 13092430647736190817303130065827539

5 13 20 23 17 11 7 4
The largest left truncatable prime in base 13 is 812751503

6 26 101 300 678 1299 2093 3017 3751 4196 4197 3823 3206 2549 1908 1269 783 507 322 163 97 55 27 13 5 2
The largest left truncatable prime in base 14 is 615419590422100474355767356763

6 22 79 207 391 644 934 1177 1275 1167 1039 816 608 424 261 142 74 45 25 13 7 1
The largest left truncatable prime in base 15 is 34068645705927662447286191

6 31 124 337 749 1292 1973 2695 3210 3490 3335 2980 2525 1840 1278 878 556 326 174 93 50 25 9 5 1
The largest left truncatable prime in base 16 is 1088303707153521644968345559987

6 22 43 55 74 58 41 31 23 8 1
The largest left truncatable prime in base 17 is 13563641583101

7 49 311 1396 5117 15243 38818 85683 167132 293518 468456 680171 911723 1133959 1313343 1423597 1449405 1395514 1270222 1097353 902477 707896 529887 381239 2632 75 174684 111046 67969 40704 23201 12793 6722 3444 1714 859 422 205 98 39 14 7 1 1
The largest left truncatable prime in base 18 is 571933398724668544269594979167602382822769202133808087

7 29 61 106 122 117 93 66 36 18 10 10 6 4
The largest left truncatable prime in base 19 is 546207129080421139

8 56 321 1311 4156 10963 24589 47737 83011 129098 181707 234685 278792 306852 315113 302684 273080 233070 188331 145016 105557 73276 48819 31244 19237 11209 6209 3383 1689 917 430 196 80 44 20 7 2
The largest left truncatable prime in base 20 is 1073289911449776273800623217566610940096241078373

8 41 165 457 1079 2072 3316 4727 6003 6801 7051 6732 5862 4721 3505 2474 1662 1039 628 369 219 112 52 17 13 4 2
The largest left truncatable prime in base 21 is 391461911766647707547123429659688417

8 48 261 1035 3259 8247 17727 33302 55354 82379 111917 137857 158043 167442 165782 152997 132508 108083 83974 61950 43453 29212 18493 11352 6693 3738 2053 1125594 293 145 70 31 13 6 2 1
The largest left truncatable prime in base 22 is 33389741556593821170176571348673618833349516314271

8 30 78 137 181 200 186 171 121 100 67 41 24 16 9 2 1
The largest left truncatable prime in base 23 is 116516557991412919458949

--Nigel Galloway 12:41, 16 September 2012 (UTC)

Discrepancy in auxiliary output

Tcl vs...

The other solution showing these counts is Tcl and for base 12 it reports 1126 candidates at length 5 whereas the counts above for Perl 6 show 1124. This is the first discrepancy. Auxiliary output from the Fortran version also shows 1124 and matches the other counts from Perl 6 also. So, here are the 1124 five-digit base twelve candidates, in storage order:

Schedule

           5 candidates at length           1
          23 candidates at length           2
         119 candidates at length           3
         409 candidates at length           4
        1124 candidates at length           5
   1      241049 = 11.7.5.11.5
   2      137369 = 6.7.5.11.5
   3       75161 = 3.7.5.11.5
   4      113177 = 5.5.5.11.5
   5       50969 = 2.5.5.11.5
   6      226937 = 10.11.3.11.5
   7      164729 = 7.11.3.11.5
   8      156089 = 7.6.3.11.5
   9      135353 = 6.6.3.11.5
  10      114617 = 5.6.3.11.5
  11      216569 = 10.5.3.11.5
  12       92153 = 4.5.3.11.5
  13      235577 = 11.4.3.11.5
  14       48953 = 2.4.3.11.5
  15      230393 = 11.1.3.11.5
  16      147449 = 7.1.3.11.5
  17      126713 = 6.1.3.11.5
  18      105977 = 5.1.3.11.5
  19      226649 = 10.11.1.11.5
  20      205913 = 9.11.1.11.5
  21      185177 = 8.11.1.11.5
  22      102233 = 4.11.1.11.5
  23       60761 = 2.11.1.11.5
  24      240473 = 11.7.1.11.5
  25       53849 = 2.7.1.11.5
  26       33113 = 1.7.1.11.5
  27      235289 = 11.4.1.11.5
  28      173081 = 8.4.1.11.5
  29       69401 = 3.4.1.11.5
  30      217697 = 10.5.11.9.5
  31      196961 = 9.5.11.9.5
  32      134753 = 6.5.11.9.5
  33       93281 = 4.5.11.9.5
  34      112289 = 5.4.11.9.5
  35       25889 = 1.2.11.9.5
  36      243473 = 11.8.10.9.5
  37      202001 = 9.8.10.9.5
  38      119057 = 5.8.10.9.5
  39       98321 = 4.8.10.9.5
  40      200273 = 9.7.10.9.5
  41      117329 = 5.7.10.9.5
  42      196817 = 9.5.10.9.5
  43      176081 = 8.5.10.9.5
  44      134609 = 6.5.10.9.5
  45      234833 = 11.3.10.9.5
  46       89681 = 4.3.10.9.5
  47      212369 = 10.2.10.9.5
  48       67217 = 3.2.10.9.5
  49      118913 = 5.8.9.9.5
  50       35969 = 1.8.9.9.5
  51      239873 = 11.6.9.9.5
  52      136193 = 6.6.9.9.5
  53       23873 = 1.1.9.9.5
  54      163409 = 7.10.6.9.5
  55      142673 = 6.10.6.9.5
  56      121937 = 5.10.6.9.5
  57       59729 = 2.10.6.9.5
  58       38993 = 1.10.6.9.5
  59      182417 = 8.9.6.9.5
  60      120209 = 5.9.6.9.5
  61       78737 = 3.9.6.9.5
  62      183569 = 8.10.2.9.5
  63      142097 = 6.10.2.9.5
  64       79889 = 3.10.2.9.5
  65      157649 = 7.7.2.9.5
  66      116177 = 5.7.2.9.5
  67       95441 = 4.7.2.9.5
  68      237137 = 11.5.2.9.5
  69      216401 = 10.5.2.9.5
  70      174929 = 8.5.2.9.5
  71       71249 = 3.5.2.9.5
  72       50513 = 2.5.2.9.5
  73      188753 = 9.1.2.9.5
  74      119489 = 5.9.1.9.5
  75       78017 = 3.9.1.9.5
  76      179969 = 8.8.1.9.5
  77      159233 = 7.8.1.9.5
  78      138497 = 6.8.1.9.5
  79       76289 = 3.8.1.9.5
  80      212801 = 10.3.1.9.5
  81      171329 = 8.3.1.9.5
  82      109121 = 5.3.1.9.5
  83       26177 = 1.3.1.9.5
  84       40853 = 1.11.7.8.5
  85      182549 = 8.9.7.8.5
  86       37397 = 1.9.7.8.5
  87       92693 = 4.5.7.8.5
  88      230933 = 11.1.7.8.5
  89       85781 = 4.1.7.8.5
  90      241013 = 11.7.5.8.5
  91      175349 = 8.5.5.8.5
  92      154613 = 7.5.5.8.5
  93      133877 = 6.5.5.8.5
  94       30197 = 1.5.5.8.5
  95       44021 = 2.1.5.8.5
  96      163109 = 7.10.4.8.5
  97      121637 = 5.10.4.8.5
  98       38693 = 1.10.4.8.5
  99      223589 = 10.9.4.8.5
 100       99173 = 4.9.4.8.5
 101       78437 = 3.9.4.8.5
 102      111269 = 5.4.4.8.5
 103       90533 = 4.4.4.8.5
 104      151013 = 7.3.4.8.5
 105      109541 = 5.3.4.8.5
 106       26597 = 1.3.4.8.5
 107      211493 = 10.2.4.8.5
 108      170021 = 8.2.4.8.5
 109      128549 = 6.2.4.8.5
 110      162821 = 7.10.2.8.5
 111      121349 = 5.10.2.8.5
 112      100613 = 4.10.2.8.5
 113       59141 = 2.10.2.8.5
 114      174917 = 8.5.2.8.5
 115      154181 = 7.5.2.8.5
 116       71237 = 3.5.2.8.5
 117      233669 = 11.3.2.8.5
 118      109253 = 5.3.2.8.5
 119       26309 = 1.3.2.8.5
 120      182537 = 8.9.7.7.5
 121       78857 = 3.9.7.7.5
 122      173897 = 8.4.7.7.5
 123       49481 = 2.4.7.7.5
 124      248057 = 11.11.6.7.5
 125      185849 = 8.11.6.7.5
 126       40697 = 1.11.6.7.5
 127      246329 = 11.10.6.7.5
 128      204857 = 9.10.6.7.5
 129      199673 = 9.7.6.7.5
 130      158201 = 7.7.6.7.5
 131       54521 = 2.7.6.7.5
 132      239417 = 11.6.6.7.5
 133      218681 = 10.6.6.7.5
 134      177209 = 8.6.6.7.5
 135      115001 = 5.6.6.7.5
 136       73529 = 3.6.6.7.5
 137       32057 = 1.6.6.7.5
 138      191033 = 9.2.6.7.5
 139      149561 = 7.2.6.7.5
 140      108089 = 5.2.6.7.5
 141       66617 = 3.2.6.7.5
 142       59561 = 2.10.5.7.5
 143      244457 = 11.9.5.7.5
 144      120041 = 5.9.5.7.5
 145       78569 = 3.9.5.7.5
 146       37097 = 1.9.5.7.5
 147      242729 = 11.8.5.7.5
 148       97577 = 4.8.5.7.5
 149      239273 = 11.6.5.7.5
 150      156329 = 7.6.5.7.5
 151      135593 = 6.6.5.7.5
 152       94121 = 4.6.5.7.5
 153       99017 = 4.9.3.7.5
 154       36809 = 1.9.3.7.5
 155      218249 = 10.6.3.7.5
 156      176777 = 8.6.3.7.5
 157      156041 = 7.6.3.7.5
 158       52361 = 2.6.3.7.5
 159      237257 = 11.5.3.7.5
 160      154313 = 7.5.3.7.5
 161      194057 = 9.4.3.7.5
 162      131849 = 6.4.3.7.5
 163      159209 = 7.8.1.7.5
 164       97001 = 4.8.1.7.5
 165       55529 = 2.8.1.7.5
 166      219689 = 10.7.1.7.5
 167      198953 = 9.7.1.7.5
 168      116009 = 5.7.1.7.5
 169       95273 = 4.7.1.7.5
 170      176489 = 8.6.1.7.5
 171      135017 = 6.6.1.7.5
 172      114281 = 5.6.1.7.5
 173       31337 = 1.6.1.7.5
 174      212777 = 10.3.1.7.5
 175      109097 = 5.3.1.7.5
 176       46889 = 2.3.1.7.5
 177       26153 = 1.3.1.7.5
 178      143333 = 6.10.11.4.5
 179      122597 = 5.10.11.4.5
 180       79397 = 3.9.11.4.5
 181       58661 = 2.9.11.4.5
 182      226133 = 10.10.10.4.5
 183      205397 = 9.10.10.4.5
 184      122453 = 5.10.10.4.5
 185       39509 = 1.10.10.4.5
 186      238229 = 11.5.10.4.5
 187      176021 = 8.5.10.4.5
 188       93077 = 4.5.10.4.5
 189       72341 = 3.5.10.4.5
 190       30869 = 1.5.10.4.5
 191      231317 = 11.1.10.4.5
 192      127637 = 6.1.10.4.5
 193       23957 = 1.1.10.4.5
 194      142757 = 6.10.7.4.5
 195      122021 = 5.10.7.4.5
 196      211877 = 10.2.7.4.5
 197      191141 = 9.2.7.4.5
 198       45989 = 2.2.7.4.5
 199       25253 = 1.2.7.4.5
 200      168677 = 8.1.7.4.5
 201       85733 = 4.1.7.4.5
 202       64997 = 3.1.7.4.5
 203      237509 = 11.5.5.4.5
 204      113093 = 5.5.5.4.5
 205       92357 = 4.5.5.4.5
 206      149381 = 7.2.5.4.5
 207      204101 = 9.10.1.4.5
 208      162629 = 7.10.1.4.5
 209      121157 = 5.10.1.4.5
 210      119429 = 5.9.1.4.5
 211       57221 = 2.9.1.4.5
 212      133253 = 6.5.1.4.5
 213       91781 = 4.5.1.4.5
 214       29573 = 1.5.1.4.5
 215      214469 = 10.4.1.4.5
 216       90053 = 4.4.1.4.5
 217       69317 = 3.4.1.4.5
 218      233477 = 11.3.1.4.5
 219      150533 = 7.3.1.4.5
 220       67589 = 3.3.1.4.5
 221       46853 = 2.3.1.4.5
 222      245129 = 11.9.10.3.5
 223      203657 = 9.9.10.3.5
 224      182921 = 8.9.10.3.5
 225      120713 = 5.9.10.3.5
 226       79241 = 3.9.10.3.5
 227      200201 = 9.7.10.3.5
 228      137993 = 6.7.10.3.5
 229       55049 = 2.7.10.3.5
 230       34313 = 1.7.10.3.5
 231      212297 = 10.2.10.3.5
 232      191561 = 9.2.10.3.5
 233      150089 = 7.2.10.3.5
 234       87881 = 4.2.10.3.5
 235       25673 = 1.2.10.3.5
 236      169097 = 8.1.10.3.5
 237      148361 = 7.1.10.3.5
 238      227561 = 10.11.8.3.5
 239       61673 = 2.11.8.3.5
 240      160169 = 7.8.8.3.5
 241       97961 = 4.8.8.3.5
 242       56489 = 2.8.8.3.5
 243       35753 = 1.8.8.3.5
 244      237929 = 11.5.8.3.5
 245      113513 = 5.5.8.3.5
 246      170537 = 8.2.8.3.5
 247      225689 = 10.10.7.3.5
 248      163481 = 7.10.7.3.5
 249      101273 = 4.10.7.3.5
 250       80537 = 3.10.7.3.5
 251      154841 = 7.5.7.3.5
 252      230873 = 11.1.7.3.5
 253      189401 = 9.1.7.3.5
 254       44249 = 2.1.7.3.5
 255      163193 = 7.10.5.3.5
 256      121721 = 5.10.5.3.5
 257       59513 = 2.10.5.3.5
 258      173561 = 8.4.5.3.5
 259       90617 = 4.4.5.3.5
 260       28409 = 1.4.5.3.5
 261      107897 = 5.2.5.3.5
 262       24953 = 1.2.5.3.5
 263      199337 = 9.7.4.3.5
 264      178601 = 8.7.4.3.5
 265      216617 = 10.5.4.3.5
 266      154409 = 7.5.4.3.5
 267      133673 = 6.5.4.3.5
 268      152681 = 7.4.4.3.5
 269       90473 = 4.4.4.3.5
 270       69737 = 3.4.4.3.5
 271      109481 = 5.3.4.3.5
 272      211433 = 10.2.4.3.5
 273      128489 = 6.2.4.3.5
 274       24809 = 1.2.4.3.5
 275      221069 = 10.7.11.2.5
 276      117389 = 5.7.11.2.5
 277      157133 = 7.6.11.2.5
 278      136397 = 6.6.11.2.5
 279       74189 = 3.6.11.2.5
 280       53453 = 2.6.11.2.5
 281       32717 = 1.6.11.2.5
 282      134669 = 6.5.11.2.5
 283      113933 = 5.5.11.2.5
 284       72461 = 3.5.11.2.5
 285      246557 = 11.10.8.2.5
 286      225821 = 10.10.8.2.5
 287      163613 = 7.10.8.2.5
 288       80669 = 3.10.8.2.5
 289      198173 = 9.6.8.2.5
 290       73757 = 3.6.8.2.5
 291      194717 = 9.4.8.2.5
 292      173981 = 8.4.8.2.5
 293      111773 = 5.4.8.2.5
 294      211997 = 10.2.8.2.5
 295       25373 = 1.2.8.2.5
 296      148061 = 7.1.8.2.5
 297       85853 = 4.1.8.2.5
 298       44381 = 2.1.8.2.5
 299      164621 = 7.11.3.2.5
 300       81677 = 3.11.3.2.5
 301      232013 = 11.2.3.2.5
 302      149069 = 7.2.3.2.5
 303       86861 = 4.2.3.2.5
 304       45389 = 2.2.3.2.5
 305      162749 = 7.10.2.2.5
 306       59069 = 2.10.2.2.5
 307       38333 = 1.10.2.2.5
 308      240509 = 11.7.2.2.5
 309      199037 = 9.7.2.2.5
 310      178301 = 8.7.2.2.5
 311       33149 = 1.7.2.2.5
 312      214589 = 10.4.2.2.5
 313      152381 = 7.4.2.2.5
 314      110909 = 5.4.2.2.5
 315       90173 = 4.4.2.2.5
 316      129917 = 6.3.2.2.5
 317       67709 = 3.3.2.2.5
 318       26237 = 1.3.2.2.5
 319      185069 = 8.11.1.2.5
 320      122861 = 5.11.1.2.5
 321      242093 = 11.8.1.2.5
 322       55469 = 2.8.1.2.5
 323      219629 = 10.7.1.2.5
 324       95213 = 4.7.1.2.5
 325      126317 = 6.1.1.2.5
 326       64109 = 3.1.1.2.5
 327       22637 = 1.1.1.2.5
 328      241793 = 11.7.11.1.5
 329      158849 = 7.7.11.1.5
 330      138113 = 6.7.11.1.5
 331      198593 = 9.6.11.1.5
 332       74177 = 3.6.11.1.5
 333       53441 = 2.6.11.1.5
 334      236609 = 11.4.11.1.5
 335      195137 = 9.4.11.1.5
 336      132929 = 6.4.11.1.5
 337       91457 = 4.4.11.1.5
 338      169217 = 8.1.11.1.5
 339       65537 = 3.1.11.1.5
 340      165041 = 7.11.6.1.5
 341      244529 = 11.9.6.1.5
 342      203057 = 9.9.6.1.5
 343       99377 = 4.9.6.1.5
 344       50993 = 2.5.6.1.5
 345      235889 = 11.4.6.1.5
 346      215153 = 10.4.6.1.5
 347       70001 = 3.4.6.1.5
 348      232433 = 11.2.6.1.5
 349      149489 = 7.2.6.1.5
 350       87281 = 4.2.6.1.5
 351       25073 = 1.2.6.1.5
 352      147761 = 7.1.6.1.5
 353       64817 = 3.1.6.1.5
 354      199313 = 9.7.4.1.5
 355      157841 = 7.7.4.1.5
 356       95633 = 4.7.4.1.5
 357       74897 = 3.7.4.1.5
 358      169937 = 8.2.4.1.5
 359       86993 = 4.2.4.1.5
 360      247553 = 11.11.3.1.5
 361      226817 = 10.11.3.1.5
 362      206081 = 9.11.3.1.5
 363      143873 = 6.11.3.1.5
 364       40193 = 1.11.3.1.5
 365      225089 = 10.10.3.1.5
 366      204353 = 9.10.3.1.5
 367      162881 = 7.10.3.1.5
 368      100673 = 4.10.3.1.5
 369      223361 = 10.9.3.1.5
 370      181889 = 8.9.3.1.5
 371      140417 = 6.9.3.1.5
 372      103451 = 4.11.10.4.11
 373       61979 = 2.11.10.4.11
 374       41243 = 1.11.10.4.11
 375      239963 = 11.6.10.4.11
 376      198491 = 9.6.10.4.11
 377      157019 = 7.6.10.4.11
 378      115547 = 5.6.10.4.11
 379       94811 = 4.6.10.4.11
 380       32603 = 1.6.10.4.11
 381      217499 = 10.5.10.4.11
 382      155291 = 7.5.10.4.11
 383      113819 = 5.5.10.4.11
 384       93083 = 4.5.10.4.11
 385      176747 = 8.6.3.4.11
 386      156011 = 7.6.3.4.11
 387      149099 = 7.2.3.4.11
 388       24683 = 1.2.3.4.11
 389      245723 = 11.10.2.4.11
 390      204251 = 9.10.2.4.11
 391      162779 = 7.10.2.4.11
 392      109211 = 5.3.2.4.11
 393       26267 = 1.3.2.4.11
 394      169691 = 8.2.2.4.11
 395      238247 = 11.5.10.5.11
 396      155303 = 7.5.10.5.11
 397      236519 = 11.4.10.5.11
 398      195047 = 9.4.10.5.11
 399      174311 = 8.4.10.5.11
 400      112103 = 5.4.10.5.11
 401       91367 = 4.4.10.5.11
 402       87911 = 4.2.10.5.11
 403       46439 = 2.2.10.5.11
 404       25703 = 1.2.10.5.11
 405      241559 = 11.7.9.5.11
 406      200087 = 9.7.9.5.11
 407      179351 = 8.7.9.5.11
 408      238103 = 11.5.9.5.11
 409      217367 = 10.5.9.5.11
 410       82759 = 3.11.10.8.7
 411      124231 = 5.11.10.8.7
 412      144967 = 6.11.10.8.7
 413      165703 = 7.11.10.8.7
 414       46471 = 2.2.10.8.7
 415       87943 = 4.2.10.8.7
 416      150151 = 7.2.10.8.7
 417      170887 = 8.2.10.8.7
 418       24007 = 1.1.10.8.7
 419       65479 = 3.1.10.8.7
 420      169159 = 8.1.10.8.7
 421      210631 = 10.1.10.8.7
 422      231367 = 11.1.10.8.7
 423       41143 = 1.11.9.8.7
 424       61879 = 2.11.9.8.7
 425      124087 = 5.11.9.8.7
 426      165559 = 7.11.9.8.7
 427      184567 = 8.10.9.8.7
 428       51511 = 2.5.9.8.7
 429      113719 = 5.5.9.8.7
 430      155191 = 7.5.9.8.7
 431      196663 = 9.5.9.8.7
 432       49783 = 2.4.9.8.7
 433      236407 = 11.4.9.8.7
 434       57991 = 2.9.6.8.7
 435      120199 = 5.9.6.8.7
 436      178951 = 8.7.6.8.7
 437      199687 = 9.7.6.8.7
 438       90823 = 4.4.6.8.7
 439      215239 = 10.4.6.8.7
 440       47623 = 2.3.6.8.7
 441      109831 = 5.3.6.8.7
 442      151303 = 7.3.6.8.7
 443      191047 = 9.2.6.8.7
 444      158071 = 7.7.5.8.7
 445      178807 = 8.7.5.8.7
 446      220279 = 10.7.5.8.7
 447       71671 = 3.5.5.8.7
 448      113143 = 5.5.5.8.7
 449      196087 = 9.5.5.8.7
 450       88951 = 4.3.5.8.7
 451      130423 = 6.3.5.8.7
 452      192631 = 9.3.5.8.7
 453      234103 = 11.3.5.8.7
 454      126967 = 6.1.5.8.7
 455      147703 = 7.1.5.8.7
 456      230647 = 11.1.5.8.7
 457       75967 = 3.7.11.6.7
 458       96703 = 4.7.11.6.7
 459      200383 = 9.7.11.6.7
 460       31039 = 1.5.11.6.7
 461      113983 = 5.5.11.6.7
 462      176191 = 8.5.11.6.7
 463      196927 = 9.5.11.6.7
 464       46591 = 2.2.11.6.7
 465      108799 = 5.2.11.6.7
 466      171007 = 8.2.11.6.7
 467      212479 = 10.2.11.6.7
 468       65599 = 3.1.11.6.7
 469      107071 = 5.1.11.6.7
 470      127807 = 6.1.11.6.7
 471       54799 = 2.7.8.6.7
 472      137743 = 6.7.8.6.7
 473      220687 = 10.7.8.6.7
 474       51343 = 2.5.8.6.7
 475      134287 = 6.5.8.6.7
 476      175759 = 8.5.8.6.7
 477      237967 = 11.5.8.6.7
 478       39103 = 1.10.7.6.7
 479       75391 = 3.7.7.6.7
 480      199807 = 9.7.7.6.7
 481      220543 = 10.7.7.6.7
 482       47743 = 2.3.7.6.7
 483      130687 = 6.3.7.6.7
 484      151423 = 7.3.7.6.7
 485      161071 = 7.9.2.6.7
 486       91951 = 4.5.2.6.7
 487      112687 = 5.5.2.6.7
 488      154159 = 7.5.2.6.7
 489       86767 = 4.2.2.6.7
 490      128239 = 6.2.2.6.7
 491      231919 = 11.2.2.6.7
 492       60703 = 2.11.1.6.7
 493       81439 = 3.11.1.6.7
 494       29599 = 1.5.1.6.7
 495       91807 = 4.5.1.6.7
 496      112543 = 5.5.1.6.7
 497      133279 = 6.5.1.6.7
 498      150559 = 7.3.1.6.7
 499      209311 = 10.1.1.6.7
 500      230047 = 11.1.1.6.7
 501       49171 = 2.4.5.5.7
 502      152851 = 7.4.5.5.7
 503      194323 = 9.4.5.5.7
 504       24979 = 1.2.5.5.7
 505       87187 = 4.2.5.5.7
 506      107923 = 5.2.5.5.7
 507      128659 = 6.2.5.5.7
 508      178627 = 8.7.4.5.7
 509       92227 = 4.5.4.5.7
 510      195907 = 9.5.4.5.7
 511      237379 = 11.5.4.5.7
 512       88771 = 4.3.4.5.7
 513      109507 = 5.3.4.5.7
 514      150979 = 7.3.4.5.7
 515      233923 = 11.3.4.5.7
 516      149251 = 7.2.4.5.7
 517      169987 = 8.2.4.5.7
 518       64579 = 3.1.4.5.7
 519      230467 = 11.1.4.5.7
 520      102451 = 4.11.3.5.7
 521      247603 = 11.11.3.5.7
 522       35059 = 1.8.3.5.7
 523      138739 = 6.8.3.5.7
 524      180211 = 8.8.3.5.7
 525      242419 = 11.8.3.5.7
 526       93811 = 4.6.3.5.7
 527      114547 = 5.6.3.5.7
 528      135283 = 6.6.3.5.7
 529      156019 = 7.6.3.5.7
 530      218227 = 10.6.3.5.7
 531       48883 = 2.4.3.5.7
 532      111091 = 5.4.3.5.7
 533      152563 = 7.4.3.5.7
 534      214771 = 10.4.3.5.7
 535       67891 = 3.3.3.5.7
 536      109363 = 5.3.3.5.7
 537      130099 = 6.3.3.5.7
 538      171571 = 8.3.3.5.7
 539      192307 = 9.3.3.5.7
 540      213043 = 10.3.3.5.7
 541      164371 = 7.11.1.5.7
 542       58963 = 2.10.1.5.7
 543       79699 = 3.10.1.5.7
 544      121171 = 5.10.1.5.7
 545      141907 = 6.10.1.5.7
 546      245587 = 11.10.1.5.7
 547       36187 = 1.8.11.3.7
 548       56923 = 2.8.11.3.7
 549       77659 = 3.8.11.3.7
 550      119131 = 5.8.11.3.7
 551      160603 = 7.8.11.3.7
 552       75931 = 3.7.11.3.7
 553       96667 = 4.7.11.3.7
 554      138139 = 6.7.11.3.7
 555      221083 = 10.7.11.3.7
 556      113947 = 5.5.11.3.7
 557      134683 = 6.5.11.3.7
 558      238363 = 11.5.11.3.7
 559      195163 = 9.4.11.3.7
 560      215899 = 10.4.11.3.7
 561       56779 = 2.8.10.3.7
 562       98251 = 4.8.10.3.7
 563      243403 = 11.8.10.3.7
 564       37339 = 1.9.7.3.7
 565      120283 = 5.9.7.3.7
 566      203227 = 9.9.7.3.7
 567      223963 = 10.9.7.3.7
 568      116827 = 5.7.7.3.7
 569       90907 = 4.4.7.3.7
 570      173851 = 8.4.7.3.7
 571       25243 = 1.2.7.3.7
 572       45979 = 2.2.7.3.7
 573      108187 = 5.2.7.3.7
 574      128923 = 6.2.7.3.7
 575      211867 = 10.2.7.3.7
 576      118411 = 5.8.6.3.7
 577       33739 = 1.7.6.3.7
 578       75211 = 3.7.6.3.7
 579       95947 = 4.7.6.3.7
 580      113227 = 5.5.6.3.7
 581      133963 = 6.5.6.3.7
 582      154699 = 7.5.6.3.7
 583      196171 = 9.5.6.3.7
 584       47563 = 2.3.6.3.7
 585      151243 = 7.3.6.3.7
 586      234187 = 11.3.6.3.7
 587       66571 = 3.2.6.3.7
 588      211723 = 10.2.6.3.7
 589      232459 = 11.2.6.3.7
 590       31723 = 1.6.4.3.7
 591      135403 = 6.6.4.3.7
 592      156139 = 7.6.4.3.7
 593      209707 = 10.1.4.3.7
 594      133387 = 6.5.2.3.7
 595      174859 = 8.5.2.3.7
 596      237067 = 11.5.2.3.7
 597       90187 = 4.4.2.3.7
 598      110923 = 5.4.2.3.7
 599      214603 = 10.4.2.3.7
 600      103423 = 4.11.10.2.7
 601       34303 = 1.7.10.2.7
 602      137983 = 6.7.10.2.7
 603      200191 = 9.7.10.2.7
 604      241663 = 11.7.10.2.7
 605       74047 = 3.6.10.2.7
 606      198463 = 9.6.10.2.7
 607      238207 = 11.5.10.2.7
 608       79087 = 3.9.9.2.7
 609       99823 = 4.9.9.2.7
 610      224239 = 10.9.9.2.7
 611       30703 = 1.5.9.2.7
 612       51439 = 2.5.9.2.7
 613      113647 = 5.5.9.2.7
 614      155119 = 7.5.9.2.7
 615      108463 = 5.2.9.2.7
 616       61519 = 2.11.7.2.7
 617      123727 = 5.11.7.2.7
 618      227407 = 10.11.7.2.7
 619       51151 = 2.5.7.2.7
 620       71887 = 3.5.7.2.7
 621       92623 = 4.5.7.2.7
 622      113359 = 5.5.7.2.7
 623      196303 = 9.5.7.2.7
 624       28687 = 1.4.7.2.7
 625      132367 = 6.4.7.2.7
 626      173839 = 8.4.7.2.7
 627       85711 = 4.1.7.2.7
 628      147919 = 7.1.7.2.7
 629      189391 = 9.1.7.2.7
 630      210127 = 10.1.7.2.7
 631      230863 = 11.1.7.2.7
 632       61231 = 2.11.5.2.7
 633       81967 = 3.11.5.2.7
 634      123439 = 5.11.5.2.7
 635      164911 = 7.11.5.2.7
 636      206383 = 9.11.5.2.7
 637       73327 = 3.6.5.2.7
 638       94063 = 4.6.5.2.7
 639      114799 = 5.6.5.2.7
 640      177007 = 8.6.5.2.7
 641      218479 = 10.6.5.2.7
 642      154543 = 7.5.5.2.7
 643      216751 = 10.5.5.2.7
 644      237487 = 11.5.5.2.7
 645       55903 = 2.8.4.2.7
 646      137119 = 6.7.4.2.7
 647      220063 = 10.7.4.2.7
 648      109471 = 5.3.4.2.7
 649      171679 = 8.3.4.2.7
 650       60943 = 2.11.3.2.7
 651      164623 = 7.11.3.2.7
 652      185359 = 8.11.3.2.7
 653       31567 = 1.6.3.2.7
 654       73039 = 3.6.3.2.7
 655      218191 = 10.6.3.2.7
 656      133519 = 6.5.3.2.7
 657      174991 = 8.5.3.2.7
 658       47119 = 2.3.3.2.7
 659       88591 = 4.3.3.2.7
 660      192271 = 9.3.3.2.7
 661      233743 = 11.3.3.2.7
 662      107599 = 5.2.3.2.7
 663      190543 = 9.2.3.2.7
 664       37747 = 1.9.10.1.7
 665      120691 = 5.9.10.1.7
 666      182899 = 8.9.10.1.7
 667      245107 = 11.9.10.1.7
 668       32563 = 1.6.10.1.7
 669       53299 = 2.6.10.1.7
 670       94771 = 4.6.10.1.7
 671      156979 = 7.6.10.1.7
 672      219187 = 10.6.10.1.7
 673       72307 = 3.5.10.1.7
 674      113779 = 5.5.10.1.7
 675      155251 = 7.5.10.1.7
 676       86131 = 4.1.10.1.7
 677      106867 = 5.1.10.1.7
 678      148339 = 7.1.10.1.7
 679      122131 = 5.10.8.1.7
 680      142867 = 6.10.8.1.7
 681       96211 = 4.7.8.1.7
 682      158419 = 7.7.8.1.7
 683      241363 = 11.7.8.1.7
 684       51283 = 2.5.8.1.7
 685       72019 = 3.5.8.1.7
 686      134227 = 6.5.8.1.7
 687      175699 = 8.5.8.1.7
 688       40627 = 1.11.6.1.7
 689       61363 = 2.11.6.1.7
 690      144307 = 6.11.6.1.7
 691      227251 = 10.11.6.1.7
 692       95923 = 4.7.6.1.7
 693      199603 = 9.7.6.1.7
 694       73459 = 3.6.6.1.7
 695      218611 = 10.6.6.1.7
 696      239347 = 11.6.6.1.7
 697      130483 = 6.3.6.1.7
 698      149491 = 7.2.6.1.7
 699      170227 = 8.2.6.1.7
 700       76771 = 3.8.5.1.7
 701      242659 = 11.8.5.1.7
 702       88867 = 4.3.5.1.7
 703      171811 = 8.3.5.1.7
 704      192547 = 9.3.5.1.7
 705       23203 = 1.1.5.1.7
 706       85411 = 4.1.5.1.7
 707      230563 = 11.1.5.1.7
 708       57331 = 2.9.2.1.7
 709      223219 = 10.9.2.1.7
 710       69427 = 3.4.2.1.7
 711       90163 = 4.4.2.1.7
 712      110899 = 5.4.2.1.7
 713      121123 = 5.10.1.1.7
 714      204067 = 9.10.1.1.7
 715       31267 = 1.6.1.1.7
 716       72739 = 3.6.1.1.7
 717      134947 = 6.6.1.1.7
 718      176419 = 8.6.1.1.7
 719      238627 = 11.6.1.1.7
 720       71011 = 3.5.1.1.7
 721      195427 = 9.5.1.1.7
 722       26083 = 1.3.1.1.7
 723       46819 = 2.3.1.1.7
 724      129763 = 6.3.1.1.7
 725       65657 = 3.1.11.11.5
 726      210809 = 10.1.11.11.5
 727       41177 = 1.11.9.11.5
 728      124121 = 5.11.9.11.5
 729      248537 = 11.11.9.11.5
 730      122393 = 5.10.9.11.5
 731      246809 = 11.10.9.11.5
 732       32537 = 1.6.9.11.5
 733      136217 = 6.6.9.11.5
 734       87833 = 4.2.9.11.5
 735      150041 = 7.2.9.11.5
 736      170777 = 8.2.9.11.5
 737      165449 = 7.11.8.11.5
 738       53129 = 2.6.8.11.5
 739      115337 = 5.6.8.11.5
 740      198281 = 9.6.8.11.5
 741      219017 = 10.6.8.11.5
 742      239753 = 11.6.8.11.5
 743      155081 = 7.5.8.11.5
 744       89417 = 4.3.8.11.5
 745      213833 = 10.3.8.11.5
 746       25679 = 1.2.10.3.11
 747       87887 = 4.2.10.3.11
 748       28559 = 1.4.6.3.11
 749      215183 = 10.4.6.3.11
 750      235919 = 11.4.6.3.11
 751      133967 = 6.5.6.3.11
 752      216911 = 10.5.6.3.11
 753      177167 = 8.6.6.3.11
 754      116687 = 5.7.6.3.11
 755       59663 = 2.10.6.3.11
 756      142607 = 6.10.6.3.11
 757      206543 = 9.11.6.3.11
 758       22943 = 1.1.3.3.11
 759      188831 = 9.1.3.3.11
 760      209567 = 10.1.3.3.11
 761      230303 = 11.1.3.3.11
 762       31583 = 1.6.3.3.11
 763      238943 = 11.6.3.3.11
 764       76511 = 3.8.3.3.11
 765      200927 = 9.8.3.3.11
 766      242399 = 11.8.3.3.11
 767      131519 = 6.4.1.3.11
 768      193727 = 9.4.1.3.11
 769      214463 = 10.4.1.3.11
 770      235199 = 11.4.1.3.11
 771       29567 = 1.5.1.3.11
 772       71039 = 3.5.1.3.11
 773       72767 = 3.6.1.3.11
 774       93503 = 4.6.1.3.11
 775       58943 = 2.10.1.3.11
 776      121151 = 5.10.1.3.11
 777      162623 = 7.10.1.3.11
 778      224831 = 10.10.1.3.11
 779       27527 = 1.3.11.1.11
 780       30983 = 1.5.11.1.11
 781       51719 = 2.5.11.1.11
 782      155399 = 7.5.11.1.11
 783      196871 = 9.5.11.1.11
 784       58631 = 2.9.11.1.11
 785       79367 = 3.9.11.1.11
 786      100103 = 4.9.11.1.11
 787      183047 = 8.9.11.1.11
 788       70439 = 3.4.9.1.11
 789      132647 = 6.4.9.1.11
 790       37607 = 1.9.9.1.11
 791      120551 = 5.9.9.1.11
 792      165479 = 7.11.9.1.11
 793      206951 = 9.11.9.1.11
 794       73607 = 3.6.7.1.11
 795       94343 = 4.6.7.1.11
 796      115079 = 5.6.7.1.11
 797       33863 = 1.7.7.1.11
 798      199751 = 9.7.7.1.11
 799       39047 = 1.10.7.1.11
 800      184199 = 8.10.7.1.11
 801      225671 = 10.10.7.1.11
 802      116663 = 5.7.6.1.11
 803      137399 = 6.7.6.1.11
 804      241079 = 11.7.6.1.11
 805      130343 = 6.3.5.1.11
 806      213287 = 10.3.5.1.11
 807       40487 = 1.11.5.1.11
 808       61223 = 2.11.5.1.11
 809      144167 = 6.11.5.1.11
 810      227111 = 10.11.5.1.11
 811      247847 = 11.11.5.1.11
 812      130199 = 6.3.4.1.11
 813      171671 = 8.3.4.1.11
 814      192407 = 9.3.4.1.11
 815      233879 = 11.3.4.1.11
 816      112919 = 5.5.4.1.11
 817      195863 = 9.5.4.1.11
 818       35159 = 1.8.4.1.11
 819       76631 = 3.8.4.1.11
 820       97367 = 4.8.4.1.11
 821      180311 = 8.8.4.1.11
 822      242519 = 11.8.4.1.11
 823       86711 = 4.2.2.1.11
 824      190391 = 9.2.2.1.11
 825       50423 = 2.5.2.1.11
 826       81527 = 3.11.2.1.11
 827      164471 = 7.11.2.1.11
 828       24359 = 1.2.1.1.11
 829       65831 = 3.2.1.1.11
 830      231719 = 11.2.1.1.11
 831       67559 = 3.3.1.1.11
 832      150503 = 7.3.1.1.11
 833       90023 = 4.4.1.1.11
 834      152231 = 7.4.1.1.11
 835      193703 = 9.4.1.1.11
 836      214439 = 10.4.1.1.11
 837       32999 = 1.7.1.1.11
 838       74471 = 3.7.1.1.11
 839      178151 = 8.7.1.1.11
 840      191803 = 9.2.11.11.7
 841      110587 = 5.3.11.11.7
 842      235003 = 11.3.11.11.7
 843       41467 = 1.11.11.11.7
 844       82939 = 3.11.11.11.7
 845      165883 = 7.11.11.11.7
 846      186619 = 8.11.11.11.7
 847      248827 = 11.11.11.11.7
 848       24043 = 1.1.10.11.7
 849      193387 = 9.3.10.11.7
 850       60331 = 2.10.10.11.7
 851      164011 = 7.10.10.11.7
 852      205483 = 9.10.10.11.7
 853       44491 = 2.1.8.11.7
 854      106699 = 5.1.8.11.7
 855      148171 = 7.1.8.11.7
 856      189643 = 9.1.8.11.7
 857       72139 = 3.5.8.11.7
 858      155083 = 7.5.8.11.7
 859       37579 = 1.9.8.11.7
 860       99787 = 4.9.8.11.7
 861      244939 = 11.9.8.11.7
 862      192667 = 9.3.5.11.7
 863      234139 = 11.3.5.11.7
 864       35419 = 1.8.5.11.7
 865      201307 = 9.8.5.11.7
 866      222043 = 10.8.5.11.7
 867      242779 = 11.8.5.11.7
 868      120091 = 5.9.5.11.7
 869      140827 = 6.9.5.11.7
 870      161563 = 7.9.5.11.7
 871      244507 = 11.9.5.11.7
 872       61339 = 2.11.5.11.7
 873      102811 = 4.11.5.11.7
 874      123547 = 5.11.5.11.7
 875       24763 = 1.2.3.11.7
 876      121531 = 5.10.3.11.7
 877      163003 = 7.10.3.11.7
 878      105691 = 5.1.1.11.7
 879      147163 = 7.1.1.11.7
 880      167899 = 8.1.1.11.7
 881      209371 = 10.1.1.11.7
 882      230107 = 11.1.1.11.7
 883      148891 = 7.2.1.11.7
 884      169627 = 8.2.1.11.7
 885       91867 = 4.5.1.11.7
 886      112603 = 5.5.1.11.7
 887      237019 = 11.5.1.11.7
 888       31387 = 1.6.1.11.7
 889       72859 = 3.6.1.11.7
 890      238747 = 11.6.1.11.7
 891       74587 = 3.7.1.11.7
 892       34843 = 1.8.1.11.7
 893       55579 = 2.8.1.11.7
 894      117787 = 5.8.1.11.7
 895      200731 = 9.8.1.11.7
 896       25759 = 1.2.10.10.7
 897       67231 = 3.2.10.10.7
 898      129439 = 6.2.10.10.7
 899      212383 = 10.2.10.10.7
 900      243487 = 11.8.10.10.7
 901       48079 = 2.3.9.10.7
 902      131023 = 6.3.9.10.7
 903      144847 = 6.11.9.10.7
 904       28927 = 1.4.8.10.7
 905       49663 = 2.4.8.10.7
 906      111871 = 5.4.8.10.7
 907      132607 = 6.4.8.10.7
 908      153343 = 7.4.8.10.7
 909      174079 = 8.4.8.10.7
 910      236287 = 11.4.8.10.7
 911       37567 = 1.9.8.10.7
 912       79039 = 3.9.8.10.7
 913      120511 = 5.9.8.10.7
 914      161983 = 7.9.8.10.7
 915       41023 = 1.11.8.10.7
 916      103231 = 4.11.8.10.7
 917      206911 = 9.11.8.10.7
 918       64927 = 3.1.6.10.7
 919       25183 = 1.2.6.10.7
 920      108127 = 5.2.6.10.7
 921      191071 = 9.2.6.10.7
 922       30367 = 1.5.6.10.7
 923      134047 = 6.5.6.10.7
 924      175519 = 8.5.6.10.7
 925      216991 = 10.5.6.10.7
 926      147151 = 7.1.1.10.7
 927      167887 = 8.1.1.10.7
 928      209359 = 10.1.1.10.7
 929      231823 = 11.2.1.10.7
 930      114319 = 5.6.1.10.7
 931       36559 = 1.9.1.10.7
 932       78031 = 3.9.1.10.7
 933      119503 = 5.9.1.10.7
 934      181711 = 8.9.1.10.7
 935       38287 = 1.10.1.10.7
 936       59023 = 2.10.1.10.7
 937      162703 = 7.10.1.10.7
 938      183439 = 8.10.1.10.7
 939      224911 = 10.10.1.10.7
 940       69539 = 3.4.2.10.11
 941      173219 = 8.4.2.10.11
 942      214691 = 10.4.2.10.11
 943       92003 = 4.5.2.10.11
 944      154211 = 7.5.2.10.11
 945       97187 = 4.8.2.10.11
 946      200867 = 9.8.2.10.11
 947      221603 = 10.8.2.10.11
 948       78179 = 3.9.2.10.11
 949      161123 = 7.9.2.10.11
 950      223331 = 10.9.2.10.11
 951       40163 = 1.11.2.10.11
 952       60899 = 2.11.2.10.11
 953      206051 = 9.11.2.10.11
 954       45491 = 2.2.3.10.11
 955      107699 = 5.2.3.10.11
 956       71411 = 3.5.3.10.11
 957       95603 = 4.7.3.10.11
 958      220019 = 10.7.3.10.11
 959      159539 = 7.8.3.10.11
 960      201011 = 9.8.3.10.11
 961      221747 = 10.8.3.10.11
 962      242483 = 11.8.3.10.11
 963       61043 = 2.11.3.10.11
 964       23747 = 1.1.8.10.11
 965       44483 = 2.1.8.10.11
 966      168899 = 8.1.8.10.11
 967      231107 = 11.1.8.10.11
 968       92867 = 4.5.8.10.11
 969      134339 = 6.5.8.10.11
 970      175811 = 8.5.8.10.11
 971      238019 = 11.5.8.10.11
 972      118787 = 5.8.8.10.11
 973      201731 = 9.8.8.10.11
 974      243203 = 11.8.8.10.11
 975       30803 = 1.5.9.10.11
 976       51539 = 2.5.9.10.11
 977      155219 = 7.5.9.10.11
 978      238163 = 11.5.9.10.11
 979       34259 = 1.7.9.10.11
 980       75731 = 3.7.9.10.11
 981      117203 = 5.7.9.10.11
 982      179411 = 8.7.9.10.11
 983       58451 = 2.9.9.10.11
 984       79187 = 3.9.9.10.11
 985       99923 = 4.9.9.10.11
 986      182867 = 8.9.9.10.11
 987       44771 = 2.1.10.10.11
 988       86243 = 4.1.10.10.11
 989      106979 = 5.1.10.10.11
 990      210659 = 10.1.10.10.11
 991       51683 = 2.5.10.10.11
 992      113891 = 5.5.10.10.11
 993      238307 = 11.5.10.10.11
 994       53411 = 2.6.10.10.11
 995      141539 = 6.9.10.10.11
 996       43451 = 2.1.1.8.11
 997       64187 = 3.1.1.8.11
 998      188603 = 9.1.1.8.11
 999       33083 = 1.7.1.8.11
1000       53819 = 2.7.1.8.11
1001      116027 = 5.7.1.8.11
1002      198971 = 9.7.1.8.11
1003      219707 = 10.7.1.8.11
1004      102203 = 4.11.1.8.11
1005      122939 = 5.11.1.8.11
1006      205883 = 9.11.1.8.11
1007      126827 = 6.1.4.8.11
1008      209771 = 10.1.4.8.11
1009      230507 = 11.1.4.8.11
1010       66347 = 3.2.4.8.11
1011       87083 = 4.2.4.8.11
1012      190763 = 9.2.4.8.11
1013      211499 = 10.2.4.8.11
1014       47339 = 2.3.4.8.11
1015       88811 = 4.3.4.8.11
1016      109547 = 5.3.4.8.11
1017       30059 = 1.5.4.8.11
1018      175211 = 8.5.4.8.11
1019       66491 = 3.2.5.8.11
1020      211643 = 10.2.5.8.11
1021       68219 = 3.3.5.8.11
1022      151163 = 7.3.5.8.11
1023       30203 = 1.5.5.8.11
1024      113147 = 5.5.5.8.11
1025      154619 = 7.5.5.8.11
1026      237563 = 11.5.5.8.11
1027      137339 = 6.7.5.8.11
1028       44171 = 2.1.6.8.11
1029       85643 = 4.1.6.8.11
1030       28619 = 1.4.6.8.11
1031      132299 = 6.4.6.8.11
1032      194507 = 9.4.6.8.11
1033      235979 = 11.4.6.8.11
1034       59723 = 2.10.6.8.11
1035      121931 = 5.10.6.8.11
1036      163403 = 7.10.6.8.11
1037      225611 = 10.10.6.8.11
1038      206603 = 9.11.6.8.11
1039       70379 = 3.4.8.8.11
1040      215531 = 10.4.8.8.11
1041       77291 = 3.8.8.8.11
1042       37547 = 1.9.8.8.11
1043      224171 = 10.9.8.8.11
1044       80747 = 3.10.8.8.11
1045      101483 = 4.10.8.8.11
1046      122219 = 5.10.8.8.11
1047       91811 = 4.5.1.6.11
1048      133283 = 6.5.1.6.11
1049       74531 = 3.7.1.6.11
1050       95267 = 4.7.1.6.11
1051      136739 = 6.7.1.6.11
1052      219683 = 10.7.1.6.11
1053       76259 = 3.8.1.6.11
1054      117731 = 5.8.1.6.11
1055      179939 = 8.8.1.6.11
1056      221411 = 10.8.1.6.11
1057      242147 = 11.8.1.6.11
1058      130259 = 6.3.4.6.11
1059      213203 = 10.3.4.6.11
1060      233939 = 11.3.4.6.11
1061       93971 = 4.6.4.6.11
1062      197651 = 9.6.4.6.11
1063       80147 = 3.10.4.6.11
1064      204563 = 9.10.4.6.11
1065      225299 = 10.10.4.6.11
1066      130547 = 6.3.6.6.11
1067      213491 = 10.3.6.6.11
1068       30323 = 1.5.6.6.11
1069       51059 = 2.5.6.6.11
1070      216947 = 10.5.6.6.11
1071      237683 = 11.5.6.6.11
1072       95987 = 4.7.6.6.11
1073      178931 = 8.7.6.6.11
1074      220403 = 10.7.6.6.11
1075       35507 = 1.8.6.6.11
1076      139187 = 6.8.6.6.11
1077      242867 = 11.8.6.6.11
1078       65027 = 3.1.7.6.11
1079       87491 = 4.2.7.6.11
1080      232643 = 11.2.7.6.11
1081       33923 = 1.7.7.6.11
1082      116867 = 5.7.7.6.11
1083      199811 = 9.7.7.6.11
1084       39107 = 1.10.7.6.11
1085      122051 = 5.10.7.6.11
1086      142787 = 6.10.7.6.11
1087      184259 = 8.10.7.6.11
1088      148403 = 7.1.10.6.11
1089      231347 = 11.1.10.6.11
1090      113843 = 5.5.10.6.11
1091      176051 = 8.5.10.6.11
1092      158771 = 7.7.10.6.11
1093      101747 = 4.10.10.6.11
1094      205427 = 9.10.10.6.11
1095      246899 = 11.10.10.6.11
1096       34499 = 1.7.11.6.11
1097      117443 = 5.7.11.6.11
1098      138179 = 6.7.11.6.11
1099      179651 = 8.7.11.6.11
1100      101891 = 4.10.11.6.11
1101      226307 = 10.10.11.6.11
1102      105767 = 5.1.2.5.11
1103      188711 = 9.1.2.5.11
1104       91943 = 4.5.2.5.11
1105       55799 = 2.8.3.5.11
1106      225143 = 10.10.3.5.11
1107       49031 = 2.4.4.5.11
1108       69767 = 3.4.4.5.11
1109       33479 = 1.7.4.5.11
1110      116423 = 5.7.4.5.11
1111       87623 = 4.2.8.5.11
1112      108359 = 5.2.8.5.11
1113      212039 = 10.2.8.5.11
1114       39239 = 1.10.8.5.11
1115      246599 = 11.10.8.5.11
1116       61703 = 2.11.8.5.11
1117      123911 = 5.11.8.5.11
1118      165383 = 7.11.8.5.11
1119      186119 = 8.11.8.5.11
1120       48023 = 2.3.9.5.11
1121      151703 = 7.3.9.5.11
1122      172439 = 8.3.9.5.11
1123       51479 = 2.5.9.5.11
1124       92951 = 4.5.9.5.11

Comparisons

The Fortran version checks for possible factors up to 2800 by bignumber division before it starts on the MR process. Dinosaur (talk) 06:11, 9 April 2017 (UTC)

One of the purposes of this task is to highlight problems with primality testing of a large number of large numbers. If you are using MR these are twofold: first being able to randomly select prime numbers fairly across the range 3 to the large number; second the number of prime numbers you are going to try. In the worst case for a single trial there is a 1 in 4 (usual case more like 1 in 50) chance that the large number is actually composite. This chance rapidly decreases with trials, but so does the time taken. So the recommendation is to do quick trials allowing some non prime candidates to be propagated, then a thorough check of your final candidate(s) that it is indeed a left truncatable prime.--Nigel Galloway (talk) 11:55, 9 April 2017 (UTC)

Indeed. An earlier version accidentally used a parameter BIGMRTRIALS instead of what I intended for the upper bound of direct division trials, 2800 (eventually chosen after some ad-hoc timing as resulting in faster runs than with say 3000 or 1500), and with a value of six, this meant that only 2, 3, and 5 were tested as possible factors by direct division. All else was via the MR test and so far, this provided the only occasion when a denunciation of "composite" did not occur in the first MR trial, though only for a few dozen out of a quarter of a million trials. With trial factors up to 2800 or so, all denunciations were made on the first MR trial: 517641 trials rejecting 282261 in the first go, and accepting 235380 in all of the second to sixth trials. This suggests that "no comment" from a MR trial might be more likely for numbers having a small prime factor, however, I'm sure this question has been investigated more thoroughly than that. So, in this case, as the horde of candidates is being produced then trimmed one MR trial would have sufficed, but this is hindsight.

Allowing a few extra (but wrong) candidates during the marshalling by avoiding repeated MR tests would save time that could be spent on more heavily testing the final few survivors, however, remember that the process is to produce not just a final number that is prime, but one that also is prime at each of its earlier stages. In other words, suppose a non-prime is admitted at say the five-digit level, and at the end (with say seven digits), some of its descendants may survive and turn out to be primes and possibly even the largest survivor. But alas, not all of its left-truncations (to six, five, four, etc. digits) would be primes.

Routine BIGMRPRIME does not try to be general and produce tests using the range [2:N - 1] for a bignumber N because of the nuisances of bignumber arithmetic when the number is big, just an ad-hoc trick with an upper bound of N1 = min(N - 1,20000000) then selecting A1 via pseudo-random function RAND into the range [2,N1] - with vexation since RAND can deliver 1 as its result. In other words, the full range of A1 in [2,N - 1] is not available for numbers above twenty million, but they seemed to work well enough that I didn't bother with yet more routines for bignumber arithmetic to handle this properly. Incidentally, the Miller–Rabin_primality_test page quotes two as the lower bound for A1, not three. A value of two in a binary computer could enable shortcuts in the calculations, for a faster initial trial before continuing with the full range of possibilities for A1. Somewhere I saw some remarks that certain trial values of A1 give definite results for N up to ... except that I didn't look closely. There might even be a collection of special values that are particularly effective at denouncing composite numbers, rather than floundering about with "random" choices... Dinosaur (talk) 12:02, 10 April 2017 (UTC)

Odd base optimization

Sadly 24 is not odd, but for bases which are:

Note that all stems greater than 2 are odd.

Prepending an odd number to the stem makes a new even candidate stem, which can not be prime.

Therefore it is only necessary to consider cases where the number prepended to the stem is even.

For 2 the situation is the reverese. --Nigel Galloway 12:27, 10 December 2012 (UTC)