The first evidence of x-ray harmonic radiation extending to 3.3 A, 3.8 keV (order n > 3200) from petawatt class laser-solid interactions is presented, exhibiting relativistic limit efficiency scaling (eta similar to n(-2.5)-n(-3)) at multi-keV energies. This scaling holds up to a maximum order, n(RO)similar to 8(1/2)gamma(3), where gamma is the relativistic Lorentz factor, above which the first evidence of an intensity dependent efficiency rollover is observed. The coherent nature of the generated harmonics is demonstrated by the highly directional beamed emission, which for photon energy h nu > 1 keV is found to be into a cone angle similar to 4 degrees, significantly less than that of the incident laser cone (20 degrees).