A001567 -id:A001567 - cp's OEIS frontend

A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

683, 1123, 1291, 4931, 16963, 25603, 70667, 110491, 121403, 145771, 166667, 301703, 424843, 529547, 579883, 696323, 715523, 854467, 904103, 1112339, 1175723, 1234187, 1306667, 1444523, 2146043, 2651687, 2796203, 2882183, 3069083, 3216931, 4284283, 4325443

Offset: 1

Francois R. Grieu, Mar 05 2018

nonn

The definition's congruence is verified if n is a safe prime A005385 with m the corresponding Sophie Germain prime A005384; and for a few other n, which form the sequence.
If that congruence is verified and m is prime, then n is prime (follows from a result by Fedor Petrov).
That congruence is equivalent to the combination: 2^m == +-1 (mod n) and 2^m == 2 (mod m).
Composite n are Euler pseudoprimes A006970, and strong pseudoprimes A001262 if m is odd. The smallest is a(6534) = (2^47+1)/3 = 46912496118443 = 283*165768537521 (cf. A303448). See Peter Košinár link.
Even m belong to A006935. The first is a(986) = 252435584573, m = 126217792286 (cf. A303008).

			n = 683 = 2*341+1 is in the sequence because 2^341 == 2048 == 3*n-1 (mod 341*683) and m = 341 = 11*13 is composite.
n = 301703 = 2*150851+1 is in the sequence because 2^150851 == 301704 == n+1 (mod 150851*301703) and m = 150851 = 251*601 is composite.
n = 5 = 2*2+1 is not in the sequence because m = 2 is prime.

Francois R. Grieu, Table of n, a(n) for n = 1..2796 (terms <2^42).
Peter Košinár, Report of a composite n, Math StackExchange, Mar 06 2018.
Fedor Petrov, Proof that the congruence and m prime imply n prime, MathOverflow.

Cf. A005385, A005384, A000040, A001262, A001567, A006935, A006970.

For[m=1,(n=2m+1)<4444444,++m,If[MemberQ[{n+1,3n-1},PowerMod[2,m,m*n]] &&!PrimeQ[m], Print[n]]] (* Francois R. Grieu, Mar 19 2018 *)

isok(n) = {if ((n % 2) && (m=(n-1)/2) && !isprime(m), v = lift(Mod(2, m*n)^m); if ((v == n+1) || (v == 3*n-1), return (1));); return (0);} \\ Michel Marcus, Mar 06 2018

A062852 Largest n-digit strong pseudoprimes (in base 2).

Original entry on oeis.org

8321, 90751, 983401, 9995671, 99789673, 999828727, 9998721001, 99973476433, 999855751441, 9998974546471, 99999760517281, 999985147456681, 9999952887414577, 99999984319096601, 999999916795882627, 9999999995077192591

Offset: 4

Shyam Sunder Gupta, Feb 13 2002

			a(4)=8321 since 8321 is the largest 4-digit strong pseudoprime to base 2.

Patrick De Geest, Smallest n-digit pseudoprimes(base 2)
Index entries for sequences related to pseudoprimes

Cf. A001567, A068216, A067845, A001262, A062568.

Edited by Charles R Greathouse IV, Nov 01 2009

a(16)-a(19) from Charles R Greathouse IV, Mar 14 2011

A083739 Pseudoprimes to bases 2, 3, 5 and 7.

Original entry on oeis.org

29341, 46657, 75361, 115921, 162401, 252601, 294409, 314821, 334153, 340561, 399001, 410041, 488881, 512461, 530881, 552721, 658801, 721801, 852841, 1024651, 1152271, 1193221, 1461241, 1569457, 1615681, 1857241, 1909001, 2100901

Offset: 1

Serhat Sevki Dincer (sevki(AT)ug.bilkent.edu.tr), May 05 2003

nonn

			a(1)=29341 since it is the first number such that 2^(k-1) = 1 (mod k), 3^(k-1) = 1 (mod k), 5^(k-1) = 1 (mod k) and 7^(k-1) = 1 (mod k).

Amiram Eldar, Table of n, a(n) for n = 1..7469 (terms below 10^12; terms 1..114 from R. J. Mathar)
Jens Bernheiden, Pseudoprimes (in German).
Fred Richman, Primality testing with Fermat's little theorem.
Index entries for sequences related to pseudoprimes.

Cf. A001567, A005935, A005936, A005938.

Proper subset of A083737.

a001567 := [] : f := fopen("b001567.txt",READ) : bfil := readline(f) : while StringTools[WordCount](bfil) > 0 do if StringTools[FirstFromLeft]("#",bfil ) <> 0 then ; else bfil := sscanf(bfil,"%d %d") ; a001567 := [op(a001567), op(2,bfil) ] ; fi ; bfil := readline(f) ; od: fclose(f) : isPsp := proc(n,b) if n>3 and not isprime(n) and b^(n-1) mod n = 1 then true; else false; fi; end: isA001567 := proc(n) isPsp(n,2) ; end: isA005935 := proc(n) isPsp(n,3) ; end: isA005936 := proc(n) isPsp(n,5) ; end: isA005938 := proc(n) isPsp(n,7) ; end: isA083739 := proc(n) if isA001567(n) and isA005935(n) and isA005936(n) and isA005938(n) then true ; else false ; fi ; end: n := 1: for psp2 from 1 do i := op(psp2,a001567) ; if isA083739(i) then printf("%d %d ",n,i) ; n :=n+1 ; fi ; od: # R. J. Mathar, Feb 07 2008

Select[ Range[2113920], !PrimeQ[ # ] && PowerMod[2, # - 1, # ] == 1 && PowerMod[3, 1 - 1, # ] == 1 && PowerMod[5, # - 1, # ] == 1 && PowerMod[7, 1 - 1, # ] == 1 & ]

is(n)=!isprime(n)&&Mod(2,n)^(n-1)==1&&Mod(3,n)^(n-1)==1&&Mod(5,n)^(n-1)==1&&Mod(7,n)^(n-1)==1 \\ Charles R Greathouse IV, Apr 12 2012

a(n) = n-th positive integer k(>1) such that 2^(k-1) = 1 (mod k), 3^(k-1) = 1 (mod k), 5^(k-1) = 1 (mod k) and 7^(k-1) = 1 (mod k).

A005938 INTERSECT A083737. - R. J. Mathar, Feb 07 2008

Edited by Robert G. Wilson v, May 06 2003

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

A215672 Fermat pseudoprimes to base 2 with three prime factors.

Original entry on oeis.org

561, 645, 1105, 1729, 1905, 2465, 2821, 4371, 6601, 8481, 8911, 10585, 12801, 13741, 13981, 15841, 16705, 25761, 29341, 30121, 30889, 33153, 34945, 41665, 46657, 52633, 57421, 68101, 74665, 83665, 87249, 88561, 91001, 93961, 113201, 115921, 121465, 137149

Offset: 1

Marius Coman, Aug 20 2012

nonn

Fermat pseudoprimes to base 2 are also called Poulet numbers.
Most of the terms shown can be written in one of the following two ways:
  (1) p*(p*(n + 1) - n)*(p*(m + 1) - m);
  (2) p*(p*n - (n + 1))*(p*m - (m + 1)),
where p is the smallest of the three prime factors and n, m natural numbers.
Exempli gratia for Poulet numbers from the first category:
  10585 = 5*29*73 = 5*(5*7 - 6)*(5*18 - 17);
  13741 = 7*13*151 = 7*(7*2 - 1)*(7*25 - 24);
  13981 = 11*31*41 = 11*(11*3 - 2)*(11*4 - 3);
  29341 = 13*37*61 = 13*(13*3 - 2)*(13*5 - 4);
  137149 = 23*67*89 = 23*(23*3 - 2)*(23*4 - 3).
Exempli gratia for Poulet numbers from the second category:
  6601 = 7*23*41 = 7*(7*4 - 5)*(7*7 - 8).
Note: from the numbers from the sequence above, just the numbers 30889, 88561 and 91001 can't be written in one of the two ways.
What these three numbers have in common: they all have a prime divisor q of the form 30*k + 23 (i.e. 23, 53, 83) and can be written as q*((r + 1)*q - r), where r is a natural number.
Conjecture: Any Poulet number P with three or more prime divisors has at least one prime divisor q for that can be written as P = q*((r + 1)*q - r), where r is a natural number.
Note: it can be proved that a Carmichael number can be written this way for any of its prime divisors - see the sequence A213812.
Note: there are also many Poulet numbers with two prime divisors that can be written this way, but here are few exceptions: 7957, 23377, 42799, 49981, 60787.
The conjecture fails for a(80) = 617093 = 43 * 113 * 127. - Charles R Greathouse IV, Dec 07 2014
First differs from A074380 at n=56. - Amiram Eldar, Jun 28 2019

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Poulet Number
Eric Weisstein's World of Mathematics, Carmichael Number

The even terms form A296117.

Cf. A001567, A007304, A074380, A080747, A213812.

Select[Range[10^5], PrimeNu[#] == 3 && PowerMod[2, (# - 1), #] == 1 &] (* Amiram Eldar, Jun 28 2019 *)

is(n)=Mod(2,n)^n==2 && bigomega(n)==3 \\ Charles R Greathouse IV, Dec 07 2014

A242742 Let k be the n-th composite number: then a(n) is the smallest base b such that b^(k-1) == 1 (mod k).

Original entry on oeis.org

5, 7, 9, 8, 11, 13, 15, 4, 17, 19, 21, 8, 23, 25, 7, 27, 26, 9, 31, 33, 10, 35, 6, 37, 39, 14, 41, 43, 45, 8, 47, 49, 18, 51, 16, 9, 55, 21, 57, 20, 59, 61, 63, 8, 65, 8, 25, 69, 22, 11, 73, 75, 26, 45, 34, 79, 81, 80, 83, 85, 4, 87, 28, 89, 91, 3, 93, 32, 95

Offset: 1

Felix Fröhlich, Aug 16 2014

nonn

Felix Fröhlich, Table of n, a(n) for n = 1..8769 (all terms up to k=10^4)

Cf. A002808, A001567, A105222, A181780, A211455, A211456, A211457, A211458.

sbb[n_]:=Module[{b=2},While[PowerMod[b,n-1,n]!=1,b++];b]; sbb/@Select[ Range[ 100],CompositeQ] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Dec 29 2018 *)

forcomposite(k=2, 1e2, for(b=2, 1e9, if(Mod(b, k)^(k-1)==1, print1(b, ", "); next({2}))); print1(">1e9, "))

a(n) = A105222(A002808(n)). - Michel Marcus, Aug 21 2014

A270697 Composite numbers k == 3 (mod 4) such that (1 + i)^k == 1 - i (mod k), where i = sqrt(-1).

Original entry on oeis.org

2047, 42799, 90751, 256999, 271951, 476971, 514447, 741751, 877099, 916327, 1302451, 1325843, 1397419, 1441091, 1507963, 1530787, 1907851, 2004403, 2205967, 2304167, 2748023, 2811271, 2953711, 2976487, 3090091, 3116107, 4469471, 4863127, 5016191

Offset: 1

José María Grau Ribas, Mar 21 2016

nonn

Composite k == 3 (mod 4) such that 2*(-4)^((k-3)/4) == -1 (mod k). - Robert Israel, Mar 21 2016
2*(-4)^((p-3)/4) == -1 (mod p) is satisfied by all primes p == 3 (mod 4), see A318908. - Jianing Song, Sep 05 2018
Numbers in A047713 that are congruent to 3 mod 4. Most terms are congruent to 7 mod 8. For terms congruent to 3 mod 8, see A244628. - Jianing Song, Sep 05 2018
Question: Is this a subsequence of A001262? I have verified that it contains all terms up to 2^64. - Joseph M. Shunia, Jul 02 2019

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..111 from Jianing Song using data from A047713)

Subsequence of A001567 and A047713.
A244628 is a proper subsequence.
Cf. A001262, A006971, A270698, A318908.

select(t -> not isprime(t) and 1 + 2*(-4) &^ ((t-3)/4) mod t = 0, [seq(i, i=7..10^7, 4)]); # Robert Israel, Mar 21 2016

Select[3 + 4*Range[10000000], PrimeQ[#] == False && PowerMod[1 + I, #, #] == Mod[1 - I, #] &]

forstep(n=3, 10^7, 4, if(Mod(2, n)^((n-1)/2)==kronecker(2, n) && !isprime(n), print1(n, ", ")))

A298758 Numbers k such that both k and 2k-1 are Poulet numbers (Fermat pseudoprimes to base 2).

Original entry on oeis.org

15709, 65281, 20770621, 104484601, 112037185, 196049701, 425967301, 2593182901, 16923897871, 32548281361, 45812984491, 52035130951, 55897227751, 82907336737, 90003640021, 92010062101, 138016057141, 204082130071, 310026150211, 620006892121, 622333751509

Offset: 1

Amiram Eldar, Jan 26 2018

nonn

2*a(n) - 1 = A303531(n) belongs to A217465. - Max Alekseyev, Apr 24 2018
Numbers k such that both k and 2k+1 are Poulet numbers are listed in A303447.
If p is a prime such that 2*p-1 is also a prime (A005382) and k = (2^(2*p-1)+1)/3 and 2*k-1 are both composites, then k is a term of this sequence (Rotkiewicz, 2000). - Amiram Eldar, Nov 09 2023

Amiram Eldar, Table of n, a(n) for n = 1..3031 (terms below 2^64)
Andrzej Rotkiewicz, Arithmetic progressions formed by pseudoprimes, Acta Mathematica et Informatica Universitatis Ostraviensis, Vol. 8, No. 1 (2000), pp. 61-74.

Subsequence of A001567.

Cf. A005382, A217465, A303447, A303448.

s = Import["b001567.txt", "Data"][[All, -1]]; n = Length[s];
aQ[n_] := ! PrimeQ[n] && PowerMod[2, (n - 1), n] == 1;
a = {}; Do[p = 2*s[[k]] - 1; If[aQ[p], AppendTo[a, s[[k]]]], {k, 1, n}]; a (* using the b-File from A001567 *)

isP(n) = (Mod(2, n)^n==2) && !isprime(n) && (n>1);
isok(n) = isP(n) && isP(2*n-1); \\ Michel Marcus, Mar 09 2018

A020139 Pseudoprimes to base 11.

Original entry on oeis.org

10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 6601, 7869, 8113, 8170, 8695, 8911, 9730, 10585, 12403, 13333, 14521, 14981, 15841, 16705, 17711, 18705, 23377, 24130, 24727, 26335, 26467

Offset: 1

David W. Wilson

nonn

According to Karsten Meyer, May 16 2006, 10 should be excluded, following the strict definition in Crandall and Pomerance.

Composite numbers n such that 11^(n-1) == 1 (mod n).

R. Crandall and C. Pomerance, "Prime Numbers - A Computational Perspective", Second Edition, Springer Verlag 2005, ISBN 0-387-25282-7 Page 132 (Theorem 3.4.2. and Algorithm 3.4.3)
J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 190, p. 57, Ellipses, Paris 2008.

R. J. Mathar and T. D. Noe, Table of n, a(n) for n = 1..1000 (R. J. Mathar to 726 terms)
F. Richman, Primality testing with Fermat's little theorem
Index entries for sequences related to pseudoprimes

Cf. A001567 (pseudoprimes to base 2).

base = 11; t = {}; n = 1; While[Length[t] < 100, n++; If[! PrimeQ[n] && PowerMod[base, n-1, n] == 1, AppendTo[t, n]]]; t (* T. D. Noe, Feb 21 2012 *)

A066488 Composite numbers k which divide A001045(k-1).

Original entry on oeis.org

341, 1105, 1387, 1729, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4681, 5461, 6601, 7957, 8321, 8911, 10261, 10585, 11305, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18721, 19951, 23377, 29341, 30121, 30889, 31417, 31609, 31621, 34945

Offset: 1

Robert G. Wilson v, Jan 03 2002

Also composite numbers k such that (2^k - 2)/3 + 1 == 2^k - 1 == 1 (mod k).
An equivalent definition of this sequence: pseudoprimes to base 2 that are not divisible by 3. - Arkadiusz Wesolowski, Nov 15 2011
Conjecture: these are composites k such that 2^M(k-1) == -1 (mod M(k)^2 + M(k) + 1), where M(k) = 2^k - 1. - Amiram Eldar and Thomas Ordowski, Dec 19 2019
These are composites k such that 2^(m-1) == 1 (mod (m+1)^6 - 1), where m = 2^k - 1. - Thomas Ordowski, Sep 17 2023

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

Cf. A001567, A002808, A001045, A066047.

[k:k in [4..40000]|not IsPrime(k) and ((2^(k-1) + (-1)^k) div 3) mod k eq 0]; // Marius A. Burtea, Dec 20 2019

a[0] = 0; a[1] = 1; a[n_] := a[n] = a[n - 1] + 2a[n - 2]; Select[ Range[50000], IntegerQ[a[ # - 1]/ # ] && !PrimeQ[ # ] && # != 1 & ]
fQ[n_] := ! PrimeQ@ n && Mod[((2^n - 2)/3 + 1), n] == Mod[2^n - 1, n] == 1; Select[ Range@ 35000, fQ]

is(n)=n%3 && Mod(2,n)^(n-1)==1 && !isprime(n) && n>1 \\ Charles R Greathouse IV, Sep 18 2013

cp's OEIS Frontend

A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A062852 Largest n-digit strong pseudoprimes (in base 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A083739 Pseudoprimes to bases 2, 3, 5 and 7.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

A215672 Fermat pseudoprimes to base 2 with three prime factors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A242742 Let k be the n-th composite number: then a(n) is the smallest base b such that b^(k-1) == 1 (mod k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A270697 Composite numbers k == 3 (mod 4) such that (1 + i)^k == 1 - i (mod k), where i = sqrt(-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A298758 Numbers k such that both k and 2k-1 are Poulet numbers (Fermat pseudoprimes to base 2).

Views

Author

Keywords