{-# OPTIONS -O2 -XBangPatterns #-}
 
import Data.Word
import Data.List (sortBy)
import Data.Function (on)
 
main = let t = nthHam 1000000000000 in print t
 
lb3 = logBase 2 3;  lb5 = logBase 2 5
lbrt30 = logBase 2 $ sqrt 30 :: Double -- estimate adjustment as per WP
-- logval (i,j,k)    = fromIntegral i + fromIntegral j*lb3 + fromIntegral k*lb5
trival (i,j,k)    = 2^i * 3^j * 5^k
estval2 n         = (6*lb3*lb5*n)**(1/3) - lbrt30 -- estimated logval, base 2
crctn n
    | n < 1000       = 0.509  -- empirical correction terms
    | n < 1000000    = 0.206
    | n < 1000000000 = 0.122  -- further divisions have little effect as already small
    | otherwise      = 0.105  -- very slowly decrease from this point for a billion
 
nthHam :: Word64 -> (Int, Int, Int)
nthHam n                                                   -- n: 1-based 1,2,3...
  | n < 2     = case n of
                  0 -> error "nthHam:  Argument is zero!"
                  _ -> (0, 0, 0)                           -- trivial case for 1
  | m <  0    = error $ "Not enough triples generated: " ++ show (c,n)
  | m >= nb   = error $ "Generated band is too narrow: " ++ show (m,nb)
  | otherwise = case res of (_, tv) -> tv -- 2^i * 3^j * 5^k
 where
  (fr,est)= (crctn n, estval2 $ fromIntegral n)            -- fraction of log2 error, est val
  (hi,lo)  = (estval2 (fromIntegral n + fr*est), 2*est-hi) -- hi > logval2 >= lo
  (c,b)    = f ()
  f () =
    let klmt = floor (hi/lb5) in
    let loopk k !ck bndk =
          if k > klmt then (ck, bndk) else
          let p = fromIntegral k*lb5; jlmt = floor ((hi-p)/lb3) in
          let loopj j !cj bndj =
                if j > jlmt then loopk (k+1) cj bndj else
                let q = fromIntegral j*lb3 + p in
                let (i, frac) = properFraction (hi-q); r = hi-frac in
                if r < lo then loopj (j+1) (fromIntegral i+cj+1) bndj else
                loopj (j+1) (fromIntegral i+cj+1) ((r,(i,j,k)):bndj) in
          loopj 0 ck bndk in
    loopk 0 0 []
  (m,nb)    = ( fromIntegral $ c - n, length b )           -- m 0-based from top, |band|
  (s,res)   = ( sortBy (flip compare `on` fst) b, s!!m )   -- sorted decreasing, result

ey0jIE9QVElPTlMgLU8yIC1YQmFuZ1BhdHRlcm5zICMtfQogCmltcG9ydCBEYXRhLldvcmQKaW1wb3J0IERhdGEuTGlzdCAoc29ydEJ5KQppbXBvcnQgRGF0YS5GdW5jdGlvbiAob24pCiAKbWFpbiA9IGxldCB0ID0gbnRoSGFtIDEwMDAwMDAwMDAwMDAgaW4gcHJpbnQgdAogCmxiMyA9IGxvZ0Jhc2UgMiAzOyAgbGI1ID0gbG9nQmFzZSAyIDUKbGJydDMwID0gbG9nQmFzZSAyICQgc3FydCAzMCA6OiBEb3VibGUgLS0gZXN0aW1hdGUgYWRqdXN0bWVudCBhcyBwZXIgV1AKLS0gbG9ndmFsIChpLGosaykgICAgPSBmcm9tSW50ZWdyYWwgaSArIGZyb21JbnRlZ3JhbCBqKmxiMyArIGZyb21JbnRlZ3JhbCBrKmxiNQp0cml2YWwgKGksaixrKSAgICA9IDJeaSAqIDNeaiAqIDVeawplc3R2YWwyIG4gICAgICAgICA9ICg2KmxiMypsYjUqbikqKigxLzMpIC0gbGJydDMwIC0tIGVzdGltYXRlZCBsb2d2YWwsIGJhc2UgMgpjcmN0biBuCiAgICB8IG4gPCAxMDAwICAgICAgID0gMC41MDkgIC0tIGVtcGlyaWNhbCBjb3JyZWN0aW9uIHRlcm1zCiAgICB8IG4gPCAxMDAwMDAwICAgID0gMC4yMDYKICAgIHwgbiA8IDEwMDAwMDAwMDAgPSAwLjEyMiAgLS0gZnVydGhlciBkaXZpc2lvbnMgaGF2ZSBsaXR0bGUgZWZmZWN0IGFzIGFscmVhZHkgc21hbGwKICAgIHwgb3RoZXJ3aXNlICAgICAgPSAwLjEwNSAgLS0gdmVyeSBzbG93bHkgZGVjcmVhc2UgZnJvbSB0aGlzIHBvaW50IGZvciBhIGJpbGxpb24KIApudGhIYW0gOjogV29yZDY0IC0+IChJbnQsIEludCwgSW50KQpudGhIYW0gbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC0tIG46IDEtYmFzZWQgMSwyLDMuLi4KICB8IG4gPCAyICAgICA9IGNhc2UgbiBvZgogICAgICAgICAgICAgICAgICAwIC0+IGVycm9yICJudGhIYW06ICBBcmd1bWVudCBpcyB6ZXJvISIKICAgICAgICAgICAgICAgICAgXyAtPiAoMCwgMCwgMCkgICAgICAgICAgICAgICAgICAgICAgICAgICAtLSB0cml2aWFsIGNhc2UgZm9yIDEKICB8IG0gPCAgMCAgICA9IGVycm9yICQgIk5vdCBlbm91Z2ggdHJpcGxlcyBnZW5lcmF0ZWQ6ICIgKysgc2hvdyAoYyxuKQogIHwgbSA+PSBuYiAgID0gZXJyb3IgJCAiR2VuZXJhdGVkIGJhbmQgaXMgdG9vIG5hcnJvdzogIiArKyBzaG93IChtLG5iKQogIHwgb3RoZXJ3aXNlID0gY2FzZSByZXMgb2YgKF8sIHR2KSAtPiB0diAtLSAyXmkgKiAzXmogKiA1XmsKIHdoZXJlCiAgKGZyLGVzdCk9IChjcmN0biBuLCBlc3R2YWwyICQgZnJvbUludGVncmFsIG4pICAgICAgICAgICAgLS0gZnJhY3Rpb24gb2YgbG9nMiBlcnJvciwgZXN0IHZhbAogIChoaSxsbykgID0gKGVzdHZhbDIgKGZyb21JbnRlZ3JhbCBuICsgZnIqZXN0KSwgMiplc3QtaGkpIC0tIGhpID4gbG9ndmFsMiA+PSBsbwogIChjLGIpICAgID0gZiAoKQogIGYgKCkgPQogICAgbGV0IGtsbXQgPSBmbG9vciAoaGkvbGI1KSBpbgogICAgbGV0IGxvb3BrIGsgIWNrIGJuZGsgPQogICAgICAgICAgaWYgayA+IGtsbXQgdGhlbiAoY2ssIGJuZGspIGVsc2UKICAgICAgICAgIGxldCBwID0gZnJvbUludGVncmFsIGsqbGI1OyBqbG10ID0gZmxvb3IgKChoaS1wKS9sYjMpIGluCiAgICAgICAgICBsZXQgbG9vcGogaiAhY2ogYm5kaiA9CiAgICAgICAgICAgICAgICBpZiBqID4gamxtdCB0aGVuIGxvb3BrIChrKzEpIGNqIGJuZGogZWxzZQogICAgICAgICAgICAgICAgbGV0IHEgPSBmcm9tSW50ZWdyYWwgaipsYjMgKyBwIGluCiAgICAgICAgICAgICAgICBsZXQgKGksIGZyYWMpID0gcHJvcGVyRnJhY3Rpb24gKGhpLXEpOyByID0gaGktZnJhYyBpbgogICAgICAgICAgICAgICAgaWYgciA8IGxvIHRoZW4gbG9vcGogKGorMSkgKGZyb21JbnRlZ3JhbCBpK2NqKzEpIGJuZGogZWxzZQogICAgICAgICAgICAgICAgbG9vcGogKGorMSkgKGZyb21JbnRlZ3JhbCBpK2NqKzEpICgociwoaSxqLGspKTpibmRqKSBpbgogICAgICAgICAgbG9vcGogMCBjayBibmRrIGluCiAgICBsb29wayAwIDAgW10KICAobSxuYikgICAgPSAoIGZyb21JbnRlZ3JhbCAkIGMgLSBuLCBsZW5ndGggYiApICAgICAgICAgICAtLSBtIDAtYmFzZWQgZnJvbSB0b3AsIHxiYW5kfAogIChzLHJlcykgICA9ICggc29ydEJ5IChmbGlwIGNvbXBhcmUgYG9uYCBmc3QpIGIsIHMhIW0gKSAgIC0tIHNvcnRlZCBkZWNyZWFzaW5nLCByZXN1bHQ=