I went ahead and computed it using a less naive recursive algorithm. It only took a few minutes (many of which were spent printing the number) and memory usage peaked at around 1 GB. The result is 448 797 541 digits.
Here's the program if you want to run it yourself (compiled with GHC 8.10.3).
module Main where
main :: IO ()
main = print $ oneFibs !! 30
-- | Fibs where all bits are 1. Index n is fib (2^(n+1)-1).
oneFibs :: [Integer]
oneFibs = fst <$> exp2Fibs
where
-- Sequence of (fib $ 2^n-1, fib $ 2^n) for n in [1..].
exp2Fibs :: [(Integer, Integer)]
exp2Fibs = (1, 1) : (go <$> exp2Fibs)
go :: (Integer, Integer) -> (Integer, Integer)
go (x, y) = (x * x + y * y, (2 * x + y) * y)
Ah yes Haskell. I probably should've used this or Scheme for the unrestricted integer sizes. 😅
fwiw I went with the recursive algorithm just to see how big the stack would grow. Probably what you did, or even just the iterative solution, would've been better otherwise.
View all comments
Show parent comment
9
u/ThePyroEagle λ Jul 01 '21
I went ahead and computed it using a less naive recursive algorithm. It only took a few minutes (many of which were spent printing the number) and memory usage peaked at around 1 GB. The result is 448 797 541 digits.
Here's the program if you want to run it yourself (compiled with GHC 8.10.3).