10236  The Fibonacci Primes
Moderator: Board moderators

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
In the problem description:
"A Fibonacci Prime is a Fibonacci number which is relatively prime to all the smaller Fibonacci numbers."
But the general definition is the following:
"A Fibonacci prime is a Fibonacci number that is prime"
Which is true for this problem?
The first difference is the 19th Fibonacci Number: 4181. (the 8th Fibonacci Prime according to the problem description) This is relatively prime to all the smaller Fibonacci number, but not prime.
So, what's the output for this input:
8
"A Fibonacci Prime is a Fibonacci number which is relatively prime to all the smaller Fibonacci numbers."
But the general definition is the following:
"A Fibonacci prime is a Fibonacci number that is prime"
Which is true for this problem?
The first difference is the 19th Fibonacci Number: 4181. (the 8th Fibonacci Prime according to the problem description) This is relatively prime to all the smaller Fibonacci number, but not prime.
So, what's the output for this input:
8

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
Can anybody say is this output correct or not?
Input:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1219
6879
7587
14828
22000
Output:
2
3
5
13
89
233
1597
4181
28657
514229
1346269
24157817
165580141
433494437
297121507
533162911
956722026
250473078
449455702
308061521
118949765
842347072
443465936
331464231
208214663
Input:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1219
6879
7587
14828
22000
Output:
2
3
5
13
89
233
1597
4181
28657
514229
1346269
24157817
165580141
433494437
297121507
533162911
956722026
250473078
449455702
308061521
118949765
842347072
443465936
331464231
208214663

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
Actually, it isn't so hard problem. It's easy to find which Fibo numbers are prime (look at some math book or at ranklist). So, main task is to compute first digits of the Fibo #n. This is also easy, compute using log (like probs 474, 702(? don't remember exactly)), the formula for Fibo #n is given in many math books (something with sqrt(5)).
The main problem (at least in my case) was floating point precision. So compute all fibo primes using integer arithmetics and compare with your floating point solution to be sure.
The main problem (at least in my case) was floating point precision. So compute all fibo primes using integer arithmetics and compare with your floating point solution to be sure.
Ivan ,
Thanks for ur reply. But still I've few problems:
first, I know Fib(n)=(pow(a,n)pow(b,n))/sqrt(5).Here a,b are 2 constants. But it's an approximate value. Then how it could be correct?
second, I got it from rank list that Fib(n) and Fib(m) are relative prime if & only if n and m are relative prime. Can u tell me the exact reference from where I can get the proof ?
Chang
Thanks for ur reply. But still I've few problems:
first, I know Fib(n)=(pow(a,n)pow(b,n))/sqrt(5).Here a,b are 2 constants. But it's an approximate value. Then how it could be correct?
second, I got it from rank list that Fib(n) and Fib(m) are relative prime if & only if n and m are relative prime. Can u tell me the exact reference from where I can get the proof ?
Chang
Ivan,
I'm facing some problem!
I tried as follows:
I generated first 22000 prime numbers & then used the formula:fib(n)=pow((1+sqrt(5))/2,n)/sqrt(5).
But the 22000'th prime is about 250000. So fib(n) is so big... Then how I can get the first 9 digits !
Pls tell how it's possible.
By the by,I couldn't understand how you implemented it applying log...Pls explain this method.
Chang
I'm facing some problem!
I tried as follows:
I generated first 22000 prime numbers & then used the formula:fib(n)=pow((1+sqrt(5))/2,n)/sqrt(5).
But the 22000'th prime is about 250000. So fib(n) is so big... Then how I can get the first 9 digits !
Pls tell how it's possible.
By the by,I couldn't understand how you implemented it applying log...Pls explain this method.
Chang

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
>> Fib(n)=(pow(a,n)pow(b,n))/sqrt(5).Here a,b are 2 constants.
>> But it's an approximate value. Then how it could be correct?
It isn't approximation it's precise value.
>> I got it from rank list that Fib(n) and Fib(m) are relative prime
>> if & only if n and m are relative prime. Can u tell me the exact
>> reference from where I can get the proof ?
I think there're several places when you can get it but I've used 'Concrete Mathematics' book by Graham & Knuth.
About log:
generally, we computing first digits of some number x^y. So, exact equation is something like [x^y / 10^k], where k is number of digits after point (and we don't care about them 'cause taking only integer part). When y is too big we facing overflow problem, so we can use log to fix this it (and than using exp() to get correct result, of course). Our equation become log(x^y / 10^k) == log (x^y)  log(10^k) == y*log(x)  k*log(10). Now we're need to select correct k value and than use exp(). I hope you're understand the idea (maybe it isn't so similar to P474 but I think these problems very close).
>> But it's an approximate value. Then how it could be correct?
It isn't approximation it's precise value.
>> I got it from rank list that Fib(n) and Fib(m) are relative prime
>> if & only if n and m are relative prime. Can u tell me the exact
>> reference from where I can get the proof ?
I think there're several places when you can get it but I've used 'Concrete Mathematics' book by Graham & Knuth.
About log:
generally, we computing first digits of some number x^y. So, exact equation is something like [x^y / 10^k], where k is number of digits after point (and we don't care about them 'cause taking only integer part). When y is too big we facing overflow problem, so we can use log to fix this it (and than using exp() to get correct result, of course). Our equation become log(x^y / 10^k) == log (x^y)  log(10^k) == y*log(x)  k*log(10). Now we're need to select correct k value and than use exp(). I hope you're understand the idea (maybe it isn't so similar to P474 but I think these problems very close).
10236 WA
I got WA..........
#include<stdio.h>
#include <math.h>
#define MAX 100
int pri[10001];
int pri_num;
void prime()
{
int i, j;
int na;
int temp;
pri[0] = 2;
pri[1] = 3;
pri_num = 2;
for(i = 5;i <10000; i += 2)
{
na = 0;
temp = (int)sqrt(i) + 1;
for (j = 1; j < pri_num && pri[j] < temp; j++)
{
if(i % pri[j] == 0)
{
na = 1;
break;
}
}
if(!na)
pri[pri_num++] = i;
}
}
int is_pri(int n)
{
int i;
int temp;
if(n == 1)
return 0;
temp = (int)sqrt(n) + 1;
for(i = 0; i < pri_num && pri <= temp;i++)
if(n % pri == 0 && n !=pri)
return 0;
return 1;
}
main()
{
double fibo[22001];
int i;
int index;
int n;
double temp[2];
double ulimit;
temp[0] = 0;
temp[1] = 1;
index = 0;
prime();
ulimit = pow(10,MAX);
for(i = 2; index < 22001;i++)
{
temp[i % 2] = temp[0] + temp[1];
while(temp[i%2] > ulimit)
temp[0]/=10,temp[1]/=10;
if(is_pri(i))
{
fibo[index++] = temp[i % 2];
}
}
fibo[0] = 2;
fibo[1] = 3;
while(scanf("%d", &n) == 1)
{
ulimit = pow(10,9);
while(fibo[n  1] > ulimit )
fibo[n  1] /= 10;
printf("%.0f\n",fibo[n  1]);
}
}

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
10236
Hi, I always got WA, maybe this is precision error problem.
Can anyone tell me what the output for this test case:
10133
9912
7710
1929
19991
20011
91
1771
2771
899
1019
113
7192
9412
761
1991
57
Thanks
Can anyone tell me what the output for this test case:
10133
9912
7710
1929
19991
20011
91
1771
2771
899
1019
113
7192
9412
761
1991
57
Thanks