{-#LANGUAGE TypeOperators#-}
{-#LANGUAGE DataKinds#-}

module Problem700 where

import Data.Array
import Data.Modular
import Data.Maybe

type ModN = Integer / 4503599627370517

b = 4503599627370517 :: Integer
a = 1504170715041707 :: ModN
a' = fromJust $ inv (-a)

bigOnes = take 16 $ iterate (\x -> head $ filter (< x) $ map (\n -> x + a * n) [1 ..]) a

smallLim = last bigOnes

convert :: ModN -> Int
convert = fromIntegral . unMod

deltas :: Array Int ModN
deltas = listArray (1, convert smallLim) (scanl1 min $ iterate (+ a') a')


smallOnes =
    tail $ takeWhile (> 0) $ iterate (\c -> c + a * (deltas ! convert c)) smallLim


main :: IO ()
main = print $ sum (smallOnes ++ bigOnes)



{-
-}

{-
ak = bq + r
0 <= r <= x
0 <= ak - bq <= x
0 <= k - bq/a <= x/a
bq/a <= k <= (bq+x)/a
bq <= k <= bq+x
also an in [-1, -2, ... -x]
so n in [-a', -2a', ... -xa']
-}

{-
(1,1504170715041707)
(3,8912517754604)
(506,2044785486369)
(2527,1311409677241)
(4548,578033868113)
(11117,422691927098)
(17686,267349986083)
(24255,112008045068)
(55079,68674149121)
(85903,25340253174)
(202630,7346610401)
(724617,4046188430)
(1246604,745766459)
(6755007,428410324)
(12263410,111054189)
(42298633,15806432)
(326125654,15397267)
(609952675,14988102)
(893779696,14578937)
(1177606717,14169772)
(1461433738,13760607)

2
503
2021
2021
6569
6569
6569
30824
30824
116727
521987
521987
5508403
5508403
30035223
-}
