Posted:

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

Page **1** of **2**

Posted: **Wed Mar 20, 2002 2:35 pm**

What are the first nine digits of number 1234567890?

Posted: **Wed Mar 20, 2002 2:56 pm**

123456789

Posted: **Wed Mar 20, 2002 4:37 pm**

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

Posted: **Wed Mar 20, 2002 8:20 pm**

I think you are thinking too mcuh, just follow the problem specification is OK,

output for 8 is 4181

output for 8 is 4181

Posted: **Thu Mar 21, 2002 3:19 pm**

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

Posted: **Thu Mar 21, 2002 3:30 pm**

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

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**

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

Posted: **Fri Apr 05, 2002 3:31 pm**

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

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**

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.

Posted: **Sat Apr 06, 2002 4:52 pm**

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

Posted: **Sat Apr 06, 2002 7:35 pm**

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

Posted: **Tue Apr 09, 2002 1:21 am**

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

Posted: **Wed Mar 26, 2003 2:41 pm**

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

if(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]);

}

}

Posted: **Sat May 17, 2003 4:32 am**

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

Posted: **Mon Jun 09, 2003 9:25 am**

hemmm....