Euler Solution 25

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 25

Find the index of the first Fibonacci number with 1000 digits.

Haskell by SanguineV

Runtime: 325ms

{- Generate a lazy list of indexes and values of Fibonacci numbers.
 - Start with F(1) = 1 and F(2) = 1, then generate by using zipWith
 -}
fibs :: [(Integer, Integer)]
fibs = (1,1):(2,1):fibs'
  where
    fibs' = zipWith (\(x1,y1) (x2,y2) -> (x1+2,y1+y2)) fibs (tail fibs)

{- Take the first F(n) with 1000 digits, print out the pair of its index and
 - the number. -}
main = print (head (filter (\(x,y) -> length (show y) == 1000) fibs))


In case you are just want to know what the number is and not the index, the first 1000 digit Fibonacci number is:

10700662663827589367649805844573968850836838966321516650132352033753145206046940406218
89147582489792657804694888177591957484336466672569959512996030461262748092482186144069
43305123477444275027378175308757939166619214925918675955396642283714894311307469950343
95470019854326097230672901928705264472437261177158218255484911205250132014786129659313
81792235559657452039506137551467837543229119602129934048260706175397706847068202895486
90266618543512452190036948064135744747091170761976694569107009802439343961747410373691
25032313655321647736970231677550515951735184605799549194109677783732296657965816465139
03488154256310184224190259846088000110186255550245493937113651657039447629584714548523
42595042858242530608354443542821261100899286379504800689433030977321783486454311320576
56598684562886168087186938352973506439862976406600007235629179052070511640776148124918
85830945940566688339109350944456576357666151619317753792891661581327159616877487983821
820492520348473874384736771934512787029218636250627816

Python by Althalus

Runtime: 1 second

import time
start_time = time.time()

def satisfied(num):
        if len(str(num)) >= 1000:
                return True
        return False


prev,cur,count = 0,1,1

while satisfied(cur) != True:
        prev,cur,count = cur,prev+cur,count+1
print(count)
run_time = time.time() - start_time
print (run_time)
Personal tools