468,291 Members | 1,734 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Share your developer knowledge by writing an article on Bytes.

A Judagrali series

13,262 8TB
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.

Expand|Select|Wrap|Line Numbers
  1. class P {
  2.      BigInteger value;
  3.         public P(BigInteger p) {
  4.           value = p;
  5.         }
  6.      public P() {}
  7. }

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.


Expand|Select|Wrap|Line Numbers
  1. class Q extends P {
  2.     public Q() {}
  3.     public Q(P p) {
  4.         value = BigInteger.ONE.shiftLeft(p.value.intValue())
  5.    .subtract(BigInteger.ONE);
  6.     }
  7. }
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:


Expand|Select|Wrap|Line Numbers
  1. class N extends Q {
  2.     public N(Q q) {
  3.         value = numDigits(q.value);
  4.     }
  5.     public BigInteger numDigits (BigInteger num) {
  6.          String s = ""+ num;
  7.          return new BigInteger(""+s.length());
  8.     }
  9. }


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


Expand|Select|Wrap|Line Numbers
  1. class PrimeGenerator {
  2.     BigInteger current = BigInteger.ONE;
  3.     public BigInteger next() {
  4.        current = current.nextProbablePrime();
  5.        return current;
  6.     }
  7. }

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.

Expand|Select|Wrap|Line Numbers
  1. public static void main(String[] args) {
  2.  PrimeGenerator g = new PrimeGenerator();
  3.  int count = 0;
  4.  while (count < 4) {      
  5.   P p = new P(g.next());
  6.   Q q = new Q(p);
  7.   if(q.isJudagrali()) {
  8.     N n = new N(q );
  9.     if(n.isJudagrali()) {
  10.       System.out.println("P :" +p.value + " Q: "+q.value + "  N :"+n.value);
  11.       count++;
  12.     }
  13.   }
  14.  }
  15. }
  16.  
There is no need to test if P is Prime because, hopefully, our prime generator is correct!
Nov 6 '08 #1
2 3883
jkmyoung
2,057 Expert 2GB
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.
Dec 10 '08 #2
r035198x
13,262 8TB
Sounds right. I hadn't realized that. Hint 3 though seems to want the solution to contain Q and have the relationships set up.
Dec 17 '08 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

1 post views Thread by Sriram Krishnan [at] gmx [dot] net | last post: by
4 posts views Thread by aW | last post: by
1 post views Thread by Sriram Krishnan [at] gmx [dot] net | last post: by
4 posts views Thread by geoffp | last post: by
33 posts views Thread by r034802n | last post: by
2 posts views Thread by MrBee | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.