Page 2 of 2
Posted: Thu Jun 12, 2003 10:48 am
by Alexander Denisjuk
I like this problem very much, specially the pair
6879 --- 842347072
In fact the correspondent Fibonacci number begins with 84234707299956....
So, you really should have good accuracy. But how did the problemsetter know about this Fib number?
My experience in getting AC is the following: use long double, do not trust any built-in functions like exp, log, even sqrt and abs. Write everything by yourself.
By the way, the proof of the basic fact, i. e. GCD(F_k,F_n)=F_{GCD(k,n)} is not very hard. Just apply Euclide's algorithm GCD(F_{k+m},F_k)=GCD(F_{k+m}-F_k,F_k) and so on.
10236
Posted: Fri Aug 13, 2004 8:27 pm
by minskcity
Does anybody know how to compute first nine digits of 250000th fibonachi number?
Posted: Tue May 09, 2006 12:40 am
by Quantris
gah, this was tough because the precision is dependent on the compiler version.
tough cases include 9307 -- 495091651, 15086 -- 920759405, and 15520 -- 386616082.
At least, those are the three that I "special cased"
Posted: Thu Aug 03, 2006 6:55 am
by Jan
Got Acc...
Input:
Output:
Code: Select all
208214663
139876647
516212329
117851144
Edit : The above cases are correct.
10236 - The Fibonacci Primes
Posted: Sat Oct 14, 2006 1:12 pm
by micheal_sunny
can anyone tell me how to solve the problem
i konw the algorithm which can gets n-th fib in lgn,but i met overflow problem when i want to calculate the all digits
is there any secret or formula which i dont konw,please tell me
Thanks for watch and reply
Re: a hint
Posted: Sun Jan 07, 2007 4:03 pm
by TimeString
minskcity wrote:Does anybody know how to compute first nine digits of 250000th fibonachi number?
You can use double.
Posted: Tue Jan 23, 2007 5:54 am
by Jan
Finally got accepted with a completely different approach (no floating point calculations). Thanks.
Posted: Thu Nov 08, 2007 10:50 pm
by mukeshtiwari
Getting TLE. plz someone reply me , what is wrong with my code and algorithm .
according to problem description, all fibonacci primes will occur at prime postions so i calculated first 22000 primes . then i use the following formula (
http://mathworld.wolfram.com/FibonacciNumber.html) F(n)=phi^n/sqrt(5) where phi=(1+sqrt(5))/2 and calculated first 9 digits as explained in the posts. There is some precison issue also in fun2() which gives wrong output for inputs 22000,6879. so how to avoid precision issue . here is my code .
Code: Select all
#include<cstdio>
#include<cmath>
long double a,c;
double fun2(int n)
{
int k;
long double v,d;
for(k=0;;k++)
{
v=(long double)n*log10l(a)-(log10l(c)+(long double)k);
if(v<9)
break;
}
d=powl(10,v);
d=floor(d+0.5);
return d;
}
int fun1(int n)
{
int i;
if(n==1)
return 0;
if(n==2)
return 1;
if(n%2==0)
return 0;
for(i=3;i*i<=n;i+=2)
if(n%i==0)
return 0;
return 1;
}
int main()
{
int prime[22010],count=0,i,n;
long double fib[22010];
a=(1+sqrtl(5))/2;
c=sqrtl(5);
for(i=1;;i++)
{
if(fun1(i))
{
prime[count++]=i;
if(count==22000)
break;
}
}
for(i=0;i<22000;i++)
{
fib[i]=fun2(prime[i]);
}
while(scanf("%d",&n)==1)
printf("%.0llf\n",fib[n-1]);
}
Posted: Sun Nov 11, 2007 7:22 am
by mukeshtiwari
no response
Posted: Sun Nov 11, 2007 1:42 pm
by rio
Code: Select all
double fun2(int n)
{
int k;
long double v,d;
for(k=0;;k++)
{
v=(long double)n*log10l(a)-(log10l(c)+(long double)k);
if(v<9)
break;
}
d=powl(10,v);
d=floor(d+0.5);
return d;
}
You don't need the k loop. This loop is causing TLE.
----
Rio
Posted: Sun Nov 11, 2007 5:29 pm
by mukeshtiwari
so is it possible to get k in o(1) time or should i use binary search . plz suggest me how to calculate k because now i am exhausted with this problem.
Posted: Wed Nov 21, 2007 10:31 am
by rio
mukeshtiwari wrote:so is it possible to get k in o(1) time or should i use binary search . plz suggest me how to calculate k because now i am exhausted with this problem.
You could get k in O(1).
Hint:
Code: Select all
10^12.34 = 10^(8.34 + 4) = 10^8.34 * 10^4
-----
Rio
Posted: Wed Nov 21, 2007 5:24 pm
by mukeshtiwari
thnkx rio .
Re: 10236 - The Fibonacci Primes
Posted: Sun Mar 13, 2016 9:05 am
by shiguowang
prove : <<the art of computer programming>> by Donald E.Knuth chapter 1.2.8 Theorem A