A new class of nonlinearly generated sequences containing several sets all equivalent to the ‘small set of Kasami sequences’, having optimal CCF and ACF properties, is introduced. The new class of sequences is obtained by interleavingm-sequences with the interleaving order governed by a set of sequences called the prime sequences introduced by Shaar and Davies. The construction procedure and the study of the CCF and ACF properties is presented in detail using the integer representation introduced by the present authors in an earlier paper.