0, 1, 3, 11, 39, 139, 495, 1763, 6279, 22363, 79647, 283667, 1010295, 3598219, 12815247, 45642179, 162557031, 578955451, 2061980415, 7343852147, 26155517271, 93154256107, 331773802863, 1181629920803, 4208437368135, 14988571946011,...

with a(n) = 3a(n-1) + 2a(n-2) for n >= 2. for which primes p do all residues r appear in {a(n)} (mod p) We'll shorten that to "a covers p".

Formula: a(n) = ( [(3+sqrt(17))/2]^n - [(3-sqrt(17))/2]^n ) / sqrt(17) now, take a(n) mod p with p prime. Using quadratic reciprocity we see 17 is a square mod p if and only if p is a square mod 17: 0, 1, 4, 9, 16, 8, 2, 15, 13. (i) If so, then a(n) can be evaluated mod p using the above formula using plain old mod p arithmetic. Then by Fermat little theorem, a(n) mod p has period=p-1 (or a divisor of p-1), and hence cannot cover. (ii) If not (p mod 17=3,5,6,7,10,11,12,14) then we need to go to an extension field to do the arithmetic. In that case the period should be p^2-1=(p-1)(p+1) or a divisor. Empirically according to Wilson, case (ii) usually yields coverage mod p, but not always (exceptions p=683, 1217, 2731, 11299, 48817) while case (i) never yields coverage. Example of case (i) is p=19, a(n) = 0, 1, 3, 11, 1, 6, 1, 15, 9, 0, 18, 16, 8, 18, 13, 18, 4, 10, 0, ... with period=18 and not covering since missing 2,5,etc. Example of case (ii) is p=5 with a(n) = 0, 1, 3, 1, 4, 4, 0, 3, 4, 3, 2, 2, 0, 4, 2, 4, 1, 1, 0, 2, 1, 2, 3, 3, 0, ... with period=24 and covering. Obviously in cases with period >> p, it is highly likely that coverage will happen, but not logically forced. Further, period=(p-1)(p+1)/k will be unlikely to happen for large divisors k, and more likely to happen for small k, so coverage is always going to be likely, but not logically forced. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)