A001567 -id:A001567 - cp's OEIS frontend

A052155 Pseudoprimes to both base 2 and base 3, i.e., intersection of A001567 and A005935.

1105, 1729, 2465, 2701, 2821, 6601, 8911, 10585, 15841, 18721, 29341, 31621, 41041, 46657, 49141, 52633, 63973, 75361, 83333, 83665, 88561, 90751, 93961, 101101, 104653, 107185, 115921, 126217, 162401, 172081, 176149, 188461

Offset: 1

Harvey P. Dale, Jan 24 2000

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 201 terms from R. J. Mathar)
J. Bernheiden, Pseudoprimes (Text in German)
Index entries for sequences related to pseudoprimes

Cf. A001567, A005935, A083737.

Select[ Range[228240], !PrimeQ[ # ] && PowerMod[2, # - 1, # ] == 1 && PowerMod[3, # - 1, # ] == 1 &]

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

A153508 Sarrus numbers A001567 that are not Carmichael numbers A002997.

Original entry on oeis.org

341, 645, 1387, 1905, 2047, 2701, 3277, 4033, 4369, 4371, 4681, 5461, 7957, 8321, 8481, 10261, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 30121, 30889, 31417, 31609, 31621, 33153, 34945

Offset: 1

Artur Jasinski, Dec 28 2008

nonn

A composite number n is a Fermat pseudoprime to base b if and only if b^(n-1) == 1 (mod n). Fermat pseudoprimes to base 2 are sometimes called Poulet numbers, Sarrus numbers, or frequently just pseudoprimes. For any given base pseudoprimes will contain Carmichael numbers as a subset. This sequence consists of base-2 Fermat pseudoprimes without the Carmichael numbers.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..306 from Brad Clardy)

Cf. A001567, A002997.

for n:= 3 to 1052503 by 2 do
  if (IsOne(2^(n-1) mod n)
      and not IsPrime(n)
      and not n mod CarmichaelLambda(n) eq 1)
      then n;
      end if;
end for; // Brad Clardy, Dec 25 2014

filter:= proc(n)
local q;
   if isprime(n) then return false fi;
   if 2 &^(n-1) mod n <> 1 then return false fi;
   if not numtheory:-issqrfree(n) then return true fi;
   for q in numtheory:-factorset(n) do
     if (n-1) mod (q-1) <> 0 then return true fi;
   od:
   false
end proc:
select(filter, [$1..10^5]); # Robert Israel, Dec 29 2014

Select[Range[3, 35000, 2], !PrimeQ[#] && PowerMod[2, # - 1, # ] == 1 && !Divisible[# - 1, CarmichaelLambda[#]] &] (* Amiram Eldar, Jun 25 2019 *)

A303448 Numbers m such that both m and (m-1)/2 are Fermat pseudoprimes base 2 (A001567).

Original entry on oeis.org

19781763, 46912496118443, 192153584101141163

Offset: 1

Max Alekseyev, Apr 24 2018

No other terms below 2^65.
Terms a(2) and a(3) are of the form (2^(2k+1)+1)/3 = A007583(k).
Terms A007583(k) belong to this sequence for k in A303009. Correspondingly, a(4) <= A007583(A303009(3)) = (2^83+1)/3 = 3223802185639011132549803.
If a(n) is not divisible by 3, then it also belongs to A175625.

Numbers (a(n)-1)/2 are listed in A303447.
Subsequence of A006970 and A300193.
Cf. A175625, A175942, A298758.

a(n) = 2*A303447(n) + 1.

a(1) from Amiram Eldar, Jan 26 2018

A303009 Numbers n such that both A002450(n)=(2^(2n)-1)/3 and A007583(n)=2*A002450(n)+1 are Fermat pseudoprimes to base 2 (A001567).

Original entry on oeis.org

23, 29, 41, 53, 89, 113, 131, 179, 191, 233, 239, 251, 281, 293, 341, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, 1013, 1019, 1031, 1049, 1103, 1223, 1229, 1271, 1289, 1409, 1439, 1451, 1481, 1499, 1511, 1559, 1583, 1601, 1733, 1811, 1889, 1901, 1931, 1973, 2003

Offset: 1

Max Alekseyev, Apr 23 2018

nonn

It can be shown that if n is odd, it is a prime or a Fermat 4-pseudoprime (A020136) not divisible by 3. Similarly, 2n+1 is a prime or a Fermat 2-pseudoprime (A001567) not divisible by 3. In fact, the sequence is the union of the following six:
(i) primes n such that 2n+1 is prime (cf. A005384) and A007583(n) is composite, with smallest such term n=a(1)=23;
(ii) primes n==2 (mod 3) such that 2n+1 is a 2-psp (no such terms are known);
(iii) 4-pseudoprimes n==5 (mod 6) such that 2n+1 is prime and A007583(n) is composite, with smallest such term n=a(15)=341;
(iv) 4-pseudoprimes n==5 (mod 6) such that 2n+1 is 2-pseudoprime, with smallest such term n=268435455;
(v) n=2k, where 4k is in A015921 and k==1 (mod 3), such that 2n+1 is prime and A007583(n) is composite, with the smallest such term n=67166;
(vi) n=2k, where 4k is in A015921 and k==1 (mod 3), such that 2n+1 is a 2-psp, with the smallest such term n=9042986.

Cf. A002450, A007583, A175625, A175942, A300193, A303008, A303447, A303448.

Edited by Max Alekseyev, Aug 08 2019

A303447 Numbers m such that both m and 2m+1 are Fermat pseudoprimes base 2 (A001567).

Original entry on oeis.org

9890881, 23456248059221, 96076792050570581

Offset: 1

Max Alekseyev, Apr 24 2018

No other terms below 2^64.

Terms a(2) and a(3) are of the form (4^k-1)/3=A002450(k). Terms A002450(k) belong to this sequence for k in A303009. Correspondingly, a(4) <= A002450(A303009(3)) = (4^41-1)/3 = 1611901092819505566274901.

Numbers 2*a(n)+1 are listed in A303448.
Subsequence of A006970.
Cf. A298758, A300193.

a(1) from Amiram Eldar, Jan 26 2018

A055550 Number of Poulet numbers (or pseudoprimes to base 2, A001567) less than 10^n.

Original entry on oeis.org

0, 0, 3, 22, 78, 245, 750, 2057, 5597, 14884, 38975, 101629, 264239, 687007, 1801533, 4744920, 12604009, 33763684, 91210364

Offset: 1

Eric W. Weisstein

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 245, pp 68, Ellipses, Paris 2008. - Lekraj Beedassy, Jul 20 2008
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 219.

Jan Feitsma and William Galway, Tables of pseudoprimes and related data.
Eric Weisstein's World of Mathematics, Poulet Number.
Eric Weisstein's World of Mathematics, Pseudoprime.

Cf. A001567, A055552.

Table[Count[Select[Range[2, 10^6], ! PrimeQ[#] && PowerMod[2, # - 1, #] == 1 &], x_ /; x < 10^n], {n, 6}]  (* Robert Price, Jun 09 2019 *)

a(14) and a(15) computed by William F. Galway and communicated by Arthur Livingstone (arthur.livingstone(AT)gmail.com), Apr 10 2007
Edited by N. J. A. Sloane, Feb 01 2009 at the suggestion of Charles R Greathouse IV
a(14)-a(15) recomputed (were missing) and a(16)-a(19) added by Charles R Greathouse IV, Jan 28 2011, based on the calculations of Jan Feitsma

A300101 a(n) = (pp-1)/x, where pp = A001567(n) and x = ord(2,pp), the smallest positive integer such that 2^x == 1 (mod pp).

Original entry on oeis.org

34, 14, 23, 46, 77, 48, 68, 186, 44, 75, 47, 117, 112, 273, 19, 312, 390, 10, 221, 160, 106, 45, 342, 42, 157, 64, 229, 237, 699, 345, 714, 352, 348, 668, 195, 285, 575, 487, 56, 163, 502, 9, 357, 439, 310, 296, 208, 803, 151, 684, 217, 2038, 324, 315, 1666, 344, 1973, 319, 607, 2763, 62, 1777, 1122, 1360, 1135, 2603

Offset: 1

Jonas Kaiser, Feb 24 2018

nonn

For primes, this definition has a clear distribution over the natural numbers (see A001917), whereas there is no such distribution for pseudoprimes. Among the first 10^6 pseudoprimes of this sequence, the smallest number is 9. Are there any numbers in this sequence which are smaller than 9?

There is no value smaller than 9 for all the pseudoprimes below 2^64. - Amiram Eldar, Nov 09 2023

Amiram Eldar, Table of n, a(n) for n = 1..10000
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A001917, A001567, A306413, A174590.

((# - 1)/MultiplicativeOrder[2, #]) & /@ Select[Range[10^5], CompositeQ[#] && PowerMod[2, # - 1, #] == 1 &] (* Amiram Eldar, Nov 09 2023 *)

is_A001567(n)={Mod(2, n)^n==2 & !isprime(n) & n>1};
lista(nn) = {for (n=1, nn, if (is_A001567(n), print1((n-1)/znorder(Mod(2, n)), ", ");););} \\ Michel Marcus, Feb 25 2018

a(n) = (A001567(n) - 1) / A306413(n). - Jianing Song, Dec 12 2021

A306413 a(n) is the multiplicative order of 2 modulo A001567(n).

Original entry on oeis.org

10, 40, 28, 24, 18, 36, 28, 11, 56, 36, 60, 28, 36, 16, 230, 15, 14, 660, 36, 52, 80, 198, 30, 252, 72, 200, 60, 58, 20, 42, 22, 45, 48, 28, 96, 70, 40, 48, 460, 180, 60, 3432, 88, 72, 102, 112, 168, 44, 264, 60, 192, 21, 144, 156, 30, 153, 28, 180, 100, 22, 1012, 36, 58, 48, 60, 28, 612, 120, 60, 166, 1008, 52, 532, 148, 9840

Offset: 1

Jianing Song, Feb 13 2019

nonn

By definition, A001567 lists the odd composite numbers k such that ord(2,k) divides k - 1, where ord(2,k) is the multiplicative order of 2 modulo k. This sequence lists the values for ord(2,k) when k runs through A001567.

			A001567(1) = 341, 341 divides 2^10 - 1, 341 = 34*10 + 1.
A001567(2) = 561, 561 divides 2^40 - 1, 561 = 14*40 + 1.
A001567(3) = 645, 645 divides 2^28 - 1, 645 = 23*28 + 1.
A001567(4) = 1105, 1105 divides 2^24 - 1, 1105 = 46*24 + 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A001567, A002326, A300101, A306413.

MultiplicativeOrder[2, #] & /@ Select[Range[1, 10^5, 2], CompositeQ[#] && PowerMod[2, # - 1, #] == 1 &] (* Amiram Eldar, Jun 29 2019 *)

forstep(n=3, 1e5, 2, my(m=znorder(Mod(2,n))); if((n-1)%m==0 && !isprime(n), print1(m, ", ")))

a(n) = A002326((A001567(n)-1)/2).

a(n) = (A001567(n) - 1) / A300101(n). - Jianing Song, Dec 12 2021

A087716 Base-2 pseudoprimes (see A001567) of the form jp(i)# - p(k) or jp(i)# + p(k), p(i) and p(k) primes with p(i) < p(k) < p(i+1)^2 and 0 < j < p(i+1).

Original entry on oeis.org

341, 1387, 2047, 4681, 13747

Offset: 1

Pierre CAMI, Sep 29 2003

Conjecture: sequence has only 5 terms. This has been checked for all i <= 150.

			   2*7#  -  79 =   341,
   7*7#  -  83 =  1387,
  10*7#  -  53 =  2047,
   2*11# +  61 =  4681,
   6*11# - 113 = 13747,
  13*7#  -  29 =  2701.

Index entries for sequences related to pseudoprimes

Cf. A001567, A087714, A087715, A087728.

# denotes primorials; see A002110.

lst(lim)=my(p=2,P=1,v=List());forprime(q=3,lim,P*=p;forprime(r=q, q^2, for(j=1,q-1,if(j*P-r>340&&psp(j*P-r),listput(v,j*P-r)); if(psp(j*P+r),listput(v,j*P+r))));p=q);vecsort(Vec(v),,8) \\ Charles R Greathouse IV, Apr 12 2012

Edited by David Wasserman, Apr 13 2006

A141216 a(n) = A137576((N-1)/2) - N, where N = A001567(n).

Original entry on oeis.org

30, 320, 224, 240, 72, 360, 728, 0, 672, 216, 1320, 0, 0, 16, 5060, 60, 126, 10560, 216, 0, 3360, 2574, 150, 5040, 2808, 3600, 3600, 232, 400, 420, 22, 2700, 2784, 224, 96, 70, 1640, 240, 9200, 3600, 2760, 58344, 616, 504, 102, 5600, 8064, 264, 11880, 1440, 7488, 252

Offset: 1

Vladimir Shevelev, Jun 14 2008, Jul 13 2008

nonn

The zero terms are of a special interest. Indeed, since for any odd prime p, A137576((p-1)/2)=p, then it is natural to call "overpseudoprimes" those Poulet pseudoprimes A001567(n) for which a(n)=0.
Theorem. A squarefree composite number m = p_1*p_2*...*p_k is an overpseudoprime if and only if A002326((p_1-1)/2) = A002326((p_2-1)/2) = ... = A002326((p_k-1)/2). Moreover, every overpseudoprime is in A001262.
Note that in A001262 there exist terms which are not squarefree. The first is A001262(52) = 1194649 = 1093^2.
It can be shown that if an overpseudoprime is not a multiple of the square of a Wieferich prime (see A001220) then it is squarefree. Also all squares of Wieferich primes are overpseudoprimes.

Amiram Eldar, Table of n, a(n) for n = 1..10000
V. Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich Primes, arxiv:0806.3412 [math.NT], 2008-2012.

Cf. A137576, A001567, A001262, A002326, A006694.

fppQ[n_]:=PowerMod[2,n,n]==2;f[n_] := (t = MultiplicativeOrder[2, 2n+1])*DivisorSum[2n+1, EulerPhi[#] / MultiplicativeOrder[2, #]&]-t+1; s={}; Do[If[fppQ[n] && CompositeQ[n],AppendTo[s,f[(n-1)/2 ]-n]],{n,1,10000}]; s (* Amiram Eldar, Dec 09 2018 after Jean-François Alcover at A137576 *)

f(n) = my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1; \\ A137576
isfpp(n) = {Mod(2, n)^n==2 & !isprime(n) & n>1}; \\ A001567
lista(nn) = {for (n=1, nn, if (isfpp(n), print1(f((n-1)/2) - n, ", ");););} \\ Michel Marcus, Dec 09 2018

More terms via b137576.txt from R. J. Mathar, Jun 12 2010

More terms from Michel Marcus, Dec 09 2018

cp's OEIS Frontend

A052155 Pseudoprimes to both base 2 and base 3, i.e., intersection of A001567 and A005935.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A153508 Sarrus numbers A001567 that are not Carmichael numbers A002997.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

A303448 Numbers m such that both m and (m-1)/2 are Fermat pseudoprimes base 2 (A001567).

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A303009 Numbers n such that both A002450(n)=(2^(2n)-1)/3 and A007583(n)=2*A002450(n)+1 are Fermat pseudoprimes to base 2 (A001567).

Views

Author

Keywords

Comments

Crossrefs

Extensions

A303447 Numbers m such that both m and 2m+1 are Fermat pseudoprimes base 2 (A001567).

Views

Author

Keywords

Comments

Crossrefs

Extensions

A055550 Number of Poulet numbers (or pseudoprimes to base 2, A001567) less than 10^n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Extensions

A300101 a(n) = (pp-1)/x, where pp = A001567(n) and x = ord(2,pp), the smallest positive integer such that 2^x == 1 (mod pp).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A306413 a(n) is the multiplicative order of 2 modulo A001567(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A087716 Base-2 pseudoprimes (see A001567) of the form j*p(i)# - p(k) or j*p(i)# + p(k), p(i) and p(k) primes with p(i) < p(k) < p(i+1)^2 and 0 < j < p(i+1).

Views

Author

Keywords

A087716 Base-2 pseudoprimes (see A001567) of the form jp(i)# - p(k) or jp(i)# + p(k), p(i) and p(k) primes with p(i) < p(k) < p(i+1)^2 and 0 < j < p(i+1).