# Largest Left-Truncatable Prime in a given base

Given an integer **N** representing the base of a number, the task is to find the largest left-truncatable prime in the given base **N**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 3Output:23Explanation:

Left-truncatable prime in base N(= 3) are given below:

(12)_{3}= (5)_{10}

(212)_{3}= (23)_{10}

Therefore, the largest left-truncatable prime in base N(= 3) is (23)_{10}.

Input:N = 5Output:7817

**Approach:** The idea is to generate all left-truncatable prime numbers in the given base **N** and print the largest left-truncatable prime number based on the following observations:

If a number containing

(i)digits is a left-truncatable prime number, then the numbers formed from the last(i – 1)digits must be a left-truncatable prime number.Therefore, to make a left-truncatable prime number of digits

i, first find all the left-truncatable prime numbers of(i – 1)digits.

- Initialize an array, say
**candidates[]**, to store the all possible left truncatable prime numbers in the given base**N**. - Iterate over the range
**[0, infinity]**using variable**i**and insert all the left truncatable prime numbers of digits**i**. If no left truncatable number consisting of**i**digits is found, then return from the loop. - Finally, print the maximum element present in the array
**candidates[]**.

Below is the implementation of the above approach:

## Python3

`# Python program to implement` `# the above approach` `import` `random` ` ` `# Function to check if a is` `# a composite number or not` `# using Miller-Rabin primality test` `def` `try_composite(a, d, n, s):` ` ` ` ` `# ((a) ^ d) % n equal to 1` ` ` `if` `pow` `(a, d, n) ` `=` `=` `1` `:` ` ` `return` `False` ` ` ` ` `for` `i ` `in` `range` `(s):` ` ` `if` `pow` `(a, ` `2` `*` `*` `i ` `*` `d, n) ` `=` `=` `n` `-` `1` `:` ` ` `return` `False` ` ` `return` `True` ` ` `# Function to check if a number` `# is prime or not using` `# Miller-Rabin primality test` `def` `is_probable_prime(n, k):` ` ` ` ` `# Base Case` ` ` `if` `n ` `=` `=` `0` `or` `n ` `=` `=` `1` `:` ` ` `return` `False` ` ` ` ` `if` `n ` `=` `=` `2` `:` ` ` `return` `True` ` ` ` ` `if` `n ` `%` `2` `=` `=` `0` `:` ` ` `return` `False` ` ` ` ` `s ` `=` `0` ` ` `d ` `=` `n` `-` `1` ` ` ` ` `while` `True` `:` ` ` `quotient, remainder ` `=` `divmod` `(d, ` `2` `)` ` ` `if` `remainder ` `=` `=` `1` `:` ` ` `break` ` ` `s ` `+` `=` `1` ` ` `d ` `=` `quotient` ` ` ` ` ` ` `# Iterate given number of k times ` ` ` `for` `i ` `in` `range` `(k):` ` ` `a ` `=` `random.randrange(` `2` `, n)` ` ` ` ` `# If a is a composite number` ` ` `if` `try_composite(a, d, n, s):` ` ` `return` `False` ` ` ` ` `# No base tested showed` ` ` `# n as composite` ` ` `return` `True` ` ` ` ` `# Function to find the largest` `# left-truncatable prime number` `def` `largest_left_truncatable_prime(base):` ` ` ` ` `# Stores count of digits` ` ` `# in a number` ` ` `radix ` `=` `0` ` ` ` ` `# Stores left-truncatable prime` ` ` `candidates ` `=` `[` `0` `]` ` ` ` ` `# Iterate over the range [0, infinity]` ` ` `while` `True` `:` ` ` ` ` `# Store left-truncatable prime` ` ` `# containing i digits` ` ` `new_candidates ` `=` `[]` ` ` ` ` `# Stores base ^ radix` ` ` `multiplier ` `=` `base ` `*` `*` `radix` ` ` ` ` ` ` `# Iterate over all possible ` ` ` `# value of the given base` ` ` `for` `i ` `in` `range` `(` `1` `, base):` ` ` ` ` ` ` `# Append the i in radix-th digit` ` ` `# in all (i - 1)-th digit ` ` ` `# left-truncatable prime` ` ` `for` `x ` `in` `candidates:` ` ` ` ` ` ` `# If a number with i digits` ` ` `# is prime` ` ` `if` `is_probable_prime(` ` ` `x ` `+` `i ` `*` `multiplier, ` `30` `):` ` ` `new_candidates.append(` ` ` `x ` `+` `i ` `*` `multiplier)` ` ` ` ` ` ` `# If no left-truncatable prime found` ` ` `# whose digit is radix ` ` ` `if` `len` `(new_candidates) ` `=` `=` `0` `:` ` ` `return` `max` `(candidates)` ` ` ` ` ` ` `# Update candidates[] to all ` ` ` `# left-truncatable prime` ` ` `# whose digit is radix ` ` ` `candidates ` `=` `new_candidates` ` ` ` ` ` ` `# Update radix` ` ` `radix ` `+` `=` `1` ` ` ` ` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `: ` ` ` `N ` `=` `3` ` ` `ans ` `=` `largest_left_truncatable_prime(N)` ` ` `print` `(ans)` |

**Output:**

23

**Time Complexity:** O(k * log^{3}N), where k is the rounds performed in Miller-Rabin primality test* Auxiliary Space: O(X)*, where

**X**is the total count of left-truncatable prime in base N