A086019 -id:A086019 - cp's OEIS frontend

A085012 For p = prime(n), a(n) is the smallest prime q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq; a(n) is 0 if no such prime exists.

0, 0, 0, 31, 0, 257, 73, 89, 113, 11, 73, 61681, 127, 178481, 157, 233, 1321, 20857, 281, 19, 2731, 13367, 23, 193, 601, 307, 6361, 37, 29, 43, 2731, 953, 168749965921, 593, 31, 53, 2593, 499, 101653, 62020897, 54001, 2281, 97, 19707683773, 5347, 29191

Offset: 2

T. D. Noe, Jun 28 2003

nonn

Using a construction in Erdős's paper, it can be shown that every odd prime except 3, 5, 7 and 13 is a factor of some 2-factor pseudoprime. Note that the cofactor q can be very large; for p=317, the smallest is 381364611866507317969. Using a theorem of Lehmer, it can be shown that the possible values of q are among the prime factors of 2^(p-1)-1. The sequence A085014 gives the number of 2-factor pseudoprimes that have prime(n) as a factor.

Sequence A086019 gives the largest prime q such that q*prime(n) is a pseudoprime.

			a(11) = 11 because prime(11) = 31 and 11 is the smallest factor of 2^30-1 that yields a pseudoprime when multiplied by 31.

Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.

Amiram Eldar, Table of n, a(n) for n = 2..619
Amiram Eldar, Table of n, a(n) for n = 2..1000 with 2 missing terms (marked with value 0)
Paul Erdős, On the converse of Fermat's theorem, Amer. Math. Monthly 56 (1949), p. 623-624.
D. H. Lehmer, On the converse of Fermat's theorem, Amer. Math. Monthly 43 (1936), p. 347-354.
Index entries for sequences related to pseudoprimes

Cf. A001567 (base-2 pseudoprimes), A085014, A086019, A180471.

Table[p=Prime[n]; q=Transpose[FactorInteger[2^(p-1)-1]][[1]]; i=1; While[i<=Length[q] && (PowerMod[2, p*q[[i]]-1, p*q[[i]]]>1), i++ ]; If[i>Length[q], 0, q[[i]]], {n, 2, 56}]

A085014 For p = prime(n), a(n) is the number of primes q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 2, 1, 3, 2, 1, 3, 2, 2, 4, 1, 2, 3, 5, 4, 3, 6, 4, 4, 6, 4, 5, 4, 6, 5, 4, 2, 5, 8, 7, 5, 6, 3, 3, 3, 4, 5, 4, 4, 5, 9, 8, 7, 8, 5, 8, 7, 8, 4, 6, 6, 7, 7, 9, 6, 11, 7, 8, 2, 7, 12, 8, 6, 8, 4, 5, 5, 6, 5, 11, 10, 9, 11, 5, 8, 9, 12, 9, 4, 7, 13, 8, 5

Offset: 2

T. D. Noe, Jun 28 2003

nonn

Using a construction in Erdős's paper, it can be shown that a(prime(n)) > 0, except for the primes 3, 5, 7 and 13. Using a theorem of Lehmer, it can be shown that the possible values of q are among the prime factors of 2^(p-1)-1. The sequence A085012 gives the smallest prime q such that q*prime(n) is a pseudoprime.

Sequence A086019 gives the largest prime q such that q*prime(n) is a pseudoprime.

			a(11) = 3 because prime(11) = 31 and 2^30-1 has 3 prime factors (11, 151, 331) that yield pseudoprimes when multiplied by 31.

Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.

Amiram Eldar, Table of n, a(n) for n = 2..337
Paul Erdős, On the converse of Fermat's theorem, Amer. Math. Monthly 56 (1949), p. 623-624.
D. H. Lehmer, On the converse of Fermat's theorem, Amer. Math. Monthly 43 (1936), p. 347-354.
Index entries for sequences related to pseudoprimes

Cf. A001567 (base-2 pseudoprimes), A085012, A086019, A180471.

Table[p=Prime[n]; q=Transpose[FactorInteger[2^(p-1)-1]][[1]]; cnt=0; Do[If[PowerMod[2, p*q[[i]]-1, p*q[[i]]]==1, cnt++ ], {i, Length[q]}]; cnt, {n, 2, 50}]

a(n) < 0.7 * p, where p is the n-th prime. - Charles R Greathouse IV, Apr 12 2012

A358699 a(n) is the largest prime factor of 2^(prime(n) - 1) - 1.

Original entry on oeis.org

3, 5, 7, 31, 13, 257, 73, 683, 127, 331, 109, 61681, 5419, 2796203, 8191, 3033169, 1321, 599479, 122921, 38737, 22366891, 8831418697, 2931542417, 22253377, 268501, 131071, 28059810762433, 279073, 54410972897, 77158673929, 145295143558111, 2879347902817, 10052678938039

Offset: 2

Hugo Pfoertner, Nov 27 2022

nonn

Amiram Eldar, Table of n, a(n) for n = 2..197 (terms 2..120 from Hugo Pfoertner)

Cf. A005420, A006093, A006530, A061286, A071243, A086019, A098102.

Subsequence of A005420 and of A274906.

forprime (p=3, 140, my(f=factor(2^(p-1)-1)); print1(f[#f[,1],1],", "))

from sympy import primefactors, sieve
def A358699(n): return primefactors(2**(sieve[n]-1)-1)[-1] # Karl-Heinz Hofmann, Nov 28 2022

a(n) = A006530(A098102(n)). - Michel Marcus, Nov 28 2022

a(n) = A005420(A006093(n)). - Amiram Eldar, Dec 01 2022

cp's OEIS Frontend

A085012 For p = prime(n), a(n) is the smallest prime q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq; a(n) is 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A085014 For p = prime(n), a(n) is the number of primes q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A358699 a(n) is the largest prime factor of 2^(prime(n) - 1) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Formula