Dana Jacobsen - cp's OEIS frontend

User: Dana Jacobsen

Dana Jacobsen has authored 3 sequences.

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

A275612 Restricted Perrin pseudoprimes (Adams and Shanks definition).

Original entry on oeis.org

Offset: 1

Dana Jacobsen, Aug 03 2016

nonn

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

Dana Jacobsen, Table of n, a(n) for n = 1..706
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)

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);
} \\ Dana Jacobsen, Aug 03 2016

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

A267012 Numbers n such that the n-th prime equals the n-th Ramanujan prime of the totient of n.

Original entry on oeis.org

1, 10, 28, 50, 56, 874, 1575, 3604, 4966, 30704, 55964, 56372, 145616, 195016, 200792, 227278, 1679518, 2611874, 3028502, 23070602, 27365684, 45639626

Offset: 1

Dana Jacobsen, Jan 08 2016

n such that A000040(n) = A104272(A000010(n)).

Values are not prime, since for n > 1, A104272(n) > 2 * A000040(n) and A000010(n) = n-1 for prime n.

			28 is in the sequence because the totient of 28 is 12, the 12th Ramanujan prime is 107, and the 28th prime is also 107.

Cf. A000010, A000040, A104272.

lim = 60000; r = Table[0, {lim}]; s = 0; Do[If[PrimeQ[k], s++]; If[PrimeQ[k/2], s--]; If[s < lim, r[[s + 1]] = k], {k, Prime[3 lim]}]; r = r + 1; Select[Range@ lim, Prime@ # == r[[EulerPhi@ #]] &] (* Michael De Vlieger, Jan 09 2016, after T. D. Noe at A104272 *)

use ntheory ":all"; sub is { my $n = shift; nth_prime($n) == nth_ramanujan_prime(euler_phi($n)); } for (1..1e5) { say if is($_) }

use ntheory ":all"; my $lim = 1e7; my($pr,$rp) = (primes(nth_prime($lim)), ramanujan_primes(nth_ramanujan_prime($lim))); for (1..$lim) { say if $pr->[$-1] == $rp->[euler_phi($)-1]; } # high memory use but faster

cp's OEIS Frontend

User: Dana Jacobsen

A275613 Restricted Perrin pseudoprimes (Grantham definition).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Perl

A275612 Restricted Perrin pseudoprimes (Adams and Shanks definition).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Perl

A267012 Numbers n such that the n-th prime equals the n-th Ramanujan prime of the totient of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Perl

Perl