1. Member
Join Date
Sep 2009
Posts
15
Rep Power
0

## tough assignment of prime numbers

I have an assignment which made me very confused!!!!:confused:

it says
Java Code:
```Pirin sequence are similar to Fibonacci series but with the following rule:
p(n) = p(n-2) + p(n-3) ; p(0) = 3 , p(1) = 0 , p(2) = 2

they have a property (now fully proven) that if p(n) is divisible by n then n is prime number
(special cases exist).

Write a program that will check whether an input x is prime or not using this technique.```
I hope to help me please .
and it would be very nice to help me with an algorithm to solve this problem than a code(but code won't hurt :D).
Last edited by moamen; 12-04-2009 at 06:41 PM.

2. Is the other way around also true? i.e. if n is prime then p(n) is divisable by n. If so, you have found a linear recurrence relation for the prime numbers ...

kind regards,

Jos (not so optimistic about it ;-)

3. Member
Join Date
Sep 2009
Posts
15
Rep Power
0
i guess the vice versa procces is true.

but my problem here is how to make a program that allows me to calculate n!!!!
(e.g) p(11) = 22 ==>22/11 =2 ==> 11 is prime.

my problem here is how to make a program that uses the formula mentiond in the question to calculate n for p(n) (22 for p(11)).

4. Originally Posted by moamen
i guess the vice versa procces is true.

but my problem here is how to make a program that allows me to calculate n!!!!
(e.g) p(11) = 22 ==>22/11 =2 ==> 11 is prime.

my problem here is how to make a program that uses the formula mentiond in the question to calculate n for p(n) (22 for p(11)).

You can calculate P(n) recursively which is utterly stupid because you are recalculating the same numbers over and over again. Better use an iterative approach and juggle with the intermediate results a bit; the following comes to mind:

Java Code:
```int P(int n) {
int a= 3, b= 0, c= 2; // the first three P(n)
switch (n) {
case 0: return a;
case 1: return b:
case 2: return c:
default:
int m;
while (n-- > 2) {
m= a+b;
c= m; b= c; a= b;
}
return m;
}
}```
kind regards,

Jos

5. Member
Join Date
Sep 2009
Posts
15
Rep Power
0
this dosent work ;(

i made another program that gave me the same result. :D

what i need is to make p(11) = #p(0) + #p(1) + #(p2)
// (e.g)p(11) = 4p(0) + 4p(1) + 5p(2) <== this is what i really get after using perrin formula(using a pen and a paper :D) then i substitute p(0) ,p(1) & p(2) with thier values!!!

Thanx very much for your help!!!

6. Originally Posted by moamen
this dosent work ;(
So I noticed; I should've tested it first; this version does work:

Java Code:
```public class Perrin {

private static int P(int n) {

int a = 3, b = 0, c = 2; // the first three P(n)
switch (n) {
case 0:
return a;
case 1:
return b;
case 2:
return c;
default:
int m = 0;
while (n-- > 2) {
m = a + b;
a = b;
b = c;
c = m;
}
return m;
}
}

public static void main(String[] args) {

for (int i = 0; i < 10; i++)
System.out.println("p(" + i + ")=" + P(i));
}
}```
kind regards,

Jos

7. Member
Join Date
Sep 2009
Posts
15
Rep Power
0
Thank You very very very very very much this really works !!!! D:D

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•