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

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:

Post by Alexander Denisjuk » Thu Jun 12, 2003 10:48 am

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.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

10236

Post by minskcity » Fri Aug 13, 2004 8:27 pm

Does anybody know how to compute first nine digits of 250000th fibonachi number? :-?

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Tue May 09, 2006 12:40 am

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" :)

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Aug 03, 2006 6:55 am

Got Acc...

Input:

Code: Select all

22000
21000
100
233
Output:

Code: Select all

208214663
139876647
516212329
117851144
Edit : The above cases are correct.
Last edited by Jan on Tue Jan 23, 2007 5:57 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

micheal_sunny
New poster
Posts: 7
Joined: Sat Oct 14, 2006 11:24 am

10236 - The Fibonacci Primes

Post by micheal_sunny » Sat Oct 14, 2006 1:12 pm

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

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Re: a hint

Post by TimeString » Sun Jan 07, 2007 4:03 pm

minskcity wrote:Does anybody know how to compute first nine digits of 250000th fibonachi number? :-?
You can use double.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Jan 23, 2007 5:54 am

Finally got accepted with a completely different approach (no floating point calculations). Thanks.
Ami ekhono shopno dekhi...
HomePage

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Thu Nov 08, 2007 10:50 pm

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

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Sun Nov 11, 2007 7:22 am

no response :(

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Nov 11, 2007 1:42 pm

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

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Sun Nov 11, 2007 5:29 pm

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Nov 21, 2007 10:31 am

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

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Wed Nov 21, 2007 5:24 pm

thnkx rio .

shiguowang
New poster
Posts: 2
Joined: Sun Mar 08, 2015 10:54 am

Re: 10236 - The Fibonacci Primes

Post by shiguowang » Sun Mar 13, 2016 9:05 am

prove : <<the art of computer programming>> by Donald E.Knuth chapter 1.2.8 Theorem A

Post Reply

Return to “Volume 102 (10200-10299)”