

A225984


Linear recurrence sequence with infrequent pseudoprimes, a(n) = a(n1) + a(n2)  a(n3) + a(n5), with initial terms (5, 1, 3, 7, 11).


3



5, 1, 3, 7, 11, 16, 33, 57, 99, 178, 318, 562, 1001, 1782, 3167, 5632, 10019, 17817, 31686, 56355, 100226, 178248, 317012, 563800, 1002705, 1783291, 3171548, 5640532, 10031571, 17840946, 31729758, 56430727, 100360899, 178489813, 317440493
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

For all prime p, a(p) mod p = p1. The first composite p satisfying the relation is 4 (from the seed value a(4) = 11), but the second one is 14791044.
Found via automated search for linear recurrence sequences of the form a(n) = trace(M^n) generating more infrequent pseudoprimes than the Perrin numbers, A001608.
This sequence, like the Lucas and Perrin numbers, has a Binetlike formula with coefficient 1 for powers of all complex roots of the characteristic equation det(M  bI) = 0. All recurrence sequences of the form a(n) = trace(M^n) seem to have a Binetlike formula of this type. Sequences with such a formula all generate a probableprime test: a(p) is congruent to a(1) mod p for prime p. A composite number satisfying the test is a pseudoprime for the sequence.
For coefficients in {1, 0, 1}, this sequence has the highest first pseudoprime after the seed indices for all linear recurrences of this type over the previous 7 terms.


LINKS

Seiichi Manyama, Table of n, a(n) for n = 0..3996 (terms 0..500 from T. D. Noe)
M. McIrvin, post on Google+
M. McIrvin, Some Sage code about Fibonaccilike sequences and primality tests
K. Brown, Proof of Generalized Little Theorem of Fermat, proves the probableprime test for sequences with Binetlike formulas of the form a(n) = sum(b_k^n), where b_k are the complex roots of the characteristic equation.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,0,1).


FORMULA

G.f.: (2*x^3+3*x^24*x5)/(x^5x^3+x^2x1).  Peter Luschny, May 22 2013
Binetlike formula: a(n) = sum(b_k^n), where b_k are the complex roots of the characteristic equation x^5 + x^4  x^3 + x^2  1 = 0.  Matt McIrvin, May 24 2013


EXAMPLE

a(5) = 11 + (7)  3 + 5 = 16.


MAPLE

f := x > (2*x^3+3*x^24*x5)/(x^5x^3+x^2x1);
seq(coeff(series(f(x), x, n+2), x, n), n=0..34); # Peter Luschny, May 22 2013


MATHEMATICA

LinearRecurrence[{1, 1, 1, 0, 1}, {5, 1, 3, 7, 11}, 40] (* T. D. Noe, May 22 2013 *)


PROG

(Sage)
def LinearRecurrence5(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9):
x, y, z, u, v = a0, a1, a2, a3, a4
while true:
yield x
x, y, z, u, v = y, z, u, v, a9*x+a8*y+a7*z+a6*u+a5*v
a = LinearRecurrence5(5, 1, 3, 7, 11, 1, 1, 1, 0, 1)
[a.next() for i in range(34)] # Peter Luschny, May 22 2013
(MAGMA) I:=[5, 1, 3, 7, 11]; [n le 5 select I[n] else Self(n5)Self(n3)+Self(n2)Self(n1): n in [1..40]]; // Bruno Berselli, May 22 2013


CROSSREFS

Cf. A225876 (pseudoprimes for this sequence), A290139.
Sequence in context: A051996 A242303 A214803 * A074048 A244350 A176321
Adjacent sequences: A225981 A225982 A225983 * A225985 A225986 A225987


KEYWORD

sign,easy


AUTHOR

Matt McIrvin, May 22 2013


STATUS

approved



