palindromic_primes_finder_optimized_v2.04

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Filename: palindromic_primes_finder_optimized_v2.04.py
# Version: 2.04
# Author: Jeoi Reqi

"""
Palindromic Primes Finder:

This Python script focuses exclusively on identifying prime numbers that are palindromes, utilizing the equation [P = y^2 - y + 41], where 'y' is provided by the user.
The script iterates through a sequence of numbers, checking for palindromic primes, and displays the results.
Finally giving the user the processing time elapsed in the terminal.

**Requirements:**
- Python 3

**Usage:**
1. Run the script in a terminal or command prompt.
2. Enter the starting value for 'y'.
3. Specify the number of iterations to check.
4. The script will output prime numbers that are also palindromes along with their corresponding 'y' values.
5. Outputs the elapsed time to process in the terminal.

**Note:**
- The equation used is [P = y^2 - y + 41].
- Only prime numbers that are palindromes will be displayed in the output.

Example:
Enter the starting value for y: 41
Enter the number of iterations: 10000000

Results:
[y=131, p=17071]
[y=1814, p=3288823]
[y=2738, p=7493947]
[y=17692, p=312989213]
[y=281233, p=79091719097]
[y=1372760, p=1884468644881]

Processing time: 164.902216 seconds
Processing time: 0 hours, 30 minutes, 18.918295 seconds
"""

import random
import time

def is_prime(num, k=5):
    if num < 2:
        return False
    if num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False

    # Use a deterministic Miller-Rabin for smaller numbers
    if num < 1373653:
        return all(num % p != 0 for p in [2, 3, 5, 7, 11, 13, 17])

    s, d = 0, num - 1
    while d % 2 == 0:
        s += 1
        d //= 2

    for _ in range(k):
        a = random.randint(2, min(num - 2, 10**5))
        x = pow(a, d, num)
        if x == 1 or x == num - 1:
            continue

        for _ in range(s - 1):
            x = pow(x, 2, num)
            if x == num - 1:
                break
        else:
            return False

    return True

def is_palindrome(num):
    str_num = str(num)
    return str_num == str_num[::-1]

def generate_primes_and_palindromes(start_y, iterations):
    results = []
    start_time = time.time()

    for y in range(start_y, start_y + iterations):
        P = y**2 - y + 41

        if is_prime(P) and is_palindrome(P):
            results.append(f"[y={y}, p={P}]")

    end_time = time.time()
    elapsed_time = end_time - start_time

    print("\nResults:")
    if not results:
        print("No Palindromic Primes found.")
    else:
        for result in results:
            print(result)

    hours, remainder = divmod(elapsed_time, 3600)
    minutes, seconds = divmod(remainder, 60)
    print(f"\nProcessing time: {int(hours)} hours, {int(minutes)} minutes, {seconds:.6f} seconds\n")


if __name__ == "__main__":
    start_y = int(input("Enter the starting value for y: "))
    iterations = int(input("Enter the number of iterations: "))
    generate_primes_and_palindromes(start_y, iterations)