We present systematic ab initio calculations for the interaction energies of 3d adatoms on the Cu(001) surface. The calculations are based on density-functional theory in the local-density approximation and apply the Korringa-Kohn-Rostoker Green's function method. Short-range interactions and oscillatory long-range interactions between magnetic adatoms are calculated. We demonstrate that magnetism has a strong impact on the interaction energies. Total-energy calculations show that the atomic exchange process at the surface between all the 3d adatoms and the Cu substrate is energetically favorable even for metals immiscible in bulk.