A225984 - OEIS

%I #44 Sep 08 2022 08:46:05

%S 5,-1,3,-7,11,-16,33,-57,99,-178,318,-562,1001,-1782,3167,-5632,10019,

%T -17817,31686,-56355,100226,-178248,317012,-563800,1002705,-1783291,

%U 3171548,-5640532,10031571,-17840946,31729758,-56430727,100360899,-178489813,317440493

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

%C 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.

%C 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.

%C 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.

%C 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.

%H Seiichi Manyama, <a href="/A225984/b225984.txt">Table of n, a(n) for n = 0..3996</a> (terms 0..500 from T. D. Noe)

%H M. McIrvin, <a href="https://plus.google.com/u/0/100452847199780289157/posts/K7NSbA3LjA1">post on Google+</a>

%H M. McIrvin, <a href="http://mmcirvin.livejournal.com/488038.html">Some Sage code about Fibonacci-like sequences and primality tests</a>

%H K. Brown, <a href="http://www.mathpages.com/home/kmath346/kmath346.htm">Proof of Generalized Little Theorem of Fermat</a>, 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.

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (-1,1,-1,0,1).

%F G.f.: (-2*x^3+3*x^2-4*x-5)/(x^5-x^3+x^2-x-1). - _Peter Luschny_, May 22 2013

%F 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

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

%p f := x -> (-2*x^3+3*x^2-4*x-5)/(x^5-x^3+x^2-x-1);

%p seq(coeff(series(f(x),x,n+2),x,n), n=0..34);  # _Peter Luschny_, May 22 2013

%t LinearRecurrence[{-1, 1, -1, 0, 1}, {5, -1, 3, -7, 11}, 40] (* _T. D. Noe_, May 22 2013 *)

%o (Sage)

%o def LinearRecurrence5(a0,a1,a2,a3,a4,a5,a6,a7,a8,a9):

%o     x, y, z, u, v = a0, a1, a2, a3, a4

%o     while True:

%o         yield x

%o         x, y, z, u, v = y, z, u, v, a9*x+a8*y+a7*z+a6*u+a5*v

%o a = LinearRecurrence5(5,-1,3,-7,11,-1,1,-1,0,1)

%o [next(a) for i in range(34)]  # _Peter Luschny_, May 22 2013

%o (Magma) 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

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

%K sign,easy

%O 0,1

%A _Matt McIrvin_, May 22 2013