A225876 -id:A225876 - cp's OEIS frontend

A225984 Linear recurrence sequence with infrequent pseudoprimes, a(n) = -a(n-1) + a(n-2) - a(n-3) + a(n-5), with initial terms (5, -1, 3, -7, 11).

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

Offset: 0

Matt McIrvin, May 22 2013

For all prime p, a(p) mod p = p-1. 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 Binet-like 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 Binet-like formula of this type. Sequences with such a formula all generate a probable-prime 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.

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

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 Fibonacci-like sequences and primality tests
K. Brown, Proof of Generalized Little Theorem of Fermat, proves the probable-prime test for sequences with Binet-like 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).

Cf. A225876 (pseudoprimes for this sequence), A290139.

I:=[5,-1,3,-7,11]; [n le 5 select I[n] else Self(n-5)-Self(n-3)+Self(n-2)-Self(n-1): n in [1..40]]; // Bruno Berselli, May 22 2013

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

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

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)
[next(a) for i in range(34)]  # Peter Luschny, May 22 2013

G.f.: (-2*x^3+3*x^2-4*x-5)/(x^5-x^3+x^2-x-1). - Peter Luschny, May 22 2013

Binet-like 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

A290139 a(n) = A225984(n) mod n.

Original entry on oeis.org

0, 1, 2, 3, 4, 3, 6, 3, 2, 8, 10, 5, 12, 3, 8, 3, 16, 6, 18, 6, 0, 14, 22, 9, 9, 16, 11, 11, 28, 18, 30, 3, 26, 3, 33, 2, 36, 3, 6, 34, 40, 26, 42, 0, 2, 26, 46, 17, 41, 43, 27, 24, 52, 42, 28, 43, 12, 32, 58, 26, 60, 3, 60, 3, 23, 11, 66, 45, 62, 17, 70, 42, 72, 3

Offset: 1

Seiichi Manyama, Jul 21 2017

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000040, A225876, A225984.

MapIndexed[Mod[#1, First@ #2] &, LinearRecurrence[{-1, 1, -1, 0, 1}, {-1, 3, -7, 11, -16}, 74]] (* Michael De Vlieger, Jul 21 2017, after T. D. Noe at A225984 *)

a(p) = p - 1 for all prime p.

cp's OEIS Frontend

A225984 Linear recurrence sequence with infrequent pseudoprimes, a(n) = -a(n-1) + a(n-2) - a(n-3) + a(n-5), with initial terms (5, -1, 3, -7, 11).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula