Investigation of Brute Force
Let's investigate and improve on a brute force method.
With basic methods, we can check whether an integer is a palindrome in time, and check whether it is prime in time. So we would probably like to do the palindrome check first.
Now, say we naively check every number . How big is ?
Well, the palindromes could be approximately apart, since for example
99988999's next palindrome is
If we assume being a palindrome and being a prime is independent, then based on the density of primes, , and we would do a palindrome check on approximately values, and a primality test on values of complexity . This seems to work.
However, we can't make this assumption of independence: whether a number is a palindrome or prime are negatively correlated events! For example, are clearly not prime. Actually, all palindromes with an even number of digits are divisible by 11, and are therefore not prime! (Except for 11.) For example, an 8 digit palindrome can be written as:
where the second-last equivalence follows as and have different parity.
Density of Palindromes
For a palindrome of digits, choosing the first digits uniquely determines the remaining digits. Hence, there are of them (the first digit can't be 0.) Thus, there are
palindromes of 8 digits or less.
Actually, we don't need to check the palindromes with an even number of digits, so there are under 10000 palindromes we need to check. However, we also need to check palindromes until we encounter the first 9 digit prime palindrome, as all 8 digit numbers will have an answer equal to that. Luckily, it occurs quickly:
100030001 is the 4th 9-digit value checked. (We can verify this with brute force.)
For each palindrome, we can test whether it is prime in operations. So in total, an approach centered around enumerating palindromes seems like it will succeed.
Approach 1: Iterate Palindromes
Say we have a palindrome . What is the next palindrome?
Each palindrome of digits has a palindromic root, it's first digits. The next palindrome is formed by the next root.
For example, if is a root for the 5 digit palindrome , then the next palindrome is with root .
Notice that roots and palindromes are not a bijection, as palindromes and have the same root.
For each palindromic root, let's find the two associated palindromes (one with an odd number of digits, and one with an even number.) For roots with digits, they will generate palindromes of and digits.
If we didn't know that palindromes with an even number of digits (and greater than 11) are never prime, we're still fine - we can just check both possibilities. When checking both possibilities, we check the palindromes with digits first, as they are all smaller than the palindromes with digits.
We'll use an idea from [LeetCode Problem: Reverse an Integer], in order to check whether an integer is a palindrome. We could have also converted the integer to a string, and checked the indices directly.
As for testing primes with
isPrime(N), we'll use the standard check: testing whether every number is a divisor of .
- Time Complexity: Based on our analysis above, we performed on the order of operations (not counting log factors from dealing with integers), given we knew the existence of prime palindrome
Interestingly, the time complexity is an open problem in mathematics, as it is not even known whether there are infinitely many prime palindromes, or whether palindromes behave as random integers for our purposes here - see ["Almost All Palindromes are Composite"] for more.
- Space Complexity: , the space used by
Approach 2: Brute Force with Mathematical Shortcut
Our brute force works except when is 8 digits (as explained in Approach Framework when we established that all 8 digit palindromes are not prime), so we can skip all 8 digit numbers.
For each number, check whether it is a palindrome. If it is, check whether it is a prime. If the number is 8 digits, skip to the 9 digit numbers.
Time Complexity: , with the caveats explained in Approach #1, and ignoring the factor when checking an integer for palindromes.
Space Complexity: .
Analysis written by: @awice.