Problem Breakdown
We are tasked with finding the smallest integer that satisfies two conditions simultaneously: it is a prime number and it is a palindrome. This target must be greater than or equal to N.
- Input: An integer
Nwhere . - Output: The smallest prime palindrome .
- Constraints & Guarantees: We are guaranteed that a solution exists within the range and specifically less than . This upper bound is critical for complexity analysis.
Edge Cases to Consider:
- Small Inputs (): The smallest prime palindrome is 3 (since 2 is not a palindrome in standard representation? Wait, 2 IS a palindrome). So if , the answer is 2 or 3 depending on primality definition and constraints. Actually, 2 is prime and “reads same left to right”. If input is 1, output should be 2 (since 1 is not prime).
- Single Digit: All single digit primes are palindromes ().
- Even Palindromes: Any palindrome with an even number of digits ending in is divisible by that last digit (and thus composite), except for the single case
2. This implies we can skip checking palindromes ending in these digits. - Range Bound: Since the answer is guaranteed to be under , we do not need arbitrary precision arithmetic or infinite loops; our search space is bounded and small enough for optimized iteration.
Intuition
A brute-force approach would iterate through every integer starting from N, check if it’s a palindrome, then check if prime.
- Complexity of Brute Force: Checking primality takes . Iterating one by one is slow because the density of palindromes drops significantly as numbers get larger (e.g., for 9-digit numbers, there are only ~4500 palindromes vs billions of integers).
- Key Insight: We can drastically reduce search space by generating candidates that are already palindromes. Instead of checking every number to see if it’s a palindrome, we construct them. Furthermore, since any prime must end in an odd digit (), and for even-length palindromes the last digit is determined by the first (which cannot be even/0 except single digits), most generated candidates will naturally fail primality checks.
- Optimization: We iterate through lengths of numbers starting from
len(str(N)). For each length, we generate valid palindromes in increasing order and stop as soon as we find a prime . This avoids checking non-palindrome integers entirely for the expensive primality test.
Approach
- Handle Small Cases: If , return
3(since 2 is not palindrome? Wait, 2 IS a palindrome). Let’s verify: Is 2 a prime palindrome? Yes. So if input and we need smallest .- Actually, let’s just start generating from length of . If
len(N)generates nothing valid (e.g., all palindromes < N), move to next length.
- Actually, let’s just start generating from length of . If
- Iterate Lengths: Start checking lengths starting from the number of digits in
N. We stop once we find a solution or exceed bounds (though bound is guaranteed). - Generate Palindromes by Half: A palindrome is determined entirely by its first digits (“half”).
- For length , the “half” ranges from to .
- Construct full palindrome: If odd,
s + s[:-1][::-1]. If even,s + s[::-1](wheresis the half string).
- Filter & Check: For each generated number:
- Skip if it’s less than .
- Since we iterate “half” in increasing order, once a palindrome is found, subsequent ones are also candidates (but larger), so the first prime one wins for that length. However, since palindromes of smaller lengths might be skipped entirely if they were all less than , we must ensure we check current length’s smallest valid candidate against
N. - Wait, simpler logic: Iterate “half” from min to max. Construct number. If num and is_prime(num), return it immediately? No, because for a fixed length L, the generated numbers are sorted by value as we increment half. So if current palindrome , continue loop (it’s not valid). Once
val >= N, check primality. Since we want smallest overall , and lengths increase monotonically:- If all palindromes of length L are less than N, move to next length.
- The first prime palindrome found with value is the answer because any smaller candidate would have been in a previous length (already checked) or earlier in current loop generation order.
Complexity Analysis
- Time: , where is max possible number () and is the count of palindromes we check.
- Primality test takes . For , this is roughly 14,000 operations per candidate.
- The number of candidates (palindromes) up to length 9 is small (). Most are filtered out by the check or primality test quickly. This fits well within time limits for Python.
- Space: auxiliary space beyond input/output storage (ignoring string conversion overhead which is logarithmic in value size).
Solution
import math
def is_prime(num):
if num < 2: return False
if num == 2 or num == 3: return True
if num % 2 == 0 or num % 3 == 0: return False
# Check divisors up to sqrt(n) with step of 6k +/- 1 optimization
i = 5
while i * i <= num:
if num % i == 0 or num % (i + 2) == 0:
return False
i += 6
return True
def next_prime_palindrome(n):
# Handle small edge cases explicitly for clarity, though loop covers them mostly.
# If n is very small, we might find a palindrome of length len(str(n)) or less?
# No, if N=10, smallest prime pal >= 10 is 11 (len 2).
# We start generating from the number of digits in N.
s_n = str(n)
l_len = len(s_n)
for length in range(l_len, 9): # Max answer < 2*10^8 implies max length is roughly 9 (actually up to 9 digits since limit is ~2e8).
# Actually if N=13 -> ans 101. If N=10^8 -> we need > 10^8, so len 9.
# The constraint says answer < 2*10^8 (which has 9 digits: 2 followed by zeros).
# So max length is 9. We can iterate up to 9 safely? Wait, if N=13, we start at len 2.
# If loop range goes too high it might miss or TLE. But constraint guarantees existence < 2e8.
half_len = (length + 1) // 2
# Determine starting value for the 'half' part to ensure palindrome >= n if possible?
# Actually, simpler: iterate all valid halves of this length and check condition.
start_half = int('0' * (half_len - 1)) # Not quite right logic for leading zeros.
# Better approach: Iterate half from smallest number with correct digit count to largest.
min_val = 10**(half_len - 1)
max_val = 10**half_len
for i in range(min_val, max_val):
s_half = str(i)
# Construct palindrome based on length parity
if length % 2 == 0:
pal_str = s_half + s_half[::-1]
else:
pal_str = s_half[:-1][::-1] + s_half
val = int(pal_str)
# Optimization: If we are generating for a specific length,
# and the current palindrome is less than N, it's not valid.
if val < n: continue
# Check primality only on candidates >= N
if is_prime(val): return val
# If no solution found in this length (e.g., all palindromes of len L are < N),
# the loop continues to next length automatically.
return -1 # Should not reach here based on problem constraints
# Wrapper for clean execution
def solve(n: int) -> int:
if n <= 2: return 3 # Smallest prime palindrome >= 1 is 2? Wait, input N=6->7.
# If N=1 or 2, answer should be the smallest prime pal >= N.
# Primes are 2, 3, 5... Palindromes: 2, 3, 4(no), 5, 7, ...
# So if n <= 2 return 2? Wait example says input 6 -> 7.
# If N=1, smallest prime pal >= 1 is 2 (since 2>=1).
# Let's fix the logic inside solve to be robust for small inputs without hardcoding too much.
pass
# Re-writing main function with correct loop bounds and edge case handling
def next_prime_palindrome_correct(n):
if n <= 3: return max(2, n) # If N=1->2, N=2->2, N=3->3? Wait problem says >=N.
# Example 6 -> 7. Example 8 -> 11.
# Let's just rely on generation logic starting from len(str(n)).
s_n = str(n)
for length in range(len(s_n), 9): # Max digits needed is roughly 9 given constraint <2e8
half_len = (length + 1) // 2
start_half = int('0' * (half_len - 1)) if half_len > 1 else 0
# Actually simpler: iterate i from min possible number of digits to max.
# Leading digit cannot be 0 for palindrome generation unless length is 1?
# Correct range logic:
start = int('1' + '0' * (half_len - 2)) if half_len > 1 else 1
end = int('9' + '9' * (half_len - 1))
for i in range(start, end):
s_half = str(i)
# Construct palindrome string carefully to avoid leading zeros issues implicitly handled by integer conversion?
if length % 2 == 0:
pal_str = s_half + s_half[::-1]
else:
pal_str = s_half[:-1][::-1] + s_half
val = int(pal_str)
# If we are at the first iteration of a new length, check if smallest palindrome >= n.
# Actually just checking `val < n` is sufficient to skip.
if val < n: continue
if is_prime(val): return val
# Optimization for single digit case or when N itself is small prime pal?
# If we start loop at len(N), and find nothing, next length handles it.
# But wait, what if N=2 (len 1)? Loop starts range(1, ...). half_len = 1. i in [0..9]? No leading zeros allowed for palindrome generation usually?
# Palindromes of len 1: 0-9. Primes: 2,3,5,7.
# If N=6 (len 1), loop range(1). half_len = 1. i in [0..9]. val < n check skips 0-5. Checks 6(no pal? wait len 1 is palindrome always)).
# Wait logic for odd length construction: s_half[:-1][::-1] + s_half.
# If len=1, half_len=1. i='2'. s_half="2". s_half[:-1]="", rev="", result "2" + "" = "2"? No wait.
# My string slicing logic for odd length: `s_half` is the first ceil(L/2) chars.
# If L=3, half_len=2. i ranges 0..9? Wait range(10). s_half="1". pal_str = "" + "1" -> "1"? No.
return -1
# Let's rewrite the generation logic cleanly for final code block to ensure correctness without bugs in thought process above.
```python
import math
def is_prime(num):
if num < 2: return False
if num == 2 or num == 3: return True
if num % 2 == 0 or num % 3 == 0: return False
i = 5
while i * i <= num:
if num % i == 0 or num % (i + 2) == 0:
return False
i += 6
return True
def next_prime_palindrome(n):
# Edge case handling for small N to ensure we don't miss single digit primes
# before the loop logic kicks in properly.
if n <= 3: return max(2, n)
s_n = str(n)
# Iterate through lengths starting from length of N up to reasonable limit (9 digits for < 2e8)
for length in range(len(s_n), 10):
half_len = (length + 1) // 2
start_half = int('1' * half_len - '0') # Not quite. Start with smallest number of this digit count? No, leading zeros not allowed.
# Smallest valid prefix for length L is 1 followed by zeros if even/odd logic applies to digits.
# Actually simpler: Iterate i from min possible value (power of 10) up to max-1.
start = int('1' + '0' * (half_len - 2)) if half_len > 1 else 1
for i in range(start, 10**half_len): # Max is exclusive bound? No inclusive logic handled by loop condition or check < n.
s_half = str(i)
if length % 2 == 0:
pal_str = s_half + s_half[::-1]
else:
pal_str = s_half[:-1][::-1] + s_half
val = int(pal_str)
# If generated palindrome is smaller than N, it's not the answer.
# Since we want smallest >= N, if current < N continue loop (next i will be larger).
if val < n: continue
if is_prime(val): return val
# Optimization check: If length increases and all palindromes of previous