venom venom - 2 months ago 12
Java Question

Russian Doll Primes

This question was asked in an interview (about prime numbers)
Russian Doll Primes

They are more commonly known as Truncatable Primes.
I found this code on wiki

public static void main(String[] args){

final int MAX = 1000000;

//Sieve of Eratosthenes (using BitSet only for odd numbers)
BitSet primeList = new BitSet(MAX>>1);
primeList.set(0,primeList.size(),true);

int sqroot = (int) Math.sqrt(MAX);
primeList.clear(0);
for(int num = 3; num <= sqroot; num+=2)
{
if( primeList.get(num >> 1) )
{
int inc = num << 1;
for(int factor = num * num; factor < MAX; factor += inc)
{
//if( ((factor) & 1) == 1)
//{
primeList.clear(factor >> 1);
//}
}
}
}


//Find Largest Truncatable Prime. (so we start from 1000000 - 1
int rightTrunc = -1, leftTrunc = -1;
for(int prime = (MAX - 1) | 1; prime >= 3; prime -= 2)
{
if(primeList.get(prime>>1))
{
//Already found Right Truncatable Prime?
if(rightTrunc == -1)
{
int right = prime;
while(right > 0 && primeList.get(right >> 1)) right /= 10;
if(right == 0) rightTrunc = prime;
}

//Already found Left Truncatable Prime?
if(leftTrunc == -1 )
{
//Left Truncation
String left = Integer.toString(prime);
if(!left.contains("0"))
{
while( left.length() > 0 ){
int iLeft = Integer.parseInt(left);
if(!primeList.get( iLeft >> 1)) break;
left = left.substring(1);
}
if(left.length() == 0) leftTrunc = prime;
}
}
if(leftTrunc != -1 && rightTrunc != -1) //Found both? then Stop loop
{
break;
}
}
}
System.out.println("Left Truncatable : " + leftTrunc);
System.out.println("Right Truncatable : " + rightTrunc);
}


This gives the output:

Left Truncatable : 998443
Right Truncatable : 796339


But I am not able to solve this particular Russian doll prime number problem like if you have a prime number and you remove either left or right digit of this prime number then if that resulting number is prime number or not?

I am new to this so please pardon any mistake.

mJr mJr
Answer Source

Let's start from the beginning:

According to the link you supplied with your question:

"Russian Doll Primes are prime numbers whose right digit can be repeatedly removed, and are still prime."

I will assume that you have a function boolean isPrime(int) to find out if a number is prime.

Googling, we will find from Wikipedia that the number of right-truncatable prime numbers up to 73,939,133 is 83, which makes brute-force a viable option; but a few optimization techniques can be employed here:

  1. Since we right-truncate, we can safely eliminate even numbers (since any even number won't be prime, and so any number generated upon it will never be a russian doll prime).
  2. Since any number that starts with 5 is divisible by 5, then based on the same rule I mentioned in the previous point, we can eliminate 5.

That leaves us with numbers that contain 1, 3, 7, and 9.

Now if we wanted to generate all possible combinations of these 4 numbers that do not exceed the maximum you mentioned (1,000,000), it would take only 4,096 iterations.

The downside of this technique is that we now have 4,096 numbers that contain possible non-prime numbers, or prime numbers that are formed from non-prime numbers and hence are not russian doll primes. We can eliminate these numbers by looping through them and checking; or better yet, we can examine russian doll primes more closely.

Upon examining the rule I quoted from your link above, we find that a russian doll primes are prime numbers whose right digit can be repeatedly removed, and are still prime (and hence are still russian doll prime, given the word repeatedly)!

That means we can work from the smallest single-digit russian doll primes, work our generation magic that we used above, and since any prime number that is formed from russian doll prime numbers is a russian doll prime number, we can eliminate non-primes early on, resulting in a clean list of russian doll prime numbers, while reducing the running time of such a program dramatically.

Take a look at the generation code below:

void russianDollPrimesGeneration(int x) {
    x *= 10;
    if (x * 10 >= 1000000) return;
    int j;
    for (int i=1; i<=9; i+=2) {
        if (i == 5) continue;
        j = x + i;
        if (isPrime(j)) {
            addToRussianDollPrimesList(j);
            russianDollPrimesGeneration(j);
        }
    }
}

Provided that void addToRussianDollPrimesList(int x) is a function that adds x to a list that we previously preserved to store the russian doll prime numbers.

UPDATED NOTE

Note that you can put the call to void russianDollPrimesGeneration(int x) that we made inside the if condition inside the void addToRussianDollPrimesList(int x) function, because whenever we call the former function, we will always call the latter function with the same arguments. I'm separating them here to emphasize the recursive nature of the generation function.

Also note that you must run this function with the integer 0.

A final note is that there are a number of cases that the generation function void russianDollPrimesGeneration(int x) above won't count, even though they are Russian Doll Primes.

Remember when we omitted 2 and 5, because even numbers and numbers divided by 5 cannot be primes and so cannot be Russian Doll Primes? and consequently cannot form Russian Doll Primes? Well, that case does not apply to 2 and 5, because they are prime, and since they are single digits, therefore they are Russian Doll Primes, and are eligible to form Russian Doll Primes, if placed in the left-side, like 23 and 53.

So how to correct our code to include these special cases?

We can make a wrapper function that adds these two numbers and checks for Russian Doll Primes that can be formed using them (which will be the same generation function we are using above).

void generationWrapperFunction(int x) {
    addToRussianDollPrimesList(2);
    russianDollPrimesGeneration(2);
    addToRussianDollPrimesList(5);
    russianDollPrimesGeneration(5);
    russianDollPrimesGeneration(0);
}

END UPDATED NOTE

This little function will produce a list of russian doll prime numbers, which can then be searched for the number we are looking for.

An alternative, yet I believe will be more time-consuming, is the following recursive function:

boolean isRussianDollPrime(int n) {
    if (!isPrime(n)) return false;
    if (n < 10) return true;
    return isRussianDollPrime(n / 10);
}

This function can be modified to work with left-truncatable primes. The generation-based solution, however, will be much difficult to implement for left-truncatable primes.

UPDATE

Check the UPDATED NOTE above.