f 1 = 1
f 3 = 3
f n | n `elem` c2  = let x = extract2 n
                     in f x
    | n `elem` c41 = let x = extract41 n
                     in 2*f(2*x+1) - (f x)
    | n `elem` c43 = let x = extract43 n
                     in 3*f(2*x+1) - 2*(f x)
    | otherwise    = -1
  where
    c2  = map (*2) [1..]
    c41 = map ((+1) . (*4)) [1..]
    c43 = map ((+3) . (*4)) [1..]
 
    extract2  = (`div` 2)
    extract41 = (`div` 4) . subtract 1
    extract43 = (`div` 4) . subtract 3
 
euler463 n = sum . take n . map f $ [1..]
 
main = do
  -- writeln 8
  writeln 100
  -- writeln (3^37)
    where
      writeln = putStrLn . show . f

ZiAxID0gMQpmIDMgPSAzCmYgbiB8IG4gYGVsZW1gIGMyICA9IGxldCB4ID0gZXh0cmFjdDIgbgogICAgICAgICAgICAgICAgICAgICBpbiBmIHgKICAgIHwgbiBgZWxlbWAgYzQxID0gbGV0IHggPSBleHRyYWN0NDEgbgogICAgICAgICAgICAgICAgICAgICBpbiAyKmYoMip4KzEpIC0gKGYgeCkKICAgIHwgbiBgZWxlbWAgYzQzID0gbGV0IHggPSBleHRyYWN0NDMgbgogICAgICAgICAgICAgICAgICAgICBpbiAzKmYoMip4KzEpIC0gMiooZiB4KQogICAgfCBvdGhlcndpc2UgICAgPSAtMQogIHdoZXJlCiAgICBjMiAgPSBtYXAgKCoyKSBbMS4uXQogICAgYzQxID0gbWFwICgoKzEpIC4gKCo0KSkgWzEuLl0KICAgIGM0MyA9IG1hcCAoKCszKSAuICgqNCkpIFsxLi5dCiAgICAKICAgIGV4dHJhY3QyICA9IChgZGl2YCAyKQogICAgZXh0cmFjdDQxID0gKGBkaXZgIDQpIC4gc3VidHJhY3QgMQogICAgZXh0cmFjdDQzID0gKGBkaXZgIDQpIC4gc3VidHJhY3QgMwoKZXVsZXI0NjMgbiA9IHN1bSAuIHRha2UgbiAuIG1hcCBmICQgWzEuLl0KCm1haW4gPSBkbwogIC0tIHdyaXRlbG4gOAogIHdyaXRlbG4gMTAwCiAgLS0gd3JpdGVsbiAoM14zNykKICAgIHdoZXJlCiAgICAgIHdyaXRlbG4gPSBwdXRTdHJMbiAuIHNob3cgLiBm