A194946 -id:A194946 - cp's OEIS frontend

A195327 Number of bases to which terms of A194946 are pseudoprime.

2, 4, 8, 16, 36, 40, 48, 100, 144, 324, 484, 900, 1296, 1764, 2116, 2704, 3600, 6084, 9216, 13728, 19044, 24336, 30000, 39204, 39360, 44100, 51984, 63888, 72900, 81648, 93636, 108900, 112896, 133956, 142884, 191844, 229376, 248004, 269568, 298116

Offset: 1

Charles R Greathouse IV, Sep 15 2011

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..659
Index entries for sequences related to pseudoprimes

Cf. A194946, A195328.

bases(n)=my(f=factor(n)[, 1]); n--; prod(i=1, #f, gcd(f[i]-1, n)) \\ Given a value of A194946, this function transforms it to a term of this sequence.

A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.

Original entry on oeis.org

9, 25, 49, 91, 341, 481, 703, 1541, 1891, 2701, 5461, 6533, 8911, 12403, 18721, 29341, 31621, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631, 1869211, 2741311

Offset: 1

Charles R Greathouse IV, Sep 15 2008

nonn

These numbers are the worst cases for the Rabin-Miller probable-prime test.
Alford, Granville, & Pomerance show that this sequence is infinite.
The sequence is unchanged whether one, both, or neither of 1 and n-1 are included as bases.

			25 is a 1-, 7-, 18- and 24-strong pseudoprime and no odd number less than 25 has four or more bases to which it is a strong pseudoprime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..5476
W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 1-16.
Shyam Narayanan, Improving the Speed and Accuracy of the Miller-Rabin Primality Test
Shyam Narayanan, Improving the Accuracy of Primality Tests by Enhancing the Miller-Rabin Theorem (2014)
Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12:1 (1980), pp. 128-138.
Index entries for sequences related to pseudoprimes

Cf. A014233, A071294, A194946.

star(n)={n--;n>>valuation(n,2)};
bases(n)=my(f=factor(n)[,1], nu=valuation(f[1]-1, 2), nn = star(n));for(i=2,#f,nu = min(nu, valuation(f[i] - 1, 2)););(1 + (2^(#f * nu) - 1) / (2^#f - 1)) * prod(i=1, #f, gcd(nn, star(f[i])));
r=0;forstep(n=9,1e8,2,if(isprime(n),next);t=bases(n);if(t>r,r=t;print1(n",")))

Edited by Charles R Greathouse IV, Jul 23 2010

A274175 Composite numbers c that set a new record for the number of bases b with 1 < b < c such that c satisfies b^(c-1) == 1 (mod c^2), i.e., such that c is a base-b "Wieferich pseudoprime".

Original entry on oeis.org

133, 1065, 141373

Offset: 1

Felix Fröhlich, Jun 12 2016

a(4) > 253263 if it exists.
Is the sequence infinite?
Let x be the integer sequence defined as x(n) = number of bases 1 < b < c such that c is a base-b "Wieferich pseudoprime", where c is the n-th composite number (that sequence does not have its own entry in the OEIS). Then a(n) is the sequence of composites where x(n) reaches record values.
Let y be the integer sequence defined as y(n) = smallest composite c with exactly n bases 1 < b < c such that c is a base-b "Wieferich pseudoprime". Is a(n) = y(n) for all n?
For every b with 1 < b < c such that c is a base-b "Wieferich pseudoprime", every prime factor p of c is a base-b Wieferich prime.

			c = 141373 satisfies b^(c-1) == 1 (mod c^2) for three values of b with 1 < b < c, namely b = 23382, 36620 and 130595. Since no other composite c < 141373 exists that has more than two such b, 141373 is a term of the sequence.

Cf. A194946, A248865, A256517, A267288.

my(r=0, i); forcomposite(c=1, , i=0; for(b=2, c-1, if(Mod(b, c^2)^(c-1)==1, i++)); if(i > r, print1(c, ", "); r=i))

cp's OEIS Frontend

A195327 Number of bases to which terms of A194946 are pseudoprime.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A274175 Composite numbers c that set a new record for the number of bases b with 1 < b < c such that c satisfies b^(c-1) == 1 (mod c^2), i.e., such that c is a base-b "Wieferich pseudoprime".

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI