# Perrin series

• 12-04-2009, 02:57 PM
moamen
tough assignment of prime numbers
I have an assignment which made me very confused!!!!:confused:

it says
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).
• 12-04-2009, 04:49 PM
JosAH
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 ;-)
• 12-04-2009, 04:59 PM
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)).

• 12-04-2009, 05:07 PM
JosAH
Quote:

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:

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
• 12-04-2009, 06:07 PM
moamen
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!!!
• 12-04-2009, 06:21 PM
JosAH
Quote:

Originally Posted by moamen
this dosent work ;(

So I noticed; I should've tested it first; this version does work:

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
• 12-04-2009, 06:27 PM
moamen
Thank You very very very very very much this really works !!!! :D:D:D