First Fibonnaci number whose first and last 200 digits form prime numbers
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

Please provide the Ruby code to calculate the first Fibonnaci number whose first 200 digits and last 200 digits form distinct prime numbers.

The algorithm should return k, where F(k) is the Fibonnacci number in question.

Also, provide the Fibonnacci number in your solution as well.

Furthermore, the program should be capable of solving the problem in under a minute or so on a decent laptop.

Thanks!

So my understanding of this question is that the Fibonnaci number is at least 200 digits long?
alex 7 years ago
Yes, actually 201 digits since the primes have to be distinct.
bevan 7 years ago
The method is_prime of the solution returns true to non prime numbers, like 15.
andycds 7 years ago
awarded to alex
Tags
ruby

Crowdsource coding tasks.

1 Solution

Winning solution

This code should work for you

#!/usr/bin/ruby

def is_prime(number)
    $i = 2
    while $i < number do
        if number % $i == 0 && $i != number
            return false
        else
             return true
        end
        $i +=1;
    end
    return true
end

def fibonacci(n)
    fibonacci_seq = Array.new()
    for i in 0..n
        if i == 0
            the_number = 1
        elsif i == 1
            the_number = 1
        else
            the_number = fibonacci_seq[i-1].to_i + fibonacci_seq[i-2].to_i
        end
        fibonacci_seq.push(the_number)
    end
    return fibonacci_seq
end

# generate a list of fibonacci sequences first
listOfFib = fibonacci(1952)
print "Generated List\n"

# lets check each term if it matches the case
numOfItems = listOfFib.count()
print "    Number if items in list: #{numOfItems}\n"
print "Starting Checking...\n\n"

for i in 0..numOfItems
    lengthOfN = listOfFib[i].to_s.length
    if lengthOfN > 200
        first200digits = listOfFib[i].to_s.split(//).first(200).join().to_i
        last200digits = listOfFib[i].to_s.split(//).last(200).join().to_i
        if is_prime(first200digits) == true && is_prime(last200digits) == true
            print "#{i}-th term: #{listOfFib[i]} works!\n"
            print "    length: #{lengthOfN}\n\n"
            break
        end
    end
end

print "\n"

The answer to the problem is the 963th term.

963-th term: 1301967666079246999739025509736981974513806323327310792803025425887225709131040982032655852614954462201163281866373391986529297423769475808932761815084406478437505702622886684757604851321223369645403523 works!
    length: 202

if you want to see the next few terms that work, remove the break on line 48.