We present the size distributions of metal ion-doped noble gas clusters of the form M+Xn (M = Mg, K and X = Ar, Kr, Xe) studied with time-of-flight mass spectrometry. All the recorded spectra exhibit magic number patterns, which change gradually from the familiar icosahedral sequence N = n + 1 = 13,19,23,26,29,32 to another one that exhibits the magic numbers N = 9,10,11,17,21,24,26,27,30, as the atomic size ratio of the metal ion to the noble gas atom decreases. Furthermore, as the cluster size N increases, the new sequence seems to convert again to the icosahedral one at some critical cluster size. Molecular dynamics simulations using pairwise additive Lennard-Jones potentials are performed in order to investigate the stability and the geometrical structure of these systems as a function of radii ratio, interaction energy, and cluster size. The results obtained are in very good agreement with the experimental ones and indicate that when the size of the dopant is comparable to that of the noble gas atoms then the clusters exhibit icosahedral geometries, while for smaller ratios, clusters having a geometry based on a capped square antiprism (CSA) are more stable.