Solution


Approach Framework

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 99999999.

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

Intuition

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.

Algorithm

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 .

Complexity Analysis

  • 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 100030001.

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 s (or sb in Java.)


Approach 2: Brute Force with Mathematical Shortcut

Intuition

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.

Algorithm

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.

Complexity Analysis

  • 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.