A013998 -id:A013998 - cp's OEIS frontend

A275613 Restricted Perrin pseudoprimes (Grantham definition).

27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121, 7279379941, 7825642579

Offset: 1

Dana Jacobsen, Aug 03 2016

nonn

These are odd composites which have an acceptable signature mod n for the Perrin sequence (A001608), using the definition given by Arno (1991).  Grantham (2000) gives a generalized definition for cubics, with the Perrin sequence being the parameters r=0, s=-1.
This is similar to the Adams and Shanks (1982) test, with three exceptions:  (1) pseudoprimes must be odd composites, (2) S-signatures with (-23|n) = 0 are not allowed, and (3) the quadratic form test for I-signatures is removed.
Below 5*10^13, there are no even pseudoprimes to the minimal restricted test (A018187), hence the first difference is not seen.  Also below 5*10^13, there are no pseudoprimes with an I-signature congruence, so the third difference is also not seen.  There are pseudoprimes divisible by 23 to the Adams/Shanks signature test (A275612), which are not pseudoprimes to this test.

Dana Jacobsen, Table of n, a(n) for n = 1..701
W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300.
Steven Arno, A note on Perrin pseudoprimes, Math. Comp. 56 (1991), 371-376.
Jon Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), 873-891.
Jon Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010) 1117-1128.
Dana Jacobsen, Perrin Primality Tests.
G. C. Kurtz, Daniel Shanks, and H. C. Williams, Fast Primality Tests for Numbers < 50*10^9, Math. Comp., 46 (1986), 691-701.

Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes), A018187 (minimal restricted Perrin pseudoprimes), A275612 (Adams/Shanks restricted Perrin pseudoprimes).

perrin3(n) = {
  my(M,L,S,j,A,B,C,D);
  if(n==2||n==23,return(1));
  if(n%2==0,return(0));
  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 == 0,return(0));
  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 (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);
}

use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($,3); } 1e8; # _Dana Jacobsen, Aug 03 2016

A294028 Composite numbers k such that k | 1 - A078712(k).

Original entry on oeis.org

49, 77, 121, 203, 319, 413, 679, 721, 749, 841, 869, 1057, 1211, 1351, 1393, 1397, 1441, 1639, 1687, 1757, 1769, 1883, 2167, 2189, 2219, 2359, 2429, 2581, 2651, 2761, 2959, 3031, 3073, 3101, 3227, 3409, 3437, 3485, 3487, 3563, 3899, 4037, 4039, 4109, 4279

Offset: 1

Amiram Eldar, Oct 22 2017

nonn

A018187 (restricted Perrin pseudoprimes) is the intersection of A013998 (unrestricted Perrin pseudoprimes) with this sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000
William Adams and Daniel Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300.

Cf. A001608, A013998, A018187, A078712.

a={}; b=-Drop[CoefficientList[Series[(2x+3)/(x^3-x-1), {x, 0, 10^4}], x] ,1];
Do[If[!PrimeQ[k]&&Divisible[b[[k]]+1,k],AppendTo[a,k]],{k, 2, Length[b]}]; a

A364701 Pseudoprimes corresponding to a Perrin-like primality test.

Original entry on oeis.org

1531398, 114009582, 940084647, 4206644978, 7962908038, 20293639091, 41947594698

Offset: 1

Robert Dougherty-Bliss, Aug 03 2023

The sequence b(n) defined by the generating function (3*x^4+5*x^2+6*x-7)/(4*x^7+x^4+x^2+x-1) has the property that b(p) == 1 (mod p) if p is a prime. A pseudoprime for b(n) is a composite number k such that b(k) == 1 (mod k).

The first seven pseudoprimes are the only ones up to 10^12.

			The value of b(1531398) is a 399290-digit number which is congruent to 1 modulo 1531398 = 2 * 3 * 11 * 23203.

Robert Dougherty-Bliss and Doron Zeilberger, Lots and Lots of Perrin-Type Primality Tests and Their Pseudo-Primes, arXiv:2307.16069 [math.NT], 2023.

b(n) is A362923.

Cf. A001608, A013998, A018187.

A306634 Numbers k such that A215339(6*k+2) = 0.

Original entry on oeis.org

0, 2755452, 4570452, 123725995972

Offset: 1

Seiichi Manyama, Mar 02 2019

Numbers k such that b(k) is an integer, where b(n) = Sum_{k=0..n} (2*n+k)!/((2*n-2*k)!*(3*k+1)!) (= A001608(6*n+2)/(6*n+2)).

			n |       b(n)
--+--------------------------
0 |       1    (=       2/2)
1 |       5/4  (=      10/8)
2 |      51/14
3 |     277/20
4 |    1497/26
5 |    4045/16 (=    8090/32)
6 |   43721/38
7 |  118141/22 (=  236282/44)
8 |  638471/25 (= 1276942/50)
9 | 6900995/56

Don Zagier, Problems posed at the St Andrews Colloquium, 1996, See "Fifth Day: Sequences and recursions, problem 2".

Cf. A001608, A013998, A215339.

A371805 Composite numbers k that divide A001644(k) - 1.

Original entry on oeis.org

182, 25201, 54289, 63618, 194390, 750890, 804055, 1889041, 2487941, 3542533, 3761251, 6829689, 12032021, 12649337, 18002881

Offset: 1

Robert FERREOL, Apr 06 2024

If k is prime, k divides A001644(k) - 1; and since A001644(k) satisfies a tribonacci recurrence, these numbers could be called tribonacci pseudoprimes.

			(A001644(182)-1)/182 = 8056145960961609628091266244940745410646318417.

Cf. A001644.
Cf. A005845 (composite k that divide Lucas(k) - 1).
Cf. A013998 (composite k that divide Perrin(k) - 1).

A001644:=proc(n) option remember: if n=0 then 3 elif n=1 then 1 elif n=2 then 3 else A001644(n-1)+A001644(n-2)+A001644(n-3) fi end:
test:=n->A001644(n) mod n = 1:select(test and not isprime, [seq(n, n=1..100000)]);

seq[kmax_] := Module[{x = 1, y = 3, z = 7, s = {}, t}, Do[t = x + y + z; If[Mod[t, k] == 1 && CompositeQ[k], AppendTo[s, k]]; x = y; y = z; z = t, {k, 4, kmax}]; s]; seq[200000] (* Amiram Eldar, Apr 06 2024 *)

from sympy import isprime
from itertools import count, islice
def agen(): # generator of terms
    t0, t1, t2 = 3, 1, 3
    for k in count(1):
        t0, t1, t2 = t1, t2, t0+t1+t2
        if k > 1 and not isprime(k) and (t0-1)%k == 0:
            yield k
print(list(islice(agen(), 5))) # Michael S. Branicky, Apr 07 2024

a(13)-a(15) from Amiram Eldar, Apr 07 2024

cp's OEIS Frontend

A275613 Restricted Perrin pseudoprimes (Grantham definition).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Perl

A294028 Composite numbers k such that k | 1 - A078712(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A364701 Pseudoprimes corresponding to a Perrin-like primality test.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A306634 Numbers k such that A215339(6*k+2) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A371805 Composite numbers k that divide A001644(k) - 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Python

Extensions