A001567 -id:A001567 - cp's OEIS frontend

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.

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}]

A086249 Number of base-2 Fermat pseudoprimes x that have ord(2,x) = n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 3, 1, 2, 1, 1, 0, 12, 4, 3, 0, 1, 1, 1, 1, 12, 1, 1, 4, 5, 1, 9, 4, 10, 8, 3, 4, 25, 0, 10, 11, 11, 4, 1, 4, 15, 4, 22, 1, 57, 0, 1, 4, 10, 1, 24, 1, 11, 1, 41, 4, 86, 4, 10, 25, 11, 0, 21, 4, 7, 4, 10, 1, 52, 1, 7, 10, 22, 0, 26, 11, 56, 1

Offset: 1

T. D. Noe, Jul 14 2003

A base-2 Fermat pseudoprime is a composite number x such that 2^x == 2 (mod x). For such an x, ord(2,x) is the smallest positive integer m such that 2^m == 1 (mod x). For a number x to have order n, it must be a factor of 2^n-1 and not be a factor of 2^r-1 for rA086250 lists the smallest pseudoprime of order n.

Note that there is no pseudoprime of order n when 2^n-1 is prime. However that does not explain why there are none for 12, 27, 49 and 77.

			a(10) = 1 there is only 1 pseudoprime, 341 = 11*31, having order 10; that is, 2^10 = 1 mod 341.

Max Alekseyev, Table of n, a(n) for n = 1..200
R. G. E. Pinch, Pseudoprimes and their factors (FTP)
Eric Weisstein's World of Mathematics, Pseudoprime

Cf. A001567 (base-2 pseudoprimes), A086250.

Table[d=Divisors[2^n-1]; cnt=0; Do[m=d[[i]]; If[ !PrimeQ[m]&&PowerMod[2, m, m]==2&&MultiplicativeOrder[2, m]==n, cnt++ ], {i, Length[d]}]; cnt, {n, 100}]

{ a(n) = my(r=0); fordiv(2^n-1,d, if(d>1 && (d-1)%n==0 && !ispseudoprime(d) && znorder(Mod(2,d),n)==n,r++) ); r } /* Max Alekseyev, Jan 07 2015 */

A122785 Nonprimes m such that 8^m == 8 (mod m).

Original entry on oeis.org

1, 4, 8, 9, 14, 21, 28, 45, 56, 63, 65, 105, 117, 133, 153, 231, 273, 292, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1016, 1105, 1106, 1281, 1288, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1736, 1785, 1905, 2044, 2047, 2169, 2465, 2501, 2696, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005

Offset: 1

Farideh Firoozbakht, Sep 12 2006

nonn

Theorem: If both numbers q and 2q-1 are primes and m=q*(2q-1) then 8^m==8 (mod m) (m is in the sequence) iff q is of the form 4k+1. 2701,18721,49141,104653,226801,665281,721801,... are such terms.

Cf. A020137, A001567.

q:= m-> not isprime(m) and 8&^m mod m = 8 mod m:
select(q, [$1..5000])[];  # Alois P. Heinz, Apr 19 2022

Select[Range[6000], ! PrimeQ[ # ] && Mod[8^#, # ] == Mod[8, # ] &]

Missing a(8)-a(18) inserted by Georg Fischer, Apr 19 2022

A175625 Numbers k such that gcd(k, 6) = 1, 2^(k-1) == 1 (mod k), and 2^(k-3) == 1 (mod (k-1)/2).

Original entry on oeis.org

7, 11, 23, 31, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 683, 719, 839, 863, 887, 983, 1019, 1123, 1187, 1283, 1291, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2543

Offset: 1

Alzhekeyev Ascar M, Jul 28 2010, Jul 30 2010

nonn

All composites in this sequence are 2-pseudoprimes, A001567. That subsequence begins with 536870911, 46912496118443, 192153584101141163, with no other composites below 2^64 (the first two were found by 'venco' from the dxdy.ru forum), and contains the terms of A303448 that are not multiples of 3. Correspondingly, composite terms include those of the form A007583(m) = (2^(2m+1) + 1)/3 for m in A303009. The only known composite member not of this form is a(1018243) = 536870911.
Intended as a pseudoprimality test; note that many primes do not pass the third condition either.
Conjecture: The prime values belong to A039787. - Bill McEachen, Dec 27 2023

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A001567, A007583, A303009, A303448.

Cf. A039787.

Select[Array[(6 # + (-1)^# - 3)/2 &, 3000], And[PowerMod[2, (# - 1), #] == 1, PowerMod[2, (# - 3), (# - 1)/2] == 1] &] (* Michael De Vlieger, Dec 27 2023 *)

isA175625(n) = gcd(n,6)==1 && Mod(2,n)^(n-1)==1 && Mod(2,n\2)^(n-3)==1

Partially edited by N. J. A. Sloane, Jul 29 2010
Entry rewritten by Charles R Greathouse IV, Aug 04 2010
Comment and b-file from Charles R Greathouse IV, Sep 06 2010
Edited by Max Alekseyev, May 28 2014, Apr 24 2018

A175738 Sizes of successive increasing gaps between 2-pseudoprimes.

Original entry on oeis.org

220, 460, 756, 780, 1140, 1356, 1496, 2000, 3050, 3580, 4532, 4784, 5220, 7140, 12132, 20412, 20650, 22320, 26076, 39424, 42392, 65740, 81252, 87698, 137104, 164448, 203506, 370396, 484140, 491526, 506940, 667908, 682820, 777224, 951114, 1201538

Offset: 1

Charles R Greathouse IV, Aug 28 2010

Rotkiewicz proves that a(n) < A175736(n)^2, and that the exponent can be replaced by 1 + epsilon for large enough n.

A. Rotkiewicz, "Les intervalles contenants les nombres pseudopremiers", Rendiconti del Circolo Matematico di Palermo, Series 2, 14 (1965), pp. 278-280.

Charles R Greathouse IV, Table of n, a(n) for n = 1..207
Charles R Greathouse IV, Illustration of gap sizes vs. lower end
H. Halberstam and A. Rotkiewicz, A gap theorem for pseudoprimes in arithmetic progression, Acta Arithmetica 13 (1967/1968), pp. 395-404.
Eric Weisstein's World of Mathematics, Fermat Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A001567 (2-pseudoprimes), A175736 (lower end), A175737 (upper end).

a(n) = A175737(n) - A175736(n).

A176033 Numbers k such that 2^(2k-1) == 2 (mod 2k) and such that 2^(k-1) != 1 (mod k).

Original entry on oeis.org

15, 85, 91, 435, 451, 703, 1247, 1271, 1581, 1695, 1891, 2071, 3133, 3367, 3683, 4795, 4859, 5551, 6643, 8695, 9061, 9131, 9211, 9605, 9919, 12403, 13019, 14351, 14701, 15051, 15211, 16021, 16471, 19669, 20191, 20485, 24727, 25351, 26335, 26599, 27511, 28645

Offset: 1

Alzhekeyev Ascar M, Dec 06 2010

nonn

The associated value m = (2^(k-1) mod k) satisfy 1 < gcd(m-1, k) < k.
The selection criterion 2^(2k-1) == 2 (mod 2k) admits 3, 5, 7, 11, 13, 15, 17, etc.
Expect that the sequences will be infinite only if the criterion has the form 2^(2k-1) == 2^m (mod 2k) where m - an integer (1, 2, ...), otherwise the sequence will be limited. For example, for criterion 2^(2k-1) == 14 (mod 2k), the sequence begins 9, 27, 7281, 19143.

Robert Israel, Table of n, a(n) for n = 1..1000

Set difference of A020136 and A001567. - Max Alekseyev, Nov 06 2017

select(n -> 2 &^ (2*n-1) - 2 mod (2*n) = 0 and 2 &^ (n-1) -1 mod n <> 0, [seq(n,n=3..10^5,2)]); # Robert Israel, Nov 06 2017

Select[Range[30000],PowerMod[2,2#-1,2#]==2&&PowerMod[2,#-1,#]!=1&] (* Harvey P. Dale, Jul 06 2025 *)

alist(m) = {for (n=1, m, v = 2^(2*n-1); if ((v % (2*n) == 2), k = 2^(n-1) % n; if (k > 1, print1(n, ", "););););} \\ Michel Marcus, Jan 24 2013

More terms from Michel Marcus, Jan 24 2013

A216170 Fermat pseudoprimes to base 2 of the form (n^2 + 2*n)/3.

Original entry on oeis.org

341, 645, 2465, 2821, 4033, 5461, 8321, 15841, 25761, 31621, 68101, 83333, 162401, 219781, 282133, 348161, 530881, 587861, 653333, 710533, 722261, 997633, 1053761, 1082401, 1193221, 1246785, 1333333, 1357441, 1398101, 1489665, 1584133, 1690501, 1735841

Offset: 1

Marius Coman, Sep 03 2012

nonn

The corresponding values of n: 31, 43, 85, 91, 109, 127, 157, 217, 277, 307, 451, 499, 697, 811, 919, 1021, 1261, 1327, 1399, 1459, 1471, 1729, 1777, 1801, 1891, 1933, 1999, 2017, 2047, 2113, 2177, 2251.
The formula can be generalized this way: Fermat pseudoprimes to base 2 of the form (n^m + m*n)/(m+1).
For m = 3, the formula becomes (n^3 + 3*n)/4, from which the Poulet numbers 341, 1729, 188461, 228241, and 1082809 (for n = 11, 19, 91, 97, and 163, respectively) were obtained.
Conjecture: For any m natural, m > 1, there exists a series with infinitely many Fermat pseudoprimes to base 2, P, formed this way: P = (n^m + m*n)/(m+1).

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Poulet Number

Cf. A001567, A210454 (subsequence).

t = Select[Table[n (n + 2)/3, {n, 4, 10000}], IntegerQ]; Select[t, PowerMod[2, # - 1, #] == 1 &] (* T. D. Noe, Sep 03 2012 *)

list(lim)=my(v=List(),t); lim\=1; forstep(n=31,sqrtint(3*lim+1)-1,[2,1], t=t=n*(n+2)/3; if(Mod(2,t)^t==2, listput(v,t))); Vec(v) \\ Charles R Greathouse IV, Jun 30 2017

A225101 Numerator of (2^n - 2)/n.

Original entry on oeis.org

0, 1, 2, 7, 6, 31, 18, 127, 170, 511, 186, 2047, 630, 8191, 10922, 32767, 7710, 131071, 27594, 524287, 699050, 2097151, 364722, 8388607, 6710886, 33554431, 44739242, 19173961, 18512790, 536870911, 69273666, 2147483647, 2863311530, 8589934591, 34359738366, 34359738367, 3714566310

Offset: 1

Alonso del Arte, Apr 28 2013

That (2^n - 2)/n is an integer when n is prime can easily be proved as a simple consequence of Fermat's little theorem.

It was believed long ago that (2^n - 2)/n is an integer only when n = 1 or a prime. In 1819, Frédéric Sarrus found the smallest counterexample, 341; these pseudoprimes are now sometimes called "Sarrus numbers" (A001567).

			a(4) = 7 because (2^4 - 2)/4 = 7/2.
a(5) = 6 because (2^5 - 2)/5 = 6.
a(6) = 31 because (2^6 - 2)/6 = 31/3.

Alkiviadis G. Akritas, Elements of Computer Algebra With Application. New York: John Wiley & Sons (1989): 66.
George P. Loweke, The Lore of Prime Numbers. New York: Vantage Press, 1982, p. 22.

Colin Barker, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Chinese Hypothesis

Cf. A001567, A064535, A159353 (denominators).

[Numerator((2^n - 2)/n): n in  [1..60]]; // Vincenzo Librandi, Nov 09 2014

A225101:=n->numer((2^n-2)/n): seq(A225101(n), n=1..50); # Wesley Ivan Hurt, Nov 10 2014

Mathematica
```
Table[Numerator[(2^n - 2)/n], {n, 50}]
```

vector(100, n, numerator((2^n - 2)/n)) \\ Colin Barker, Nov 09 2014

A228575 Pseudoprimes n to base 2 such that n-4, n-2 and n+2 are primes.

Original entry on oeis.org

645, 656601, 6212361, 18958567881, 287468425245, 626160901281, 1395494019921, 1925525109201, 1960708164801, 1962378065901, 1977370759365, 2788325761551, 3032013857181, 6877227801081, 22298617759881, 30242009317521, 39454593651201, 42401101442001

Offset: 1

Shyam Sunder Gupta, Oct 27 2013

nonn

All numbers in this sequence end in either 5 or 1.

			645 is a pseudoprime (base 2) and 641, 643 and 647 are primes.

Shyam Sunder Gupta, Table of n, a(n) for n = 1..831

Cf. A001567, A057942, A230488, A230489.

A230483 Strong pseudoprimes (base 2) that become prime when two is subtracted.

Original entry on oeis.org

4681, 29341, 42799, 49141, 52633, 85489, 90751, 104653, 458989, 1004653, 1082401, 1251949, 1302451, 1907851, 2510569, 2811271, 3090091, 3539101, 5044033, 5049001, 5489641, 5590621, 7177105, 9069229, 9073513, 9567673, 9995671, 10323769, 11473885, 12263131

Offset: 1

Shyam Sunder Gupta, Oct 20 2013

nonn

			4681 is a strong pseudoprime (base 2) and 4679 is prime.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..5001 from Shyam Sunder Gupta)

Cf. A001567, A001262, A230484, A230485, A230487.

cp's OEIS Frontend

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

A086249 Number of base-2 Fermat pseudoprimes x that have ord(2,x) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A122785 Nonprimes m such that 8^m == 8 (mod m).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Extensions

A175625 Numbers k such that gcd(k, 6) = 1, 2^(k-1) == 1 (mod k), and 2^(k-3) == 1 (mod (k-1)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A175738 Sizes of successive increasing gaps between 2-pseudoprimes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A176033 Numbers k such that 2^(2k-1) == 2 (mod 2k) and such that 2^(k-1) != 1 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A216170 Fermat pseudoprimes to base 2 of the form (n^2 + 2*n)/3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A225101 Numerator of (2^n - 2)/n.

Views

Author

Keywords

Comments