Brute forces perhaps

I guess you all familiar with the Fibonacci sequence.

For those who haven't known this term yet, the Fibonacci sequence is a sequence of numbers which F ( 0 ) = 0 F(0)=0 , F ( 1 ) = 1 F(1)=1 and for n 2 n \ge 2 , F ( n ) = F ( n 1 ) + F ( n 2 ) F(n)=F(n-1)+F(n-2) .

So, here's my question:

If F ( x ) F(x) is the largest prime Fibonacci number where x 200 x \le 200 , find log x F ( x ) \left\lfloor \log _{ x }{ F(x) } \right\rfloor .

This problem belongs to this set


The answer is 13.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Maria Kozlowska
Jul 23, 2015

This can be solved just by number theory methods. The last Fibonacci prime before 200 has index 137 OEIS .

Closed-form expression can be used to calculate the logarithm. Since for large numbers the second term of the closed form expression can be ignored, it becomes: l o g 1 3 7 ( φ 137 / 5 ) = 13.23608812 log{_1}{_3}{_7} ( \varphi ^{137} / \sqrt{5}) = 13.23608812

where φ = 1 + 5 2 1.61803 39887 \varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots

Pranjal Jain
Apr 29, 2015

I have Fast Fibonacci algorithm to calculate n-th Fibonacci Number but no Prime Testing Algorithm for so big numbers. So I calculated F ( 200 ) F(200) and then checked out the list of prime Fibonacci on oeis .

@Agnishom Chattopadhyay Any idea?

Pranjal Jain - 6 years, 1 month ago

Log in to reply

I used Mathematica for this one.

However, algorithms like AKS or Miller-Rabin should be helpful. See this: Link

Agnishom Chattopadhyay - 6 years, 1 month ago

I too checked out OEIS to find that the last fibonacci prime before n = 200 n=200 is k = 137 k=137 . Rest was computed using Binet's formula.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import math

def fib(n):
    if(n==0):
        return 0
    else:
        #Binet's formula
        return math.floor((1/math.sqrt(5)*((1+math.sqrt(5))**n - (1-math.sqrt(5))**n)/2**n))

print("ans : ",math.floor(math.log(fib(137))/math.log(137)))

John Phillips
Sep 28, 2015

Since log (x)=x^n/1-n then n would have to be a prime number no larger than 13. At least, this is what made sense in my head, I just don't know exactly how to write the notation.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...