Recently a friend of mine who was staying at a hotel revealed that the six digit security code for the room was 313131. This looked like an easy code to crack and I was reminded of a post that I'd made recently titled Passcodes and Repeated Digits in November of 2025. Figure 1 shows the probabilities for the number of distinct digits chosen: |
Figure 1 |
So the code 313131 is indeed easy to crack, requiring only a maximum of 62 attempts or 31 attempts on average. However, what was of most interest to me regarding 313131 was its prime factorisation:$$ 313131=3 \times 7 \times 13 \times 31 \times 37$$If we rearrange the order of multiplication we get the following:$$ 313131=7 \times 3 \times 13 \times 31 \times 37$$Concatenating these digits we get the number \(73133137\) which is palindromic.
Naturally, I wondered how many other numbers share this property and so I set Gemini to investigate this with the following prompt:
Write a program in Python, tailored for insertion into SageMathCell or a Jupyter notebook, that identifies all composite numbers from 4 up to a user chosen upper limit with the property that the prime factors, when arranged in a suitable order and then concatenated, produce a palindromic number. The default upper limit can be set to 40000. An example of such a number would be 313131 = 3 x 7 x 13 x 31 x 37 that can written as 7 x 3 x 13 x 31 x 37 to produce the palindromic number 73133137 when concatenated. The output of the program should be a table showing number and factorisation followed by a comma separated list of the qualifying numbers.
Naturally this a processor intensive process and my Jupyter notebook struggled mightily to generate the list of suitable numbers. After some time, I decided to restrict the range to between 28000 and 29000 and after further modifications by Gemini, I was able to achieve the following list of numbers:
28072, 28125, 28194, 28224, 28242, 28273, 28308, 28322, 28332, 28416, 28431, 28448, 28585, 28589, 28593, 28601, 28602, 28609, 28620, 28672, 28685, 28692, 28750, 28800, 28812, 28847, 28951
Figure 2 shows the details:
 |
Figure 2 |
I've incorporated this algorithm into my daily search program that has become somewhat impressive if I do say so myself. See Figure 3 for the results of 28067, my diurnal age today.
 |
Figure 3 |
The output is generated by the same program but I've just restricted the range to my daily number, rather lazy but it does the job. Remember the prime factorisation takes multiplicity into account. For completeness I'll include the Python code:
import sys
def get_prime_factors(n):
"""Returns a list of prime factors of n."""
factors = []
d = 2
temp = n
while d * d <= temp:
while temp % d == 0:
factors.append(d)
temp //= d
d += 1
if temp > 1:
factors.append(temp)
return factors
def is_palindrome(s):
"""Checks if a string is a palindrome."""
return s == s[::-1]
def distinct_permutations(iterable):
"""
Yields unique permutations of items in iterable.
This handles repeated elements efficiently (e.g., [2, 2, 3])
without generating all n! redundant combinations.
"""
# Sort the list to start with the lexicographically first permutation
s = sorted(iterable)
yield tuple(s)
n = len(s)
while True:
# 1. Find the largest index i such that s[i] < s[i+1]
i = n - 2
while i >= 0 and s[i] >= s[i+1]:
i -= 1
if i == -1:
return # All permutations generated
# 2. Find the largest index j such that s[i] < s[j]
j = n - 1
while s[j] <= s[i]:
j -= 1
# 3. Swap s[i] and s[j]
s[i], s[j] = s[j], s[i]
# 4. Reverse the sequence from s[i+1] up to the end
s[i+1:] = s[i+1:][::-1]
yield tuple(s)
def find_palindromic_composites(start_n, end_n):
results = []
actual_start = max(4, start_n)
for n in range(actual_start, end_n + 1):
factors = get_prime_factors(n)
# Skip primes
if len(factors) < 2:
continue
found_property = False
winning_perm = None
winning_concat = None
# Use the optimized generator instead of itertools.permutations
for p in distinct_permutations(factors):
concat_str = "".join(map(str, p))
if is_palindrome(concat_str):
found_property = True
winning_perm = p
winning_concat = concat_str
break
if found_property:
fact_str = " x ".join(map(str, winning_perm))
results.append((n, fact_str, winning_concat))
return results
# --- Configuration ---
LOWER_BOUND = 28000
UPPER_BOUND = 29000
# --- Main Execution ---
print(f"Searching for composite numbers between {LOWER_BOUND} and {UPPER_BOUND}...")
print("-" * 80)
print(f"{'Number':<8} | {'Valid Factor Ordering':<35} | {'Resulting Palindrome'}")
print("-" * 80)
qualifying_numbers = find_palindromic_composites(LOWER_BOUND, UPPER_BOUND)
if not qualifying_numbers:
print(f"No qualifying numbers found in the range {LOWER_BOUND} to {UPPER_BOUND}.")
else:
for num, factor_str, pal_str in qualifying_numbers:
print(f"{num:<8} | {factor_str:<35} | {pal_str}")
print("-" * 80)
print("\nComma separated list of qualifying numbers:")
print(", ".join(str(r[0]) for r in qualifying_numbers))
