Page 1 of 2

Posted: Wed Mar 20, 2002 2:35 pm
by ftomi
What are the first nine digits of number 1234567890?

Posted: Wed Mar 20, 2002 2:56 pm
by shahriar_manzoor
123456789

Posted: Wed Mar 20, 2002 4:37 pm
by 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

Posted: Wed Mar 20, 2002 8:20 pm
by ..
I think you are thinking too mcuh, just follow the problem specification is OK,
output for 8 is 4181

Posted: Thu Mar 21, 2002 3:19 pm
by 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

Posted: Thu Mar 21, 2002 3:30 pm
by shahriar_manzoor
My output is as follows. I did not check with yours. Visual comparision is hard :smile:

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

Posted: Thu Mar 21, 2002 3:45 pm
by Ivan Golubev
Thanks! It's the same. Looks like I have a precision error problem...

Posted: Fri Apr 05, 2002 3:31 pm
by 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

Posted: Fri Apr 05, 2002 5:29 pm
by 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.

Posted: Sat Apr 06, 2002 4:52 pm
by 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

Posted: Sat Apr 06, 2002 7:35 pm
by 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

Posted: Tue Apr 09, 2002 1:21 am
by 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).

10236 WA

Posted: Wed Mar 26, 2003 2:41 pm
by tinapon
:o
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]);
}
}

10236

Posted: Sat May 17, 2003 4:32 am
by 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 :lol:

Posted: Mon Jun 09, 2003 9:25 am
by Red Scorpion
hemmm.... :-?