A Judagrali series

[r035198x]

A while ago the following question was flooding programming forums.

Find the 4th prime number N such that N=NumberOfDigits(Q) where N is prime AND Q is
prime AND where Q = (2^p) - 1 where P is prime.
We are looking for the 2nd,3rd, 4th prime number N in the Judagrali series as well as its
corresponding Q and P values.
Hints:
1 The 4th N corresponds to a very large Q. Take this into account when doing the
calculation.
2 Computational efficiency is important.
3 Object orientation and inheritance MUST be used. i.e. N is a prime, and a subset
(subclass) of Q, Q is also prime and a subset of P which is also prime.



It was apparently being asked in interview questions.
The hints were complete giveaways.

1 The 4th N corresponds to a very large Q. Take this into account when doing the
calculation.
That's an easy one. Whatever variable that we use to store our Q's needs to be able to store large integers (I'll use java.math.BigInteger).

2 Computational efficiency is important.
I'll just use java.math.BigDecimal's nextProbablePrime method for generating primes.

3 Object orientation and inheritance MUST be used. i.e. N is a prime, and a subset
(subclass) of Q, Q is also prime and a subset of P which is also prime.
Starting with the relationship between P and Q, P is just a (prime) number.

class P {
     BigInteger value;
        public P(BigInteger p) {
          value = p;
        }
     public P() {}
}

As you can see, P is not interesting at all. It just stores the BigInteger value in a, well, value variable. The only important thing about it is that it must store prime numbers only. The isJudagrali method just tests if value is a prime number.
Now Q and P's relationship is specified as Q = (2^p) - 1. From that relation, if we have a P, we can get a Q easily. However, for that Q to be a valid number for our sequence, it (the Q) needs to be prime as well. The fact that it needs to be prime as well means that the Q class can extend P. Our isJudagrali method inherited from P still works for us here. The relationship Q = (2^p) - 1 is easily enforced in Q's constructor.

class Q extends P {
    public Q() {}
    public Q(P p) {
        value = BigInteger.ONE.shiftLeft(p.value.intValue())
   .subtract(BigInteger.ONE);
    }
}

I just did a little bit of shifting to achieve (2^p). There is nothing evil about it!
The last piece of the puzzle is the N.
N is a Q so we make it extend Q. It should also hold the number of digits of a given Q.
Again the constructor can enforce that for us:

class N extends Q {
    public N(Q q) {
        value = numDigits(q.value);
    }
    public BigInteger numDigits (BigInteger num) {
         String s = ""+ num;
         return new BigInteger(""+s.length());
    }
}

The prime number generator I'll use for this one is simply from the BigInteger class

class PrimeGenerator {
    BigInteger current = BigInteger.ONE;
    public BigInteger next() {
       current = current.nextProbablePrime();
       return current;
    }
}

The main program doesn't have much to do. It simply grabs primes from our prime number generator, constructs a P and it's corresponding Q value. If the Q and P relationship is satisfied, it constructs
a corresponding N using that Q. If N is valid Judagrali then it prints out the P, Q, N values until 4 of them have been printed.

public static void main(String[] args) {
 PrimeGenerator g = new PrimeGenerator();
 int count = 0;
 while (count < 4) {      
  P p = new P(g.next());
  Q q = new Q(p);
  if(q.isJudagrali()) {
    N n = new N(q );
    if(n.isJudagrali()) {
      System.out.println("P :" +p.value + " Q: "+q.value + "  N :"+n.value);
      count++;
    }
  }
 }
}
 

There is no need to test if P is Prime because, hopefully, our prime generator is correct!

[jkmyoung]

Considering this, do we actually need to store Q?

The relationship from p to n is
n = Roundup(log(2)*p)
and we can store log(2) as a constant.

Testing if 2^p -1 is prime may be easier than testing if a particular number is prime because we can use modulus.


If using the brute force method to test if something is prime:
2^p-1 is divisible by x, only if
2^p - 1 = 0 mod x
2^p = 1 mod x
This should be computationally faster, eg take the binary of p, and find
2^1 mod x
2^2 mod x
2^4 mod x
...
2^(2^n) mod x for some n, where p < 2^n
add up the relative terms mod x, and see if they add to 0.

Of course, this all depends on how we test for primality.

[r035198x]

Sounds right. I hadn't realized that. Hint 3 though seems to want the solution to contain Q and have the relationships set up.