In number theory, a right-truncatable prime is a prime number which, in a given base, contains no 0, and if the last (“right”) digit is successively removed, then all resulting numbers are prime. 7393 is an example of a right-truncatable prime, since 7393, 739, 73, and 7 are all prime.
In this essay, we’re going to write some code to generate truncatable primes. Along the way, we’ll get some practice working with JavaScript generators implmenting lazily generated lists, we’ll get a chance to look at some of the ways a naïve algorithm might have terrible runtime performance, and we’ll get a chance to explore how pipelining data through functions helps us to separate concerns.
That, and we’ll get a chance to play with an esoteric concept in number theory, truncatable primes. Let’s start with a simple question: Are there an infinite number of truncatable primes? Or is the number of truncatable primes finite?
the infinitude of primes
Now, we know that there are an infinite number of primes. The reductio ad absurdum proof of this is easy to follow along:
To prove that there are an infinite number of primes, we first assume the opposite–that there are a finite number of primes–and then show that this presumption leads to a contradiction.
If there are a finite number of primes, there is some finite list of primes, call them p0, p1, p2, …, pN, where “pN” is the largest prime. Now we know from other work in number theory that every number can be decomposed into a set of prime factors, even primes. The only thing special about primes in this respect is that their only prime factor is themselves.
It follows then that every integer has one or more factors from the list p0, p1, p2, …, pN and only this list. So now let us consider the number p0 times p1 times p2, …, times pN. It is the product of all of the primes, and we will call it pN. This is obviously not a prime. But what about the number pN + 1?
We also know from other work that if some number x is divisible by some prime p, the numbers x + y and x - y are not divisible by p unless y is divisible by p. The most trivial example is when y = 1, because 1 is not divisible by any prime. For example, the number 10 is divisible by 2 and 5, but the numbers 9 and 11 are not divisible by either 2 or 5.
From this, we know that pN* + 1 is not divisible by any prime, be it p0, p1, p2, …, or pN. But that contradicts our knowledge that all numbers have one or more prime factors! So, from this, we conclude that pN* + 1 must be divisible by some prime other than p0, p1, p2, …, pN.
This tells us that any finite list of primes is necessarily incomplete.
Ok, that is middle-school mathematics. What about truncatable primes? Are there an infinite number of them?
are there an infinite number of truncatable primes?
One way to settle this question is with a clever bit of reasoning, like the proof that there are an infinite number of primes. But while that’s the elegant way, it’s not the only way.
Some mathematical problems can be solved by brute force. If you have an abbey full of mathematically minded monks, you can solve a brute force problem in a couple of decades. It’s a matter of figuring out how to enumerate all of the cases, divide up the work, and wait.
No abbey? No problem, today we have computers. How can we put a computer to work to brute-force the problem?
the naïve brute force approach
The naïve thing to do is to lazily generate a list of primes, checking each one to see if it’s a truncatable prime. This generates a lazy list of truncatable primes.
That seems like a terrible idea, because we just established that there are an infinite list of primes. Whether there are a finite number of truncatable primes or not, our algorithm will never terminate.
But we can combine brute force with a modicum of reasoning. If there are an infinite number of truncatable primes, our algorithm will never stop. But what if there are a finite number of truncatable primes?
What do we know about truncatable primes? One thing we can use is the deduction that any two consecutive truncatable primes must either have the same number of digits, or differ by at most one digit.
Consider some right truncatable prime p, with d digits. The next largest truncatable prime might also have d digits, as might the next. Or it might have d + 1 digits, as might the next. But for any truncatable prime, the next largest truncatable prime cannot have d + 2 digits, because if you removed a digit, there would have to be some truncatable prime with d + 1 digits.
It follows then that if we are testing consecutive primes for “truncatability,” and if we know the length of the largest truncatable prime that we’ve seen so far, any prime that has two more digits than the largest truncatable prime must necessarily not be truncatable, and we would know there would be no larger truncatable primes. Which would mean that there would be a finite number of left truncatable primes.
Of course, if our algorithm keeps finding truncatable primes that have the same length as the previous truncatable prime, or are at most one digit longer, we will only know that there are more of them than we have patience to test.
But maybe we should try it? There may be a reasonably tractable finite number of truncatable primes.
computering truncatable primes
In job interviews, it seems they always ask you to implement something from scratch, whereas in real life you just DuckDuckGo for TEH CODEZ. Let’s do that: We want some code that lazily generates prime numbers in ascending order. Like this code from The Hubris of Impatient Sieves of Eratosthenes:
function * multiplesOf (startingWith, n) {
let number = startingWith;
while (true) {
yield number;
number = number + n;
}
}
function destructure (iterable) {
const iterator = iterable[Symbol.iterator]();
const { done, value } = iterator.next();
if (!done) {
return { first: value, rest: iterator }
}
}
class HashSieve {
constructor () {
this._hash = Object.create(null);
}
addAll (iterable) {
const { first, rest } = destructure(iterable);
if (this._hash[first]) {
this._hash[first].push(rest);
}
else this._hash[first] = [rest];
return this;
}
has (number) {
if (this._hash[number]) {
this._remove(number);
return true;
}
else return false;
}
_remove (number) {
const iterables = this._hash[number];
if (iterables == null) return false;
delete this._hash[number];
iterables.forEach((iterable) => this.addAll(iterable));
return number;
}
}
function * Primes () {
let prime = 2;
const composites = new HashSieve();
while (true) {
yield prime;
composites.addAll(multiplesOf(prime * prime, prime));
while (composites.has(++prime)) {
// do nothing
}
}
}
We’ll need to iterate over all the primes, checking each one to see if it is truncatable. That would normally involve a lot of checking whether numbers are prime. But a lazy list of primes doesn’t help with that. We could save them as we generate them, but that might take up a lot of space. If we presume that there are a lot fewer tractable primes than all primes, maybe we can get away with just storing tractable primes.
In fact, we don’t need to save every truncatable prime, just those that are the same length or one digit smaller than whatever prime we’re currently examining. If there aren’t any that are the same length or one digit smaller, it means our current prime is at least two digits larger than the largest truncatable prime we’ve found, and we’re done.
Here’s a first cut at a brute-force check for right truncatable primes. Although we’re generating the primes, what we’re really doing is a brute-force search for a gap that would indicate that there can be no larger right truncatable primes:
// Depends upon Primes() from https://gist.github.com/raganwald/78b086166c0712b49e5160edca5ebadd
const rightTruncatablePrimeStrings = [];
for (const primeInt of Primes()) {
const prime = primeInt.toString();
const isRightTruncatablePrime = isRightTruncatablePrimeString(prime);
if (isRightTruncatablePrime === true) {
rightTruncatablePrimeStrings.push(prime);
console.log(prime);
} else if (isRightTruncatablePrime === null) {
console.log('There are no more right truncatable primes.');
break;
}
}
// returns:
//
// true, indicating that the string passed represents a right truncatable prime;
//
// false, indicating that the string passed does not represent a right truncatable prime,
// but more right truncatable primes may yet exist
//
// null, indicating the string passed does not represent a right truncatable prime,
// and there are no larger right truncatable primes
function isRightTruncatablePrimeString(prime) {
if (prime.length === 1) {
return true;
} else {
const remainder = prime.substr(0, prime.length - 1);
const remainderLength = remainder.length - 1;
// remove our existing truncatable primes that are too short
while (rightTruncatablePrimeStrings.length > 0 && rightTruncatablePrimeStrings[0].length < remainderLength) {
rightTruncatablePrimeStrings.shift();
}
if (rightTruncatablePrimeStrings.length === 0) {
return null;
} else {
return rightTruncatablePrimeStrings.includes(remainder);
}
}
}
//=>
2
3
5
7
23
...
23399339
29399999
37337999
59393339
73939133
There are no more right truncatable primes.
Success! Of a kind…
evaluating our naïve brute force algorithm
If you physically babysist this algorithm while it runs, you’ll see that it gets slower and slower as it goes. If we count how many primes it has to check to discover each truncatable prime, we find that although the number gyrates back and forth a lot, the number of primes to be tested grows rapidly as the algorithm finds longer and longer truncatable primes.
For example, having found the second-last truncatable prime (59,393,339), it has to check 807,690 more primes before it discovers 73,939,133, the last truncatable prime.
How many primes do you suppose it has to check before it reaches 1,000,000,007, the first prime with ten digits? That’s when it realizes that there can be no more truncatable primes.
And it’s worse than this. Generating the consecutive primes with our “sieve” algorithm is itself a process that gets slower and slower as each prime is generated. And we need to generate more and more primes to disciver each truncatable prime.
So there’s no surprise that it is painfully slow. But at least we made it work. Can we make it faster?
generate-and-test
Our algorithm above is a classic “generate-and-test” brute-force approach. One algorithm generates candidate solutions, the other tests them. As it happens, the “generate” is itself a variation of generate-and-test: It generates integers, tests to see whether the integers are prime, and then tests the primes to see if they are truncatable.
Another approach is to flip things around. Instead of testing whether prime numbers are truncatable, what if we test truncatable numbers to see if they are prime?
Here’s a little prime testing function. It uses our lazily generated primes to come up with factors to test:
const primeIterable = Primes();
const factors = [];
function isPrime(n) {
const squareRoot = Math.floor(math.sqrt(n));
while (factors.length === 0 || factors[factors.length - 1] < squareRoot) {
factors.push(primeIterable.next().value);
}
for (factor of factors) {
if (n % factor === 0) {
return false;
} else if (n > squareRoot) {
break;
}
}
return true;
}
This works, but there’s an obvious refactoring: The function is doing mixing two concerns. factors is clearly a list of primes, but we’re faffing about with an array backed by an iterable to save recomputing primes from 2 every time we test a number.
What we want is an iterable over primes that is memoized. DuckDuckGo to the rescue again… And this gist has just the thing!
function memoize (generator) {
const memos = {},
iterators = {};
return function * (...args) {
const key = JSON.stringify(args);
let i = 0;
if (memos[key] == null) {
memos[key] = [];
iterators[key] = generator(...args);
}
while (true) {
if (i < memos[key].length) {
yield memos[key][i++];
}
else {
const { done, value } = iterators[key].next();
if (done) {
return;
} else {
yield memos[key][i++] = value;
}
}
}
}
}
And now we can write:
// requires `memoize` from https://gist.github.com/raganwald/9714874740ec0048e3bc
const factors = memoize(Primes);
function isPrime(n) {
const squareRoot = Math.floor(Math.sqrt(n));
for (const factor of factors()) {
if (n % factor === 0) {
return false;
} else if (factor > squareRoot) {
return true;
}
}
}
Much better. Ok, we can test whether some arbitrary number is a prime. How do we generate truncatables?
2, 3, 5, and 7 are truncatables. Given a truncatable, we can try appending a 1, 3, 7, or 9 to it. If the result is a prime, it too is truncatable. (We could try 2, 4, 6, and 8, but it’s obvious that any number ending in an even digit is not a prime, and any number ending in a 0 or a 5 is also not a prime.)
If we visualize the truncatable numbers as a tree, we can perform a search of the tree for primes. 2 has as its children 21, 23, 27, and 29. Only 23 and 29 are prime. 23 has as its children 231, 233, 237, and 239, of which 233 and 239 are prime. And so forth, and so forth…
Here’s an implementation of the above “depth-first” search. It won’t be in numerical order, but if it terminates, we know that the number of truncatables is finite:
function * truncatables(...bases) {
for (const base of bases) {
yield base;
const baseTimesTen = base * 10;
for (const digit of [1, 3, 7, 9]) {
const candidate = baseTimesTen + digit;
if (isPrime(candidate)) {
yield * truncatables(candidate);
}
}
}
}
for (const truncatable of truncatables(2, 3, 5, 7)) {
console.log(truncatable);
}
console.log('there are a finite number of truncatables');
And as we expected, this is lightning-quick compared to our “generate primes and test them for truncatability” algorithm.
what have we learned?
First, we’ve learned that brute-force, while it has its limitations, can answer questions for us, or at least rule out certain possibilities.
Second, we’ve learned that even when choosing to “brute force” a solution to a problem, carefully choosing how we go about brute forcing the solution can have a tremendous impact on the performance of our programs.
And third, we’ve learned (by osmosis) that lazy computations like using generators can help us structure our code in a reasonable manner, separating concerns.
(discuss “Truncatable Primes in JavaScript” on /r/javascript, or feel free to edit this page yourself)