Search: a013998 -id:a013998
|
| |
|
|
A001608
|
|
Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3) with a(0) = 3, a(1) = 0, a(2) = 2.
(Formerly M0429 N0163)
|
|
+10
73
|
|
|
|
3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853, 1130, 1497, 1983, 2627, 3480, 4610, 6107, 8090, 10717, 14197, 18807, 24914, 33004, 43721, 57918, 76725, 101639, 134643, 178364, 236282, 313007
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
Has been called the skiponacci sequence or skiponacci numbers. - N. J. A. Sloane, May 24 2013
For n >= 3, also the numbers of maximal independent vertex sets, maximal matchings, minimal edge covers, and minimal vertex covers in the n-cycle graph C_n. - Eric W. Weisstein, Mar 30 2017 and Aug 03 2017
With the terms indexed as shown, has property that p prime => p divides a(p). The smallest composite n such that n divides a(n) is 521^2. For quotients a(p)/p, where p is prime, see A014981.
Asymptotically, a(n) ~ r^n, with r=1.3247179572447... the inverse of the real root of 1-x^2-x^3=0 (see A060006). If n>9 then a(n)=round(r^n). - Ralf Stephan, Dec 13 2002
The recursion can be used to compute a(-n). The result is -A078712(n). - T. D. Noe, Oct 10 2006
For n>=3, a(n) is the number of maximal independent sets in a cycle of order n. - Vincent Vatter, Oct 24 2006
Let r1, r2 and r3 denote the roots of x^3 - x - 1. Then the following identity holds: a(k*n) + (a(k))^n - (a(k) - r1^k)^n - (a(k) - r2^k)^n - (a(k) - r3^k)^n
= 0 for n = 0, 1, 2,
= 6 for n = 3,
= 12*a(k) for n = 4,
= 10*[2*(a(k))^2 - a(-k)] for n = 5,
= 30*a(k)*[(a(k))^2 - a(-k)] for n = 6,
= 7*[6*(a(k))^4 - 9*a(-k)*(a(k))^2 + 2*(a(-k))^2 - a(k)] for n = 7,
= 56*a(k)*[((a(k))^2 - a(-k))^2 - a(k)/2] for n = 8,
where a(-k) = -A078712(k) and the formula (5.40) from the paper of Witula and Slota is used. (End)
The parity sequence of a(n) is periodic with period 7 and has the form (1,0,0,1,0,1,1). Hence we get that a(n) and a(2*n) are congruent modulo 2. Similarly we deduce that a(n) and a(3*n) are congruent modulo 3. Is it true that a(n) and a(p*n) are congruent modulo p for every prime p? - Roman Witula, Feb 09 2013
The trinomial x^3 - x - 1 divides the polynomial x^(3*n) - a(n)*x^(2*n) + ((a(n)^2 - a(2*n))/2)*x^n - 1 for every n>=1. For example, for n=3 we obtain the factorization x^9 - 3*x^6 + 2*x^3 - 1 = (x^3 - x - 1)*(x^6 + x^4 - 2*x^3 + x^2 - x + 1). Sketch of the proof: Let p,s,t be roots of the Perrin polynomial x^3 - x - 1. Then we have (a(n))^2 = (p^n + s^n + t^n)^2 = a(2*n) + 2*a(n)*x^n -2*x^n + 2/x^n for every x = p,s,t, i.e., x^(3*n) - a(n)*x^(2*n) + ((a(n)^2 - a(2*n))/2)*x^n - 1 = 0 for every x = p,s,t, which finishes the proof. By discussion of the power(a(n))^3 = (p^n + s^n + t^n)^3 it can be deduced that the trinomial x^3 - x - 1 divides the polynomial 2*x^(4*n) - a(n)*x^(3*n) - a(2*n)*x^(2*n) + ((a(n)^3 - a(3*n) - 3)/3)*x^n - a(n) = 0. Co-author of these divisibility relations is also my young student Szymon Gorczyca (13 years old as of 2013). - Roman Witula, Feb 09 2013
The sum of powers of the real root and complex roots of x^3-x-1=0 as expressed as powers of the plastic number r, (see A060006). Let r0=1, r1=r, r2=1+r^(-1) and c0=2, c1=-r and c3 = r^(-5) then a(n) = r(n-2)+r(n-3) + c(n-2)+c(n-3). Example: a(5) = 1 + r^(-1) + 1 + r + 2 - r + r^(-5) = 4 + r^(-1) + r^(-5) = 5. - Richard Turk, Jul 14 2016
Also the number of minimal total dominating sets in the n-sun graph. - Eric W. Weisstein, Apr 27 2018
Named after the French engineer François Olivier Raoul Perrin (1841-1910). - Amiram Eldar, Jun 05 2021
|
|
|
REFERENCES
|
Olivier Bordellès, Thèmes d'Arithmétique, Ellipses, 2006, Exercice 4.11, p. 127.0
Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.2.
Dmitry Fomin, On the properties of a certain recursive sequence, Mathematics and Informatics Quarterly, Vol. 3 (1993), pp. 50-53.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 70.
Manfred Schroeder, Number Theory in Science and Communication, 3rd ed., Springer, 1997.
A. G. Shannon, P. G. Anderson and A. F. Horadam, Properties of Cordonnier, Perrin and Van der Laan numbers, International Journal of Mathematical Education in Science and Technology, Volume 37:7 (2006), 825-831. See Q_n.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
J. Chick, Problem 81G, Math. Gazette, Vol. 81, No. 491 (1997), p. 304.
E. B. Escott, Problem 151, Amer. Math. Monthly, Vol. 15, No. 11 (1908), p. 209.
Christian Holzbaur, Perrin pseudoprimes [Original link broke many years ago. This is a cached copy from the WayBack machine, dated Apr 24 2006]
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 90.
Mathilde Noual, Dynamics of Circuits and Intersecting Circuits, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444, DOI; also on arXiv, arXiv 1011.3930 [cs.DM], 2010.
R. Perrin, Query 1484, L'Intermédiaire des Mathématiciens, Vol. 6 (1899), p. 76.
Razvan Tudoran, Problem 653, College Math. J., Vol. 31, No. 3 (2000), pp. 223-224.
Eric Weisstein's World of Mathematics, Sun Graph
|
|
|
FORMULA
|
G.f.: (3 - x^2)/(1 - x^2 - x^3). - Simon Plouffe in his 1992 dissertation
a(n) = r1^n + r2^n + r3^n where r1, r2, r3 are three roots of x^3-x-1=0.
a(n-1) + a(n) + a(n+1) = a(n+4), a(n) - a(n-1) = a(n-5). - Jon Perry, Jun 05 2003
a(n) = trace(M^n) where M is the 3 X 3 matrix [0 1 0 / 0 0 1 / 1 1 0], the companion matrix of the characteristic polynomial of this sequence, P = X^3 - X - 1.
M^n * [3, 0, 2] = [a(n), a(n+1), a(n+2)]; e.g., M^7 * [3, 0, 2] = [7, 10, 12].
a(0) + a(1) + a(2) + ... + a(n) = a(n+5) - 2.
a(0) + a(2) + a(4) + ... + a(2*n) = a(2*n+3).
a(1) + a(3) + a(5) + ... + a(2*n+1) = a(2*n+4) - 2. (End)
a(0) + a(3) + a(6) + a(9) + ... + a(3*n) = a(3*n+2) + 1.
a(0) + a(5) + a(10) + a(15) + ... + a(5*n) = a(5*n+1)+3.
a(0) + a(7) + a(14) + a(21) + ... + a(7*n) = (a(7*n) + a(7*n+1) + 3)/2. (End)
a(n) = n*Sum_{k=1..floor(n/2)} binomial(k,n-2*k)/k, n > 0, a(0)=3. - Vladimir Kruchinin, Oct 21 2011
(a(n)^3)/2 + a(3n) - 3*a(n)*a(2n)/2 - 3 = 0. - Richard Turk, Apr 26 2017
2*a(4n) - 2*a(n) - 2*a(n)*a(3n) - a(2n)^2 + a(n)^2*a(2n) = 0. - Richard Turk, May 02 2017
a(n)^4 + 6*a(4n) - 4*a(3n)*a(n) - 3*a(2n)^2 - 12a(n) = 0. - Richard Turk, May 02 2017
a(n+5)^2 + a(n+1)^2 - a(n)^2 = a(2*(n+5)) + a(2*(n+1)) - a(2*n). - Aleksander Bosek, Mar 04 2019
a(n+12) = a(n) + 2*a(n+4) + a(n+11);
a(n+16) = a(n) + 4*a(n+9) + a(n+13);
a(n+18) = a(n) + 2*a(n+6) + 5*a(n+12);
a(n+21) = a(n) + 2*a(n+12) + 6*a(n+14);
a(n+27) = a(n) + 3*a(n+9) + 4*a(n+22). (End)
a(n) = Sum_{j=0..floor((n-g)/(2*g))} 2*n/(n-2*(g-2)*j-(g-2)) * Hypergeometric2F1([-(n-2g*j-g)/2, -(2j+1)], [1], 1), g = 3 and n an odd integer. - Richard Turk, Oct 14 2019
|
|
|
EXAMPLE
|
We note that if a + b + c = 0 then:
1) a^3 + b^3 + c^3 = 3*a*b*c,
2) a^4 + b^4 + c^4 = 2*((a^2 + b^2 + c^2)/2)^2,
3) (a^5 + b^5 + c^5)/5 = (a^3 + b^3 + c^3)/3 * (a^2 +
b^2 + c^2)/2,
4) (a^7 + b^7 + c^7)/7 = (a^5 + b^5 + c^5)/5 * (a^2 + b^2 + c^2)/2 = 2*(a^3 + b^3 + c^3)/3 * (a^4 + b^4 + c^4)/4,
5) (a^7 + b^7 + c^7)/7 * (a^3 + b^3 + c^3)/3 = ((a^5 + b^5 + c^5)/5)^2.
Hence, by the Binet formula for a(n) we obtain the relations: a(3) = 3, a(4) = 2*(a(2)/2)^2 = 2, a(5)/5 = a(3)/3 * a(2)/2, i.e., a(5) = 5, and similarly that a(7) = 7. (End)
|
|
|
MAPLE
|
A001608 :=proc(n) option remember; if n=0 then 3 elif n=1 then 0 elif n=2 then 2 else procname(n-2)+procname(n-3); fi; end proc;
|
|
|
MATHEMATICA
|
LinearRecurrence[{0, 1, 1}, {3, 0, 2}, 50] (* Harvey P. Dale, Jun 26 2011 *)
per = Solve[x^3 - x - 1 == 0, x]; f[n_] := Floor @ Re[N[ per[[1, -1, -1]]^n + per[[2, -1, -1]]^n + per[[3, -1, -1]]^n]]; Array[f, 46, 0] (* Robert G. Wilson v, Jun 29 2010 *)
CoefficientList[Series[(3 - x^2)/(1 - x^2 - x^3), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 03 2015 *)
Table[RootSum[-1 - # + #^3 &, #^n &], {n, 0, 20}] (* Eric W. Weisstein, Mar 30 2017 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<0, 0, polsym(x^3-x-1, n)[n+1])
(Haskell)
a001608 n = a000931_list !! n
a001608_list = 3 : 0 : 2 : zipWith (+) a001608_list (tail a001608_list)
(Python)
A001608_list, a, b, c = [3, 0, 2], 3, 0, 2
for _ in range(100):
a, b, c = b, c, a+b
(GAP) a:=[3, 0, 2];; for n in [4..20] do a[n]:=a[n-2]+a[n-3]; od; a; # Muniru A Asiru, Jul 12 2018
(Magma) I:=[3, 0, 2]; [n le 3 select I[n] else Self(n-2) +Self(n-3): n in [1..50]]; // G. C. Greubel, Mar 18 2019
(Sage) ((3-x^2)/(1-x^2-x^3)).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, Mar 18 2019
|
|
|
CROSSREFS
|
Cf. A013998 (Unrestricted Perrin pseudoprimes).
Cf. A018187 (Restricted Perrin pseudoprimes).
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Additional comments from Mike Baker, Oct 11 2005
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A018187
|
|
Restricted Perrin pseudoprimes.
|
|
+10
8
|
|
|
|
27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
These are the "minimal restricted" Perrin pseudoprimes. They meet conditions (4) and (5) from Adams and Shanks (1982), equivalent to condition (7) from Kurtz et al. (1986). That is, A(n) = 0 mod p and A(-n) = -1 mod p. Kurtz et al. call this the "minimal test", Wagon (1999) calls this the "strong Perrin test".
Further restrictions (Adams and Shanks, Arno / Grantham) lead to subsets of this sequence.
Kurtz et al. (1986) state that all acceptables (numbers where A(n) = 0 mod p and A(-n) = -1 mod p) <= 50*10^9 have S-type signatures. The first example where this does not hold is 16043638781521, which does not have an S-signature (nor an I- or Q-type signature).
The first example of a pseudoprime in this sequence that does not pass the Adams/Shanks signature test is 167385219121, with an S-signature but the wrong Jacobi symbol.
Some sources have conjectured the restricted Perrin pseudoprimes can be derived from the unrestricted Perrin pseudoprimes by checking if { M=[0,1,0; 0,0,1; 1,1,0]; Mod(M,n) == Mod(M,n)^n }. Counterexamples include 52437986833, 60518537641, 364573433665, and 4094040693601. (End)
|
|
|
REFERENCES
|
S. Wagon, Mathematica in action, 2nd ed., 1999, pp. 402 - 403 and Mathematica notebook for Chapter 18 in attached CD-ROM
|
|
|
LINKS
|
|
|
|
PROG
|
(Perl) use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($_, 1); } 1e8; # Dana Jacobsen, Aug 03 2016
(PARI) is(n) = { lift(trace(Mod([0, 1, 0; 0, 0, 1; 1, 1, 0], n)^n)) == 0 && lift(trace(Mod([0, 1, 0; 0, 0, 1; 1, 0, -1], n)^n)) == n-1; }
forcomposite(n=1, 1e8, is(n)&&print(n)) \\ Dana Jacobsen, Aug 03 2016
|
|
|
CROSSREFS
|
Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A173656
|
|
Primes p such that p^2 divides P(p), where P = Perrin sequence A001608.
|
|
+10
4
|
| |
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
It is not known if this sequence is infinite.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
521 is in the sequence since its square 271441 is the factor of A001608(521).
|
|
|
MATHEMATICA
|
lst = {}; a = 3; b = 0; c = 2; Do[P = b + a; If[PrimeQ[n] && Divisible[P, n^2], AppendTo[lst, n]]; a = b; b = c; c = P, {n, 3, 2*10^5}]; lst
lst = {}; PowerMod2[mat_, n_, m_] := Mod[Fold[Mod[If[#2 == 1, #1.#1.mat, #1.#1], m] &, mat, Rest@IntegerDigits[n, 2]], m]; LinearRecurrence2[coeffs_, init_, n_, m_] := Mod[First@PowerMod2[Append[RotateRight /@ Most@IdentityMatrix@Length[coeffs], coeffs], n, m].init, m] /; n >= Length[coeffs]; Do[n = Power[p, 2]; If[PrimeQ[p] && LinearRecurrence2[{1, 1, 0}, {3, 0, 2}, n, n] == 0, AppendTo[lst, p]], {p, 1, 2*10^5, 2}]; lst
|
|
|
PROG
|
(PARI)
/* Assuming b13998 containing second column of b013998.txt */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
bref,hard,more,nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
0, 0, 0, 2, 0, 5, 0, 2, 3, 7, 0, 5, 0, 9, 8, 10, 0, 14, 0, 17, 10, 2, 0, 13, 5, 15, 12, 23, 0, 20, 0, 26, 25, 19, 12, 2, 0, 21, 3, 5, 0, 33, 0, 2, 32, 2, 0, 21, 7, 42, 20, 41, 0, 23, 27, 3, 41, 2, 0, 34, 0, 33, 61, 26, 44, 27, 0, 53, 26, 31, 0, 34, 0, 2, 68, 21, 29, 18, 0, 5, 39, 43, 0, 71, 39, 2, 3, 10, 0, 83, 46, 2, 65, 49
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
a(n) = 0 for n=1, n a prime, or n a Perrin pseudoprime (A013998).
|
|
|
LINKS
|
|
|
|
PROG
|
(PARI)
M = [0, 1, 0; 0, 0, 1; 1, 1, 0];
a(n)=lift( trace( Mod(M, n)^n ) );
vector(66, n, a(n))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A075764
|
|
Schroeder pseudoprimes: Composites k that divide the k-th Schroeder number A001003(k-1).
|
|
+10
2
|
|
|
|
105, 261, 301, 693, 1605, 1755, 2151, 2905, 2907, 3393, 3875, 4641, 4833, 5005, 5655, 6279, 6913, 7161, 8883, 9405, 10899, 11025, 11289, 15687, 17199, 19203, 22275, 27387, 36855, 37791, 50007, 50463, 53493, 54891, 55209, 55755, 63327, 64337
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
105 is a term because A001003(105) = 15646506064359350392347086201481965698808674470977505246623827696393838448345 which is divisible by 105.
105 is a term because A001003(104) = 15646506064359350392347086201481965698808674470977505246623827696393838448345 which is divisible by 105.
|
|
|
MATHEMATICA
|
s = {}; k1 = k2 = 1; Do[k3 = ((6*n - 9)*k2 - (n - 3)*k1)/n; If[CompositeQ[n] && Divisible[k3, n], AppendTo[s, n]]; k1 = k2; k2 = k3, {n, 3, 10^5}]; s (* Amiram Eldar, Jun 28 2022 *)
|
|
|
PROG
|
(PARI) x1 = 1; x2 = 1; for (n = 3, 100000, x = (3*(2*n - 3)*x1 - (n - 3)*x2)/n; if (!isprime(n), if (!(x%n), print(n))); x2 = x1; x1 = x); \\ David Wasserman, Feb 23 2005
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A174625
|
|
Table T(n,k) with the coefficients of the polynomial P_n(x) = P_{n-1}(x) + x*P_{n-2}(x) + 1 in row n, by decreasing exponent of x.
|
|
+10
2
|
|
|
|
0, 2, 3, 2, 4, 5, 5, 2, 9, 6, 7, 14, 7, 2, 16, 20, 8, 9, 30, 27, 9, 2, 25, 50, 35, 10, 11, 55, 77, 44, 11, 2, 36, 105, 112, 54, 12, 13, 91, 182, 156, 65, 13, 2, 49, 196, 294, 210, 77, 14, 15, 140, 378, 450, 275, 90, 15, 2, 64, 336, 672, 660, 352, 104, 16, 17, 204, 714, 1122, 935, 442
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The polynomials are defined by the recurrence starting with P_1(x)=0, P_2(x)=2.
The degree of the polynomial (row length minus 1) is A004526(n-2).
All coefficients of P_n are multiples of n iff n is prime.
Apparently a mirrored version of A157000. [R. J. Mathar, Nov 01 2010]
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The table starts
0; # 0
2; # 2
3; # 3
2,4; # 4+2*x
5,5; # 5+5*x
2,9,6; # 6+9*x+2*x^2
7,14,7; # 7+14*x+7*x^2
2,16,20,8; # 8+20*x+16*x^2+2*x^3
9,30,27,9; # 9+27*x+30*x^2+9*x^3
2,25,50,35,10; # 10+35*x+50*x^2+25*x^3+2*x^4
11,55,77,44,11; # 11+44*x+77*x^2+55*x^3+11*x^4
|
|
|
MATHEMATICA
|
p[0]:=0 p[1]:=2; p[n_]:=p[n]=Expand[p[n-1] +x p[n-2]+1]; Flatten[{0, Map[Reverse[CoefficientList[#, x]]&, Table[Expand[p[n]], {n, 0, 20}]]}] (* Peter J. C. Moses, Aug 18 2013 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,tabf
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Definition rephrased, sequence extended, keyword:tabf, examples added R. J. Mathar, Nov 01 2010
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
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).
|
|
+10
2
|
| |
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
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
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
A225984(4) = 11, and 11 == 3 (mod 4). Since 4 is composite, it is a pseudoprime with respect to A225984.
|
|
|
PROG
|
(PARI)
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, ", "); );
); }
|
|
|
KEYWORD
|
nonn,hard,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Terms 4 through 7 found by Richard Holmes, added by Matt McIrvin, May 27 2013
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A275612
|
|
Restricted Perrin pseudoprimes (Adams and Shanks definition)
|
|
+10
2
|
|
|
|
27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121, 7279379941, 7825642579
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
These are composites which have an acceptable signature mod n for the Perrin sequence (A001608). See Adams and Shanks (1982), page 261.
They add additional conditions to the unrestricted Perrin test (A013998) and the minimal restricted test (A018187).
The quadratic form restriction for the I-signature (equation 29 in Adams and Shanks (1982)) is sometimes removed. No pseudoprimes are currently known that match the I-signature congruences. Adams and Shanks note that objections could be raised to its inclusion in the test, and Arno (1991) and Grantham (2000) both drop it.
Kurtz et al. (1986) call these "acceptable composites for the Perrin sequence". - N. J. A. Sloane, Jul 28 2019
|
|
|
LINKS
|
|
|
|
PROG
|
(Perl) use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($_, 2); } 1e8; # Dana Jacobsen, Aug 03 2016
(PARI) perrin2(n) = {
my(M, L, S, j, A, B, C, D);
M=Mod( [0, 1, 0; 0, 0, 1; 1, 1, 0], n)^n;
L=Mod( [0, 1, 0; 0, 0, 1; 1, 0, -1], n)^n;
S=[ 3*L[3, 2]-L[3, 3], 3*L[2, 2]-L[2, 3], 3*L[1, 2]-L[1, 3], \
3*M[3, 1]+2*M[3, 3], 3*M[1, 1]+2*M[1, 3], 3*M[2, 1]+2*M[2, 3] ];
if (S[5] != 0 || S[2] != n-1, return(0));
j = kronecker(-23, n);
if (j == -1, B=S[3]; A=1+3*B-B^2; C=3*B^2-2; if(S[1]==A && S[3]==B && S[4]==B && S[6] == C && B != 3 && B^3-B==1, return(1), return(0)));
if (S[1] == 1 && S[3] == 3 && S[4] == 3 && S[6] == 2, return(1));
if (j == 1 && S[1] == 0 && S[6] == n-1 && S[3] != S[4] && S[3]+S[4] == n-3 && (S[3]-S[4])^2 == Mod(-23, n), return(1));
return(0);
|
|
|
CROSSREFS
|
Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes), A018187 (minimal restricted Perrin pseudoprimes)
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A078512
|
|
Carmichael numbers that are unrestricted Perrin pseudoprimes.
|
|
+10
1
|
|
|
|
7045248121, 7279379941, 24306384961, 43234580143, 52437986833, 60518537641, 80829302401, 118805562613, 144377609419, 165321688501, 167385219121, 254302215553, 364573433665, 575687567521, 588909469501, 652270080001, 2152302898747, 4094040693601, 6287912246305
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
|
|
|
LINKS
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A178375
|
|
The greatest common prime divisor of A000032(n)-1 and A001608(n), or 1 if no such divisor exists.
|
|
+10
1
|
|
|
|
2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1, 2, 17, 1, 19, 1, 1, 2, 23, 1, 5, 1, 3, 1, 29, 1, 31, 2, 7, 1, 3, 1, 37, 1, 7, 1, 41, 1, 43, 2, 1, 2, 47, 1, 7, 2, 1, 3, 53, 1, 7, 1, 1, 2, 59, 1, 61, 1, 1, 2, 7, 1, 67, 3, 1, 1, 71, 1, 73, 2, 1, 1, 5, 1, 79, 1, 7, 1, 83, 1, 2, 2, 7, 2, 89, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,1
|
|
|
COMMENTS
|
If n is prime, then n divides c(n). If n is composite and divides c(n) it is a pseudoprime to both the Lucas (Bruckman) and Perrin tests, which is the intersection of A005845 and A013998.
Conjecture: Records of the sequence are consecutive primes.
|
|
|
LINKS
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.015 seconds
|
