6 ms·
Left Truncatable Prime
- Terr_ 9y agoWhen written in base 10, anyway :) I suppose an extra challenge would be to find values which are truncatable primes in more than one base at once... Hmmm.
- theophrastus 9y agoIt's often worthy to first check the OEIS[1] prior to committing a large number of cpu cycles to the effort. [1] https://oeis.org/search?q=left+truncatable+primes+base&sort=&language=english&go=Search https://oeis.org/search?q=left+truncatable+primes+base&sort=...
- kmm 9y agoI wonder why base 24 is such an extreme outlier. I had noticed it already when I was playing with this concept in Mathematica, it's the only one I couldn't exhaustively search.
- madcaptenor 9y agoThese primes can be built up right to left, and the last "digit" of a prime, mod 24, can only take on phi(24) = 8 different values. (phi is Euler's phi function here.) So when you're considering adding on a digit (base 24) to the left of a prime, the chances of getting a prime are relatively high, since the last digit is already stacked in your favor. Notice that for example that sequence is really small when n is prime, because you don't get that same advantage. To get a lot of left truncatable primes you want your base n to be large (so you have a lot of choices at each step of the search) and you want phi(n)/n to be small (so you can stack the deck in your favor on the last digit). And why does the sequence stop at 29? phi(30) = 8, setting a new minimum for phi(n)/n.
- moomin 9y agoAFAICT, The code would never find a prime of the form 100p
- detaro 9y agoAFAIK zeros aren't allowed in truncatable primes.
- ColinWright 9y agoLeading zeros are generally not allowed, so if you had, say 503, then that's prime, 3 is prime, but 03 isn't allowed.
- moomin 9y agoOkay, I’m getting confused because the code does test for 10p.
- ColinWright 9y agoI don't think it does. Are you aware that "range(1,10)" in Python is the list [1, 2, 3, 4, 5, 6, 7, 8, 9] ?? Ranges in Python don't include their endpoint. A few people have expressed confusion as to this choice in the design, but it means that the expression: range(a,b) + range(b,c) + range(c,d) includes everything from a to d-1 one and only once. Knuth said that intervals should include the initial point and not the endpoint for this reason.
- moomin 9y agoAaaah. Makes sense.
- mclehman 9y agoThis issue is one of the things Perl 6 addresses well in my opinion. Regular ranges include their endpoints, and you can think of ^ as "not including" or "up to (exclusive)" 1..5 is 1, 2, 3, 4, 5 1..^5 is 1, 2, 3, 4 1^..5 is 2, 3, 4, 5 1^..^5 is 2, 3, 4 There's also convenient shorthand for 0..^n (useful if you want to do something n times): ^n
- tzs 9y agoI wonder how long one could be if we only require it to stay prime when it has more than K digits? Take K=0 to get the original problem. In this form of the problem, it is not the length, L, of the initial prime that we want to maximize but rather L-K. My guess is that these looser requirements won't make much difference. Estimating based on the prime number theorem and pretending that primes are essentially random numbers (an assumption that works remarkably well a large fraction of the time), I get, if I didn't totally botch it, that given a k digit integer that is prime, there is about a 1/(2k) chance that you can add a digit on the left and still have a prime. Another generalization comes to mind. Suppose that instead of a pencil, we are dealing with some item with break-away segment. Each segment has d digits printed on it, so when we have L segments we have a dL digit number. As we break away segments we left truncate this number by d digits. I don't think that would make much of a difference. We can treat it as an L digit number in base 10^d, which we truncate a digit at a time. Another hand wavy application of prime number theorem gives 1/(2kd) as the chance that you can left-extend a k digit base 10^d prime by one digit and get a prime.
- Stratoscope 9y agoThe article mentions a "DON'T DO DRUGS" pencil. The actual pencil, distributed in 1998 by the Bureau for At-Risk Youth, was even funnier. It said "TOO COOL TO DO DRUGS", and apparently the company had no clue what would happen as you sharpened it: ◄ TOO COOL TO DO DRUGS ◄ COOL TO DO DRUGS ◄ DO DRUGS ◄ DRUGS http://www.nytimes.com/1998/12/12/nyregion/slogan-causes-pencil-recall.html http://www.nytimes.com/1998/12/12/nyregion/slogan-causes-pen... Someone has even done a remake of the pencil: http://shop.brrybnds.com/product/cool-to-do-drugs-pencil http://shop.brrybnds.com/product/cool-to-do-drugs-pencil
- ColinWright 9y agoThank you! I'll edit the post. (edit) Now edited - thanks again.
- tedunangst 9y agoLinking to the HN front page as a reference won't be of much use, even only a few hours from now.
- ColinWright 9y agoThe link to the front page is the reference to Hacker News in general, not to this specific item. I never intended to link to the specific reference, although I can see why people might think it's relevant. I mentioned the person with a link to their profile, I linked to the forum in general, and I quoted/paraphrased the relevant information. I wouldn't think anything more was needed.
- Stratoscope 9y agoI certainly wasn't offended by not having a link to the specific comment. Heck, I didn't even expect a mention of my nom de bit. I was just happy to be able to help you make a fun story even more fun! ◄ TOO COOL TO CARE ABOUT LINKS ◄ COOL TO CARE ABOUT LINKS ◄ CARE ABOUT LINKS ◄ LINKS
- epx 9y agoThe primality test uses Fermat's Little Theorem, but I thought it was not 100% perfect. (Or perhaps it is for left-truncatable primes?) I didn't know about the third parameter in pow(), either. Quite interesting.
- CarolineW 9y agoIt's good enough for smallish primes, especially when you use multiple bases. There aren't many Carmichael numbers, and the early ones all have a small factor. So the test is certainly adequate in this range.
- ColinWright 9y agoIt's not perfect, but it's fast, easy to code, and the first false positive for this version is a long way out. Early Carmichael numbers have small factors, and although I'm only testing against prime bases up to 19, I'm not sure where the first false positive is. But it's a long way further out than the numbers we're dealing with here. I should go looking ...
- svat 9y agoHere are the first ten false positives for the is_prime function in the post, along with their factors: 252601: 41 61 101 294409: 37 73 109 399001: 31 61 211 410041: 41 73 137 488881: 37 73 181 512461: 31 61 271 1152271: 43 127 211 1193221: 31 61 631 1461241: 37 73 541 1857241: 31 181 331
- ColinWright 9y agoThanks for that. As it happens it's not a problem because the first 30 all have even digits and so can't be a final segment of a left-truncatable prime, except 7519441, and 441 isn't prime. I could write a more comprehensive test - didn't seem worth it for this case, but it's an interesting exercise. It's easy to extend this test so the list of primes used goes as far as the smallest factor in each of these factorisations, say, 109. Then these would all be correctly identified as composite. It would also be easy to combine it with Pollard Rho or PPP tests, to extend the range before we need to do something more serious. Anyway, here are the first 30 with factorisations 252601 : 41 61 101 294409 : 37 73 109 399001 : 31 61 211 410041 : 41 73 137 488881 : 37 73 181 512461 : 31 61 271 1152271 : 43 127 211 1193221 : 31 61 631 1461241 : 37 73 541 1615681 : 23 199 353 1857241 : 31 181 331 1909001 : 41 101 461 2508013 : 53 79 599 3057601 : 43 211 337 3581761 : 29 113 1093 3828001 : 101 151 251 4335241 : 53 157 521 5049001 : 31 271 601 5148001 : 41 241 521 5444489 : 29 197 953 5481451 : 31 151 1171 5968873 : 43 127 1093 6189121 : 61 241 421 6733693 : 109 163 379 6868261 : 43 211 757 7519441 : 41 241 761 8134561 : 37 109 2017 8927101 : 31 37 43 181 9439201 : 61 271 571 9494101 : 23 61 67 101
- dhbradshaw 9y agoPretty cool. I first learned about truncatable primes from Project Euler problem 37: "Find the sum of the only eleven primes that are both truncatable from left to right and right to left." https://projecteuler.net/problem=37 https://projecteuler.net/problem=37 (I have some rust code that solves this problem in ~300 microseconds on my laptop. I bet it's possible to get it faster though. Anyone want to try?)
- piinbinary 9y agoI'm curious how you got it to even go that fast. My best solution takes about 6 milliseconds, so 20x longer.
- dhbradshaw 9y agoI used a branch and prune algorithm, starting with the 1 digit primes and then adding digits to the right, pruning using a non-memoising prime test and testing for left truncatability to see if the new numbers should be added to the sum. The tree came to an end fairly quickly, which made the algorithm fast. I also avoided any string manipulation, favoring truncating by using integer division for right truncation and modulus for left truncation. Is that similar to your algorithm?
- piinbinary 9y agoAh, I guessed that you might be taking some approach that generated numbers to try. Mine was the brute-force "calculate all primes under a million then test them all" approach.
- Someone 9y agoAs always with this kind of problems (no input, small output, no limit on the amount of mathematical ‘preprocessing’ allowed), the fastest program will just call write to output the sum. That’s why I don’t think speeding up such solutions beyond making it really fast using algorithmic changes/specializations is worthwhile.
- jwilk 9y agohttps://en.wikipedia.org/wiki/Truncatable_prime https://en.wikipedia.org/wiki/Truncatable_prime
- jwilk 9y agoWhat if we allowed 0 as a digit? Are there infinitely many 0-enabled left-truncatable primes?
- ColinWright 9y agoI would guess that there are infinitely many primes of the form 10^k+1. If so, that would be a yes.
- xelxebar 9y agoActually, I believe this is an open problem at them moment. Primes of the form a^n + 1 are called Generalized Fermat Primes and the consensus seems to be that there are probably only finitely many for every base a.
- jwilk 9y agoBut these truncate to 1, which is normally not considered prime.
- ColinWright 9y agoYah, I wrote that without thinking. Replace 1 with 3, and take a.10^k+p with p a small prime, etc.
- svat 9y agoHere is a heuristic argument for why we should expect there to be infinitely many. Suppose we start with a prime p which is d digits long (say p=3 so that d=1), and consider the sequence {a10^k + p : 1≤a≤9, k ≥ d}. So for p=3, we would consider 13, 23, … 93, then 103, 203, … 903, then 1003, 2003, … 9003, etc. By a standard heuristic argument (based on the prime number theorem), the number n is prime with "probability" about 1/log n, so each a10^k + p will be prime with probability about 1/k (ignoring some constant factors). The sum of these probabilities diverges, so one can be very confident that there will be a prime number in this sequence. In other words, we can be extremely confident of the following lemma: given any prime number p, there is a way of extending it to another prime number by adding some digit (followed by 0s) to its left. Repeated applications of this lemma (with any starting prime p, or even different primes p if you wish) will give the result. For example starting with the prime p=3 and taking the first choice each time, you get primes like 30007020009000000000000000600000000900906001600500006000001026001050612113. Of course, turning this heuristic argument from "extremely confident" to an actual proof is a challenge. (There may be ways to prove this, I don't know: I know this heuristic is often used by number theorists though.)
- ianopolous 9y agoIt's fun to see this. I investigated these on my own as an undergrad, but I called them solid primes. Originally I wrote a visual basic program (it was a long time ago) to find all the solid primes in base ten, which obviously involved writing a big num implementation. It ran for three days, only half solved the problem and then ran out of memory. Recoding it in Mathematica took 6 lines, ran in 20 minutes and found all of them. Plotting the distribution gives a nice curve which you can model quite well with the prime number theorem. From memory it looks like x^2*e^-x. Then plotting in different bases is also interesting.