CubeSums.hs

module CubeSums where

-- Note: Runtime on 64-bit can be reduced by 25-35% by using Int.
-- 64-bit Int would need ~70 hours of number-crunching to overflow,
-- but 32-bit Int can overflow in less than a second.
cube :: Integer -> Integer
cube x = x * x * x
cubeSums = [[cube x + cube y | y <- [0..x]] | x <- [0..]]

xmerge (a:as) bs = a:(merge as bs)

merge as [] = as
merge [] bs = bs
merge as@(ah:at) bs@(bh:bt)
  | ah <= bh  = ah:(merge at bs)
  | otherwise = bh:(merge as bt)

fancyFold f (x:xs) = x `f` (fancyFold f ys `f` fancyFold f zs)
  where (ys, zs) = bifurcate xs
        bifurcate (a:b:cs) = (a:as, b:bs)
          where (as, bs) = bifurcate cs

dups (a:as)
  | a == head as = (a:) $ dups $ dropWhile (== a) as
  | otherwise    = dups as

-- Main routines.  (FIXME: parse argv or something)

howMany = 100000

-- Quickly: (1.2s for howMany = 5000)
main = mapM_ print $ take howMany $ dups $ fancyFold xmerge cubeSums

-- Slowly: (7s for howMany = 5000)
--main = mapM_ print $ take howMany $ dups $ foldr1 xmerge cubeSums