4 ms·
Pretty 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 lef
by dhbradshaw 9y ago
Pretty 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.