## 10236 - The Fibonacci Primes

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
What are the first nine digits of number 1234567890?

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

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
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 great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I think you are thinking too mcuh, just follow the problem specification is OK,
output for 8 is 4181

Ivan Golubev
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

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am
My output is as follows. I did not check with yours. Visual comparision is hard

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

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Thanks! It's the same. Looks like I have a precision error problem...

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am
Hi !
Can any body inform how this problem could be solved ! What's the main idea behind it? I tried a lot, but failed tired to find a solution.

chang

Ivan Golubev
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.

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am
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

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am
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

Ivan Golubev
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.

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).

tinapon
New poster
Posts: 4
Joined: Tue Mar 25, 2003 5:20 pm

### 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]);
}
}

Red Scorpion
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

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
hemmm....