Talk:Find largest left truncatable prime in a given base

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)