A007535 -id:A007535 - cp's OEIS frontend

A250199 Smallest pseudoprime (>prime(n)) to base prime(n).

341, 91, 124, 25, 15, 21, 45, 45, 33, 35, 49, 45, 105, 77, 65, 65, 87, 91, 85, 105, 111, 91, 105, 99, 105, 175, 133, 133, 117, 133, 153, 143, 148, 161, 175, 175, 186, 186, 231, 205, 185, 195, 217, 276, 231, 225, 217, 231, 285, 285, 259, 255, 363, 289, 301, 341, 286, 341, 322, 329

Offset: 1

Eric Chen, Feb 21 2015

nonn

Subsequence of A007535, see formula.

			a(7) = 45 because the 7th prime is 17, and the smallest pseudoprime (> 17) to base 17 is 45.

Eric Chen, Table of n, a(n) for n = 1..4096

Cf. A007535, A090086, A108162, A098650.

f[n_] := Block[{b = Prime[n], k = Prime[n] + 1}, While[PrimeQ[k] || PowerMod[b, k - 1, k] != 1, k++]; k]; Array[f, 60]

a(n) = for(k=prime(n)+1,2^24,if(Mod(prime(n),k)^(k-1)==Mod(1,k) && !isprime(k),return(k)))

a(n) = A007535(A000040(n)).

A078505 Possible values for smallest pseudoprime ( > n ) to base n.

Original entry on oeis.org

4, 9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 66, 69, 75, 76, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124, 125, 129, 133, 135, 141, 143, 145, 147, 148, 153, 155, 159, 161, 165, 169, 171, 172, 175, 177, 183, 185, 186

Offset: 1

Jason Earls, Jan 05 2003

nonn

Sean A. Irvine, Table of n, a(n) for n = 1..1000

Cf. A007535.

A245097 Number of primes greater than n and not greater than the smallest pseudoprime to base n.

Original entry on oeis.org

2, 67, 22, 4, 27, 8, 5, 0, 5, 7, 1, 13, 2, 0, 62, 9, 7, 2, 6, 0, 8, 11, 2, 0, 0, 0, 9, 5, 1, 5, 4, 0, 12, 0, 4, 13, 2, 0, 12, 12, 14, 33, 7, 0, 7, 18, 3, 0, 3, 0, 3, 8, 2, 0, 2, 0, 2, 16, 6, 51, 6, 0, 50, 0, 11, 6, 4, 0, 4, 20, 7, 3, 8, 0, 3, 0, 32, 47, 2, 0

Offset: 1

Reinhard Zumkeller, Nov 12 2014

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000720, A007535, A010051.

a245097 n = sum $ map a010051' [n + 1 .. a007535 n]

f(n) = forcomposite(m=n+1, , if(Mod(n, m)^(m-1)==1, return(m))); \\ A007535
a(n) = primepi(f(n)) - primepi(n); \\ Michel Marcus, Jan 24 2022

a(n) = Sum {k=n+1..A007535(n)} A010051(k).

a(n) = A000720(A007535(n)) - A000720(n).

A253233 Smallest even pseudoprime (>2n+1) in base 2n+1.

Original entry on oeis.org

4, 286, 124, 16806, 28, 70, 244, 742, 1228, 906, 1852, 154, 28, 286, 52, 66, 496, 442, 66, 1834, 344, 526974, 76, 506, 66, 70, 286, 1266, 2296, 946, 130, 5662, 112, 154, 14246, 370, 276, 8614, 2806, 2626, 112, 1558, 276, 2626, 19126, 1446, 322, 658, 176, 742, 190, 946, 5356, 742, 186, 190, 176, 8474, 2806, 2242, 148

Offset: 0

Eric Chen, May 17 2015

nonn

For an even base there are no even pseudoprimes.
Conjecture: There are infinitely many even pseudoprimes in every odd base.
Records: 4, 286, 16806, 526974, 815866, 838246, ..., and they occur at indices: 0, 1, 3, 21, 503, 691, ...

Eric Chen, Table of n, a(n) for n = 0..999 (a(0) corrected by _Georg Fischer_, Jan 20 2019)
Eric Weisstein's World of Mathematics, Fermat pseudoprime
Wikipedia, Fermat pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A005097, A090082, A090083, A090084, A090085, A090086, A090087, A090088, A090089, A108162, A130433, A130434, A130435, A130436, A130437, A130438, A130439, A130440, A139441, A130442, A130443, A007535.

f[n_] := Block[{k = 2 * n + 2}, While[PrimeQ[k] || OddQ[k] || PowerMod[2 * n + 1, k - 1, k] != 1, k++ ]; k]; Table[ f[n], {n, 0, 60}]

a(n) = for(k=n+1, 2^24, if(!isprime(2*k) && Mod(2*n+1, 2*k)^(2*k-1) == Mod(1, 2*k), return(2*k)))

a(A005097(n-1)) = A108162(n).

A316504 Numbers n such that A090086(n+1) > n+1.

Original entry on oeis.org

0, 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 47, 53, 59, 71, 83, 89, 101, 109, 139, 149, 157, 179, 199, 307, 461, 571

Offset: 1

Thomas Ordowski, Aug 12 2018

Probably complete.
Numbers n such that A090086(n+1) = A007535(n+1).
For n > 1, if A090086(n+1) > n+1, then n is a prime.

Cf. A000040, A090086, A007535, A317851.

a090086(n) = {forcomposite(k=2, , if (Mod(n, k)^(k-1) == 1, return (k)); ); }
isok(n) = a090086(n+1) > n+1; \\ Michel Marcus, Aug 12 2018

A090099 Smallest bases the smallest true-prime-power-pseudoprime is belonging to equals a true power of n-th prime.

Original entry on oeis.org

1, 8, 7, 30, 3, 22, 38, 54, 42, 14

Offset: 1

Labos Elemer, Dec 01 2003

nonn

			n=10: p[10]=29, a[10]=14 because -1+14^(841-1)=840.k,
and in A020142 the terms<841 are not powers of primes.
Corresponding least p-power pseudoprimes are 4,9,25,49,121,..,841,..

Cf. A020142, A090096-A090098, A007535.

A163582 Smallest pseudoprimes in ascending bases b of the form pq, where p = (b^k - 1) / (b - 1) and q = (b^k + 1) / (b + 1), both prime, with k a prime less than 100.

Original entry on oeis.org

341, 597871, 1010101010101010101010101010101010101, 432988561, 584645231109031, 54989488181, 48793204382746801501446610630739608190006929723969, 11694525061301

Offset: 2

Reikku Kulon, Jul 31 2009

nonn

These numbers can be factored in O(log n) time by iterating over their multiplicative Sylow p-subgroups.
Let n be an odd integer. Its maximal multiplicative order is n - 1; the largest power of 2 dividing n - 1 is o, the maximal order of its multiplicative Sylow 2-subgroup.
Let t = (n - 1) / o.
Pick random integers x and y such that the Jacobi symbols (x/n) and (y/n) are -1; that is, x and y are quadratic nonresidues modulo n. Exponentiate both by t to produce generators of the Sylow 2-subgroup. Retain the value of y as r.
Repeatedly multiply x by y and y by r, modulo n, giving a parabolic sequence of x values. A factor may be obtained from gcd(x - 1, n), gcd(y - 1, n), gcd(x - y, n), or gcd(x + y, n). If a factor is not found quickly, choose new values of x and y.
It is often the case that one iteration is sufficient, instead of log n iterations.

			341 = 11 * 31 is a base 2 pseudoprime; 2^340 = 1 (mod 341).
597871 = 547 * 1093 is a base 3 pseudoprime; 3^597870 = 1 (mod 597871).
1010101010101010101010101010101010101 = 909090909090909091 * 1111111111111111111 is a base 10 pseudoprime.
The smallest base 387 pseudoprime semiprime has 1204 bits:
190343478807499085058031516398268680442601127373980882552883668761244360084075072419711216782718751807174818426029099795926922432206385551671790497449073768776989824173201266255008090697631436472577273835739136689804694203609505130893771033656337490070783749133621893887506391690839509492668015407074108567267922714146861065256735761674160812989129563106060165551
which has factors
13760898475567760339045070218774452423864352937859851193617152180919304736064745532601237230112112091064203139709556823171465678472351610172571294148439637693965101978819764531439203
and
13832198467669147698314733795037532488236707098159643168713614109317850356458863385101761775345853604489406264785772143498778972143192810225278917434182848251964921160057172637819717
The large factor can be found in 8 iterations, taking six seconds on a 2GHz processor. In general, factorization requires less than a minute for numbers having fewer than 2000 bits.

Cf. A000040, A001358, A007535

A247906 a(n) = n-th pseudoprime to base n.

Original entry on oeis.org

561, 286, 341, 781, 1105, 1105, 133, 364, 703, 793, 1105, 1099, 1891, 6541, 1271, 3991, 1649, 1849, 3059, 7363, 2047, 1738, 4537, 1128, 3145, 2993, 5365, 4069, 4097, 7421, 2465, 11305, 2937, 16589, 4495, 2044, 6601, 26885, 13073, 6892, 22945, 3885, 8695, 10879

Offset: 2

Felix Fröhlich, Sep 26 2014

nonn

			a(2) = A001567(2) = 561.
a(3) = A005935(3) = 286.

Cf. A007535, A098650.

Cf. Pseudoprimes to base b: A001567 (b=2), A005935 (b=3), A020136 (b=4), A005936 (b=5), A005937 (b=6), A005938 (b=7), A020137 (b=8), A020138 (b=9).

for(n=2, 20, i=0; forcomposite(c=2, 1e9, if(Mod(n, c)^(c-1)==1, i++; if(i==n, print1(c, ", "); i=0; break({1}))); if(c==1e9, print1(">1e9, "))))

cp's OEIS Frontend

A250199 Smallest pseudoprime (>prime(n)) to base prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A078505 Possible values for smallest pseudoprime ( > n ) to base n.

Views

Author

Keywords

Links

Crossrefs

A245097 Number of primes greater than n and not greater than the smallest pseudoprime to base n.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

PARI

Formula

A253233 Smallest even pseudoprime (>2n+1) in base 2n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A316504 Numbers n such that A090086(n+1) > n+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A090099 Smallest bases the smallest true-prime-power-pseudoprime is belonging to equals a true power of n-th prime.

Views

Author

Keywords

Examples

Crossrefs

A163582 Smallest pseudoprimes in ascending bases b of the form pq, where p = (b^k - 1) / (b - 1) and q = (b^k + 1) / (b + 1), both prime, with k a prime less than 100.

Views

Author

Keywords

Comments

Examples

Crossrefs

A247906 a(n) = n-th pseudoprime to base n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI