{-# OPTIONS -O3 -XStrict -XBangPatterns #-}
 
import Data.List (sortBy, foldl')
import Data.Function (on)
 
main = let (r,t) = nthHam 1000000000000 in print t -- >> print (trival t)
 
trival (i,j,k) = 2^i * 3^j * 5^k
 
nthHam :: Int -> (Double, (Int, Int, Int))            -- ( 64bit: use Int!!!     NB! )
nthHam n                                                  -- n: 1-based: 1,2,3...
  | n <= 0    = error $ "n is 1--based: must be n > 0: " ++ show n
  | n < 2     = ( 0.0, (0, 0, 0) ) -- trivial case so estimation works for rest
  | w >= 1    = error $ "Breach of contract: (w < 1):  " ++ show w
  | m <  0    = error $ "Not enough triples generated: " ++ show ((c,n) :: (Int, Int))
  | m >= nb   = error $ "Generated band is too narrow: " ++ show (m,nb)
  | otherwise = sortBy (flip compare `on` fst) b !! m     -- m-th from top in sorted band
 where  
  lb3 = logBase 2 3;  lb5 = logBase 2 5;  lb30_2 = logBase 2 30 / 2
  v = (6*lb3*lb5* fromIntegral n)**(1/3) - lb30_2         -- estimated logval, base 2
  estval n = (v + (1/v), 2/v)                             -- the space tweak! (thx, GBG!)
  (hi,w) = estval n                                       --   hi > logval > hi-w
  m      = fromIntegral (c - n)                           -- target index, from top
  nb     = length (b :: [(Double, (Int, Int, Int))])      -- length of the band
  (c,b) = foldl_ (\(c,b) (i,t)-> let c2=c+i in c2 `seq`   -- ( total count, the band )
                     case t of []-> (c2,b);[v]->(c2,v:b) ) (0,[])  -- ( =~= mconcat )
            [ ( fromIntegral i+1,                         -- total triples w/ this (j,k)
                [ (r,(i,j,k)) | frac < w ] )              -- store it, if inside band
              | k <- [ 0 .. floor ( hi   /lb5) ],  let p = fromIntegral k*lb5,    
                j <- [ 0 .. floor ((hi-p)/lb3) ],  let q = fromIntegral j*lb3 + p,
                let (i,frac) = pr  (hi-q) ;            r = hi - frac  -- r = i + q 
            ] where  pr      = properFraction             -- pr 1.24 => (1,0.24)
                     foldl_  = foldl'
 

ey0jIE9QVElPTlMgLU8zIC1YU3RyaWN0IC1YQmFuZ1BhdHRlcm5zICMtfQoKaW1wb3J0IERhdGEuTGlzdCAoc29ydEJ5LCBmb2xkbCcpCmltcG9ydCBEYXRhLkZ1bmN0aW9uIChvbikKCm1haW4gPSBsZXQgKHIsdCkgPSBudGhIYW0gMTAwMDAwMDAwMDAwMCBpbiBwcmludCB0IC0tID4+IHByaW50ICh0cml2YWwgdCkKCnRyaXZhbCAoaSxqLGspID0gMl5pICogM15qICogNV5rCgpudGhIYW0gOjogSW50IC0+IChEb3VibGUsIChJbnQsIEludCwgSW50KSkgICAgICAgICAgICAtLSAoIDY0Yml0OiB1c2UgSW50ISEhICAgICBOQiEgKQpudGhIYW0gbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLS0gbjogMS1iYXNlZDogMSwyLDMuLi4KICB8IG4gPD0gMCAgICA9IGVycm9yICQgIm4gaXMgMS0tYmFzZWQ6IG11c3QgYmUgbiA+IDA6ICIgKysgc2hvdyBuCiAgfCBuIDwgMiAgICAgPSAoIDAuMCwgKDAsIDAsIDApICkgLS0gdHJpdmlhbCBjYXNlIHNvIGVzdGltYXRpb24gd29ya3MgZm9yIHJlc3QKICB8IHcgPj0gMSAgICA9IGVycm9yICQgIkJyZWFjaCBvZiBjb250cmFjdDogKHcgPCAxKTogICIgKysgc2hvdyB3CiAgfCBtIDwgIDAgICAgPSBlcnJvciAkICJOb3QgZW5vdWdoIHRyaXBsZXMgZ2VuZXJhdGVkOiAiICsrIHNob3cgKChjLG4pIDo6IChJbnQsIEludCkpCiAgfCBtID49IG5iICAgPSBlcnJvciAkICJHZW5lcmF0ZWQgYmFuZCBpcyB0b28gbmFycm93OiAiICsrIHNob3cgKG0sbmIpCiAgfCBvdGhlcndpc2UgPSBzb3J0QnkgKGZsaXAgY29tcGFyZSBgb25gIGZzdCkgYiAhISBtICAgICAtLSBtLXRoIGZyb20gdG9wIGluIHNvcnRlZCBiYW5kCiB3aGVyZSAgCiAgbGIzID0gbG9nQmFzZSAyIDM7ICBsYjUgPSBsb2dCYXNlIDIgNTsgIGxiMzBfMiA9IGxvZ0Jhc2UgMiAzMCAvIDIKICB2ID0gKDYqbGIzKmxiNSogZnJvbUludGVncmFsIG4pKiooMS8zKSAtIGxiMzBfMiAgICAgICAgIC0tIGVzdGltYXRlZCBsb2d2YWwsIGJhc2UgMgogIGVzdHZhbCBuID0gKHYgKyAoMS92KSwgMi92KSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLS0gdGhlIHNwYWNlIHR3ZWFrISAodGh4LCBHQkchKQogIChoaSx3KSA9IGVzdHZhbCBuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLS0gICBoaSA+IGxvZ3ZhbCA+IGhpLXcKICBtICAgICAgPSBmcm9tSW50ZWdyYWwgKGMgLSBuKSAgICAgICAgICAgICAgICAgICAgICAgICAgIC0tIHRhcmdldCBpbmRleCwgZnJvbSB0b3AKICBuYiAgICAgPSBsZW5ndGggKGIgOjogWyhEb3VibGUsIChJbnQsIEludCwgSW50KSldKSAgICAgIC0tIGxlbmd0aCBvZiB0aGUgYmFuZAogIChjLGIpID0gZm9sZGxfIChcKGMsYikgKGksdCktPiBsZXQgYzI9YytpIGluIGMyIGBzZXFgICAgLS0gKCB0b3RhbCBjb3VudCwgdGhlIGJhbmQgKQogICAgICAgICAgICAgICAgICAgICBjYXNlIHQgb2YgW10tPiAoYzIsYik7W3ZdLT4oYzIsdjpiKSApICgwLFtdKSAgLS0gKCA9fj0gbWNvbmNhdCApCiAgICAgICAgICAgIFsgKCBmcm9tSW50ZWdyYWwgaSsxLCAgICAgICAgICAgICAgICAgICAgICAgICAtLSB0b3RhbCB0cmlwbGVzIHcvIHRoaXMgKGosaykKICAgICAgICAgICAgICAgIFsgKHIsKGksaixrKSkgfCBmcmFjIDwgdyBdICkgICAgICAgICAgICAgIC0tIHN0b3JlIGl0LCBpZiBpbnNpZGUgYmFuZAogICAgICAgICAgICAgIHwgayA8LSBbIDAgLi4gZmxvb3IgKCBoaSAgIC9sYjUpIF0sICBsZXQgcCA9IGZyb21JbnRlZ3JhbCBrKmxiNSwgICAgCiAgICAgICAgICAgICAgICBqIDwtIFsgMCAuLiBmbG9vciAoKGhpLXApL2xiMykgXSwgIGxldCBxID0gZnJvbUludGVncmFsIGoqbGIzICsgcCwKICAgICAgICAgICAgICAgIGxldCAoaSxmcmFjKSA9IHByICAoaGktcSkgOyAgICAgICAgICAgIHIgPSBoaSAtIGZyYWMgIC0tIHIgPSBpICsgcSAKICAgICAgICAgICAgXSB3aGVyZSAgcHIgICAgICA9IHByb3BlckZyYWN0aW9uICAgICAgICAgICAgIC0tIHByIDEuMjQgPT4gKDEsMC4yNCkKICAgICAgICAgICAgICAgICAgICAgZm9sZGxfICA9IGZvbGRsJwo=