In 1876 Lucas devised a test for the primality of Mersenne numbers M_n, where n ≡ 3 (mod 4). He did so by calculating a recursive sequence s_k with s_k+1 = s_k² – 2, using an initial value of s₁ = 3. Later, Lehmer refined Lucas' techniques and constructed a test for all Mersenne numbers with odd n (n ≥ 3); again he used the sequence s_k, but with an initial value of 4. We investigate what initial values can be used in similar primality tests and for which values of n they can be used to test M_n. We also present some computational results.