10236 - The Fibonacci Primes

[ftomi]

What are the first nine digits of number 1234567890?

[shahriar_manzoor]

123456789

[ftomi]

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

[..]

I think you are thinking too mcuh, just follow the problem specification is OK,
output for 8 is 4181

[Ivan Golubev]

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]

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]

Thanks! It's the same. Looks like I have a precision error problem...

[chang]

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.
Thanks in advance.

chang

[Ivan Golubev]

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]

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]

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]

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

[tinapon]

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]

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]

hemmm....