[math-fun] Odd behavior in a sequence
I'm looking at the linear recurrence 0, 1, 3, 11, 39, 139, . with a(n) = 3a(n-1) + 2a(n-2) for n >= 2. I was interested in the question, for which primes p do {a(n)} == Z (mod p)? That is, for which primes p do all residues r appear in {a(n)} (mod p) (Forgive my notational abuse)? We'll shorten that to "a covers p". I expected this to have a simple answer, and it almost does. It turns out that whether or not a covers p most of the time depends on p mod 17. In general, a covers p if p == 0, 3, 5, 6, 7, 10, 11, 12, or 14 (mod 7). However, there seem to be a smattering of primes p: 683, 1217, 2731, 11299, 48817, . which, according to their residue mod 17, should be covered by a, but are not. Very curious.
Read " In general, a covers p if p == 0, 3, 5, 6, 7, 10, 11, 12, or 14 (mod 17). " Note that X^2 - 3*X - 2 has discriminant 17 ; it's not immediately obvious to me why this should be relevant, but general principles suggest a probable connection. NJAS ? WFL On 10/21/15, David Wilson <davidwwilson@comcast.net> wrote:
I'm looking at the linear recurrence
0, 1, 3, 11, 39, 139, .
with a(n) = 3a(n-1) + 2a(n-2) for n >= 2.
I was interested in the question, for which primes p do {a(n)} == Z (mod p)?
That is, for which primes p do all residues r appear in {a(n)} (mod p) (Forgive my notational abuse)?
We'll shorten that to "a covers p".
I expected this to have a simple answer, and it almost does.
It turns out that whether or not a covers p most of the time depends on p mod 17.
In general, a covers p if p == 0, 3, 5, 6, 7, 10, 11, 12, or 14 (mod 7).
However, there seem to be a smattering of primes p:
683, 1217, 2731, 11299, 48817, .
which, according to their residue mod 17, should be covered by a, but are not.
Very curious.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A smattering of numerology ... Except for 0, the list of residues mod 17 is the non-squares. For mod 17, this is equivalent to being a primitive root. In the exception list further down, two of the primes have a recognizable property: 683 = (2^11+1)/3, and 2731 = (2^13+1)/3. I don't see anything special about the other three. 43691 = (2^17+1)/3 is absent, but it's 1 mod17, hence excused. Rich ---------- Quoting Fred Lunnon <fred.lunnon@gmail.com>:
Read " In general, a covers p if p == 0, 3, 5, 6, 7, 10, 11, 12, or 14 (mod 17). "
Note that X^2 - 3*X - 2 has discriminant 17 ; it's not immediately obvious to me why this should be relevant, but general principles suggest a probable connection. NJAS ?
WFL
On 10/21/15, David Wilson <davidwwilson@comcast.net> wrote:
I'm looking at the linear recurrence
0, 1, 3, 11, 39, 139, .
with a(n) = 3a(n-1) + 2a(n-2) for n >= 2.
I was interested in the question, for which primes p do {a(n)} == Z (mod p)?
That is, for which primes p do all residues r appear in {a(n)} (mod p) (Forgive my notational abuse)?
We'll shorten that to "a covers p".
I expected this to have a simple answer, and it almost does.
It turns out that whether or not a covers p most of the time depends on p mod 17.
In general, a covers p if p == 0, 3, 5, 6, 7, 10, 11, 12, or 14 (mod 7).
However, there seem to be a smattering of primes p:
683, 1217, 2731, 11299, 48817, .
which, according to their residue mod 17, should be covered by a, but are not.
Very curious.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The solution of the recurrence with initial conditions a(0)=0, a(1)=1 is a(n) = (s^n - t^n)/sqrt(17) where s = (3+sqrt(17))/2 and t = (3-sqrt(17))/2 = -2/s. This works in any field (not of characteristic 2 or 17) where 17 has a square root. Thus if p is an odd prime and 17 is a quadratic residue mod p, say 17 == b^2 mod p, we have a(n) == (s^n - t^n)/b mod p where s == (3+b)/2 and t == -2/s. Now by Fermat's little theorem, a(n) is periodic in n with period at most p-1, so in this case it's impossible to cover all the residues. On the other hand, if 17 is not a quadratic residue mod p, you go to an extension field, and it's possible that all residues will be covered. However, this is not guaranteed. Thus for p = 683, s and t have order 396, so at most 396 of the residues are covered (in fact only 177 are). Note, by the way, that by quadratic reciprocity 17 is a quadratic residue mod the odd prime p iff p is a quadratic residue mod 17, i.e. p == 1, 2, 4, 8, 9, 13, 15, or 16 mod 17. Cheers, Robert On Oct 20 2015, David Wilson wrote:
I'm looking at the linear recurrence
0, 1, 3, 11, 39, 139, .
with a(n) = 3a(n-1) + 2a(n-2) for n >= 2.
I was interested in the question, for which primes p do {a(n)} == Z (mod p)?
That is, for which primes p do all residues r appear in {a(n)} (mod p) (Forgive my notational abuse)?
We'll shorten that to "a covers p".
I expected this to have a simple answer, and it almost does.
It turns out that whether or not a covers p most of the time depends on p mod 17.
In general, a covers p if p == 0, 3, 5, 6, 7, 10, 11, 12, or 14 (mod 7).
However, there seem to be a smattering of primes p:
683, 1217, 2731, 11299, 48817, .
which, according to their residue mod 17, should be covered by a, but are not.
Very curious.
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
participants (4)
-
David Wilson -
Fred Lunnon -
israel@math.ubc.ca -
rcs@xmission.com