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:
Input: N = 3 Output: 23 Explanation: 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 = 5 Output: 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:
C++
#include <bits/stdc++.h>using namespace std;// Function to check if a number// is even or notbool is_even(int n) { return n % 2 == 0;}// Function to compute base^exp mod mint expmod(int base, int exp, int m) { if (exp == 0) { return 1; } else if (is_even(exp)) { return (int)pow(expmod(base, exp / 2, m), 2) % m; } else { return base * expmod(base, exp - 1, m) % m; }}// Function to check if a is// a composite number || not// using Miller-Rabin primality testbool try_composite(int a, int d, int n, int s) { // ((a) ^ d) % n equal to 1 if (expmod(a, d, n) == 1) { return false; } for (int i = 0; i < s; i++) { if (expmod(a, pow(2, i) * d, n) == n - 1) { return false; } } return true;}// Function to check if a number// is prime || not using// Miller-Rabin primality testbool is_probable_prime(int n, int k) { // Base Case if (n == 0 || n == 1) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } int s = 0; int d = n - 1; while (true) { int quotient = d / 2; int remainder = d % 2; if (remainder == 1) { break; } s += 1; d = quotient; } // Iterate given number of k times for (int i = 0; i < k; i++) { int a = rand() % (n - 2) + 2; // 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 numberint largest_left_truncatable_prime(int base) { // Stores count of digits // in a number int radix = 0; // Stores left-truncatable prime vector<int> candidates{0}; // Iterate over the range [0, infinity] while (true) { // Store left-truncatable prime // containing i digits vector<int> new_candidates; // Stores base ^ radix int multiplier = pow(base, radix); // Iterate over all possible // value of the given base for (int i = 1; i < base; i++) { // Append the i in radix-th digit // in all (i - 1)-th digit // left-truncatable prime for (auto x : candidates) // If a number with i digits // is prime if (is_probable_prime( x + i * multiplier, 30)) new_candidates.push_back( x + i * multiplier); } // If no left-truncatable prime found // whose digit is radix if (new_candidates.size() == 0) return *max_element(candidates.begin(), candidates.end()); // Update candidates[] to all // left-truncatable prime // whose digit is radix candidates = new_candidates; // Update radix radix += 1; }}// Driver Codeint main(){ int N = 3; int ans = largest_left_truncatable_prime(N); cout << ans ;}// This code is contributed by Phasing17. |
Java
import java.util.*;class Main { // Function to check if a is a composite number || not // using Miller-Rabin primality test static boolean TryComposite(long a, long d, long n, int s) { // ((a) ^ d) % n equal to 1 long x = ModPow(a, d, n); if (x == 1 || x == n - 1) { return false; } for (int i = 0; i < s; i++) { x = ModPow(x, 2, n); if (x == n - 1) { return false; } } return true; } // Function to compute base^exp mod m static long ModPow(long baseNumber, long exponent, long modulus) { long result = 1; while (exponent > 0) { if ((exponent & 1) == 1) { result = (result * baseNumber) % modulus; } baseNumber = (baseNumber * baseNumber) % modulus; exponent >>= 1; } return result; } // Function to check if a number is prime || not using // Miller-Rabin primality test static boolean IsProbablePrime(long n, int k) { // Base Case if (n == 0 || n == 1) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } long d = n - 1; int s = 0; while (d % 2 == 0) { s++; d /= 2; } Random rnd = new Random(); // Iterate given number of k times for (int i = 0; i < k; i++) { long a = rnd.nextInt(-2 + (int)n - 1) + 2; // If a is a composite number if (TryComposite(a, d, n, s)) { return false; } } // No base tested showed // n as composite return true; } // Function to find the largest // left-truncatable prime number static long LargestLeftTruncatablePrime(int baseNumber) { // Stores count of digits // in a number int radix = 0; // Stores left-truncatable prime long[] candidates = { 0 }; // Iterate over the range [0, infinity] while (true) { long[] newCandidates = new long[0]; long multiplier = (long)Math.pow(baseNumber, radix); for (int i = 1; i < baseNumber; i++) { for (int j = 0; j < candidates.length; j++) { if (IsProbablePrime( candidates[j] + i * multiplier, 30)) { long[] temp = new long[newCandidates.length + 1]; temp[newCandidates.length ] = candidates[j] + i * multiplier; newCandidates = temp; } } } if (newCandidates.length == 0) { return candidates[0]; } candidates = newCandidates; radix++; } } // Driver code public static void main(String[] args) { System.out.println(LargestLeftTruncatablePrime(3)); }}// This code is contributed by phasing17. |
Python3
# Python program to implement# the above approachimport random# Function to check if a is# a composite number or not# using Miller-Rabin primality testdef 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 testdef 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 numberdef 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 Codeif __name__ == "__main__": N = 3 ans = largest_left_truncatable_prime(N) print(ans) |
C#
using System;class Program{ // Function to check if a is a composite number || not // using Miller-Rabin primality test static bool TryComposite(long a, long d, long n, int s) { // ((a) ^ d) % n equal to 1 long x = ModPow(a, d, n); if (x == 1 || x == n - 1) { return false; } for (int i = 0; i < s; i++) { x = ModPow(x, 2, n); if (x == n - 1) { return false; } } return true; } // Function to compute base^exp mod m static long ModPow(long baseNumber, long exponent, long modulus) { long result = 1; while (exponent > 0) { if ((exponent & 1) == 1) { result = (result * baseNumber) % modulus; } baseNumber = (baseNumber * baseNumber) % modulus; exponent >>= 1; } return result; } // Function to check if a number is prime || not using // Miller-Rabin primality test static bool IsProbablePrime(long n, int k) { // Base Case if (n == 0 || n == 1) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } long d = n - 1; int s = 0; while (d % 2 == 0) { s++; d /= 2; } Random rnd = new Random(); // Iterate given number of k times for (int i = 0; i < k; i++) { long a = rnd.Next(2, (int)n - 1); // If a is a composite number if (TryComposite(a, d, n, s)) { return false; } } // No base tested showed // n as composite return true; } // Function to find the largest // left-truncatable prime number static long LargestLeftTruncatablePrime(int baseNumber) { // Stores count of digits // in a number int radix = 0; // Stores left-truncatable prime long[] candidates = { 0 }; // Iterate over the range [0, infinity] while (true) { long[] newCandidates = new long[0]; long multiplier = (long)Math.Pow(baseNumber, radix); for (int i = 1; i < baseNumber; i++) { for (int j = 0; j < candidates.Length; j++) { if (IsProbablePrime( candidates[j] + i * multiplier, 30)) { Array.Resize(ref newCandidates, newCandidates.Length + 1); newCandidates[newCandidates.Length - 1] = candidates[j] + i * multiplier; } } } if (newCandidates.Length == 0) { return candidates[0]; } candidates = newCandidates; radix++; } } // Driver code static void Main(string[] args) { Console.WriteLine(LargestLeftTruncatablePrime(3)); }}// This code is contributed by phasing17. |
Javascript
// JS program to implement// the above approachfunction is_even(n) { return n % 2 === 0;}function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? expmod(base, exp / 2, m) ** 2 % m : base * expmod(base, exp - 1, m) % m;}// Function to check if a is// a composite number || not// using Miller-Rabin primality testfunction try_composite(a, d, n, s){ // ((a) ^ d) % n equal to 1 if (expmod(a, d, n) == 1) return false for (var i = 0; i < s; i++) if (expmod(a, 2**i * d, n) == n-1) return false return true}// Function to check if a number// is prime || not using// Miller-Rabin primality testfunction is_probable_prime(n, k){ // Base Case if (n == 0 || n == 1) return false if (n == 2) return true if (n % 2 == 0) return false let s = 0 let d = n-1 while (true) { var quotient = Math.trunc(d/2) var remainder = d % 2; if (remainder == 1) break s += 1 d = quotient } // Iterate given number of k times for (var i = 0; i < k; i++) { var a = Math.random() * (n - 2) + 2 // 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 numberfunction largest_left_truncatable_prime(base){ // Stores count of digits // in a number let radix = 0 // Stores left-truncatable prime let candidates = [0] // Iterate over the range [0, infinity] while (true) { // Store left-truncatable prime // containing i digits let new_candidates = [] // Stores base ^ radix let multiplier = base ** radix // Iterate over all possible // value of the given base for (var i = 1; i < base; i++) { // Append the i in radix-th digit // in all (i - 1)-th digit // left-truncatable prime for (let x of candidates) // If a number with i digits // is prime if (is_probable_prime( x + i * multiplier, 30)) new_candidates.push( x + i * multiplier) } // If no left-truncatable prime found // whose digit is radix if (new_candidates.length == 0) return Math.max(...candidates) // Update candidates[] to all // left-truncatable prime // whose digit is radix candidates = new_candidates // Update radix radix += 1 }}// Driver Codelet N = 3let ans = largest_left_truncatable_prime(N)console.log(ans)// This code is contributed by Phasing17. |
Output:
23
Time Complexity: O(k * log3N), 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
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
