A085012 -id:A085012 - cp's OEIS frontend

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.

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

A180471 Irregular triangle in which row n has all primes q such that prime(n)*q is a base-2 Fermat pseudoprime.

Original entry on oeis.org

31, 257, 73, 89, 683, 113, 11, 151, 331, 73, 109, 61681, 127, 337, 5419, 178481, 2796203, 157, 1613, 233, 1103, 2089, 3033169, 1321, 20857, 599479, 281, 86171, 122921, 19, 37, 109, 433, 38737, 2731, 8191, 121369, 22366891, 13367, 164511353, 8831418697, 23, 353, 397, 683, 2113, 2931542417

Offset: 5

T. D. Noe, Jan 19 2011

The length of row n is A085014(n). The smallest and largest primes in row n are A085012(n) and A085019(n).

			The irregular triangle begins
31
none
257
73
89, 683
113
11, 151, 331
73, 109
61681

See A085012.

Amiram Eldar, Table of n, a(n) for n = 5..3424
Index entries for sequences related to pseudoprimes

Cf. A085012, A085014, A085019.

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

A086019 For p = prime(n), a(n) is the largest 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.

Original entry on oeis.org

0, 0, 0, 31, 0, 257, 73, 683, 113, 331, 109, 61681, 5419, 2796203, 1613, 3033169, 1321, 599479, 122921, 38737, 22366891, 8831418697, 2931542417, 22253377, 268501, 131071, 28059810762433, 279073, 54410972897, 77158673929, 145295143558111

Offset: 2

T. D. Noe, Jul 08 2003

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. Sequence A085012 gives the smallest prime q such that 2^(pq-1) = 1 mod pq. Sequence A085014 gives the number of 2-factor pseudoprimes that have prime(n) as a factor.

			a(9) = 683 because prime(9) = 23 and 683 is the largest factor of 2^22-1 that yields a pseudoprime when multiplied by 23.

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.

Cf. A001567 (base 2 pseudoprimes), A085012, A085014, A180471.

Table[p=Prime[n]; q=Reverse[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, 40}]

A086000 For p = prime(n), a(n) is the smallest N such that pN is a base-2 pseudoprime (that is, 2^(pN-1) = 1 mod pN).

Original entry on oeis.org

187, 129, 247, 31, 85, 33, 73, 89, 85, 11, 73, 161, 15, 93, 157, 233, 481, 133, 281, 19, 391, 1067, 23, 193, 601, 307, 6361, 37, 29, 15, 2731, 545, 10213, 593, 31, 53, 2593, 499, 1205, 141155, 1261, 2281, 97, 3333, 1387, 1891, 1777, 3391, 381, 59, 20231, 97

Offset: 2

T. D. Noe, Jul 08 2003

Tables compiled by Pinch were used. Sequence A085999 lists a(n)*prime(n). It can be shown that a(n) has the form 1 + 2 ord(4, prime(n)) k for some k > 0, where the ord(x,y) function is the smallest positive integer r such that x^r = 1 mod y. The value of k for a(n) is given in sequence A086001. Note that prime(n) divides 2^a(n) - 2. Compare A085012, which gives the smallest prime q such that pq is a 2-pseudoprime.

			a(2) = 187 because prime(2) = 3 and N=187 is the smallest number such that 3N is a 2-pseudoprime.

Amiram Eldar, Table of n, a(n) for n = 2..10001
R. G. E. Pinch, Pseudoprimes and their factors (FTP).
Eric Weisstein's World of Mathematics, Pseudoprime.

Cf. A001567 (base-2 pseudoprimes), A082654 (ord(4, p)), A085012, A085999, A086001.

Table[p=Prime[n]; m=MultiplicativeOrder[4, p]; k=1; While[psp=p(1+2*m*k); PowerMod[2, psp-1, psp]!=1, k++ ]; 1+2*m*k, {n, 2, 100}]

A086001 For p = prime(n), a(n) is the smallest k such that p*(1 + 2 Ord(4,p) k) is a base-2 pseudoprime.

Original entry on oeis.org

93, 32, 41, 3, 7, 4, 4, 4, 3, 1, 2, 8, 1, 2, 3, 4, 8, 2, 4, 1, 5, 13, 1, 4, 6, 3, 60, 1, 1, 1, 21, 8, 74, 4, 1, 1, 16, 3, 7, 793, 7, 12, 1, 17, 7, 9, 24, 15, 5, 1, 85, 4, 1, 1, 4, 2155, 3, 1, 1, 25, 6, 1, 27, 1, 1669, 1, 1, 12, 6, 1, 4, 57, 15, 29, 817, 4, 2, 3, 4, 63, 3, 20, 1, 12, 3, 11, 3, 9, 31

Offset: 2

T. D. Noe, Jul 08 2003

Sequences A085999 and A086000 list p*(1 + 2 Ord(4,p) k) and 1 + 2 Ord(4,p) k., respectively. Although, for any prime p, Dirichlet's theorem says the sequence 1 + 2 Ord(4,p) k contains an infinite number of primes, only a finite number of these produce a pseudoprime when multiplied by p.

			a(11) = 1 because prime(11) = 31, ord(4,31) = 5 and 31*(1+2*5*1) is a 2-pseudoprime.

Amiram Eldar, Table of n, a(n) for n = 2..10001
Eric Weisstein's World of Mathematics, Pseudoprime.

Cf. A001567 (base-2 pseudoprimes), A082654 (ord(4, p)), A085012, A085999, A086000.

Table[p=Prime[n]; m=MultiplicativeOrder[4, p]; k=1; While[psp=p(1+2*m*k); PowerMod[2, psp-1, psp]!=1, k++ ]; k, {n, 2, 100}]

cp's OEIS Frontend

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

A180471 Irregular triangle in which row n has all primes q such that prime(n)*q is a base-2 Fermat pseudoprime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A086019 For p = prime(n), a(n) is the largest 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

A086000 For p = prime(n), a(n) is the smallest N such that pN is a base-2 pseudoprime (that is, 2^(pN-1) = 1 mod pN).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A086001 For p = prime(n), a(n) is the smallest k such that p*(1 + 2 Ord(4,p) k) is a base-2 pseudoprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica