Critical data length for period estimation

We address the following question in this paper: Given that the period of a discrete time periodic signal belongs to a set P = {P_1, P_2,…,P_K}, what is the minimum duration of the signal necessary to identify its period? It will be shown that the following number of samples is both necessary and sufficient: max P_i + P_j - gcd(P_i, P_j), where gcd is the greatest common divisor, and the maximization is over all pairs P_i, P_j ∈ P. Sufficiency is shown via a constructive proof, leading to a new period estimation algorithm