Matt McIrvin - cp's OEIS frontend

User: Matt McIrvin

Matt McIrvin has authored 2 sequences.

A225876 Composite n which divide s(n)+1, where s is the linear recurrence sequence s(n) = -s(n-1) + s(n-2) - s(n-3) + s(n-5) with initial terms (5, -1, 3, -7, 11).

4, 14791044, 143014853, 253149265, 490434564, 600606332, 993861182, 3279563483

Offset: 1

Matt McIrvin, May 23 2013

The pseudoprimes derived from the fifth-order linear recurrence A225984(n) are analogous to the Perrin pseudoprimes A013998, and the Lucas pseudoprimes A005845.
For prime p, A225984(p) == p - 1 (mod p). The pseudoprimes are composite numbers satisfying the same relation. 4 = 2^2; 14791044 = 2^2 * 3 * 19 * 29 * 2237; 143014853 = 907 * 157679.
Like the Perrin test, the modular sequence is periodic so simple pre-tests can be performed.  Numbers divisible by 2, 3, 4, 5, 9, and 25 have periods 31, 11, 62, 24, 33, and 120 respectively. - Dana Jacobsen, Aug 29 2016
a(9) > 1.4*10^11. - Dana Jacobsen, Aug 29 2016

			A225984(4) = 11, and 11 == 3 (mod 4). Since 4 is composite, it is a pseudoprime with respect to A225984.

K. Brown, Proof of Generalized Little Theorem of Fermat, proves that for prime p, a(p) == a(1) (mod p) for recurrences of the form of A225984.
R. Holmes, comments to M. McIrvin's post on Google+ (found terms 4 through 7)

N=10^10;
default(primelimit, N);
M = [0, 1, 0, 0, 0; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0, 1; 1, 0, -1, 1, -1];
a(n)=lift( trace( Mod(M, n)^n ) );
ta(n)=lift( trace( Mod(M, n) ) );
{ for (n=2, N,
    if ( isprime(n), next() );
    if ( a(n)==ta(n), print1(n, ", "); );
); }
/* Matt McIrvin, after Joerg Arndt's program for A013998, May 23 2013 */

Terms 4 through 7 found by Richard Holmes, added by Matt McIrvin, May 27 2013

a(8) from Dana Jacobsen, Aug 29 2016

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).

Original entry on oeis.org

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

cp's OEIS Frontend

User: Matt McIrvin

A225876 Composite n which divide s(n)+1, where s is the linear recurrence sequence s(n) = -s(n-1) + s(n-2) - s(n-3) + s(n-5) with initial terms (5, -1, 3, -7, 11).

Views

Author

Keywords

Comments

Examples

Links

Programs

PARI

Extensions

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