A006935 -id:A006935 - cp's OEIS frontend

A287297 Fermat pseudoprimes n such that n+1 is prime.

161038, 9115426, 143742226, 665387746, 1105826338, 3434672242, 11675882626, 16732427362, 18411253246, 81473324626, 85898088046, 98730252226, 134744844466, 136767694402, 161097973246, 183689075122, 315554044786, 553588254766, 778581406786, 1077392692846

Offset: 1

Amiram Eldar, May 26 2017

nonn

Kazimierz Szymiczek asked about the existence of such pseudoprimes in 1972 (Problem 42 in Rotkiewicz's book). Rotkiewicz found the first 6 terms. Rotkiewicz also proved that there is no Fermat pseudoprime n such that n-1 is prime.

Subsequence of A006935.

			161038 is in the sequence since it is a Fermat pseudoprime (2^161038 == 2 (mod 161038)), and 161038 + 1 = 161039 is prime.

Andrzej Rotkiewicz, Pseudoprime Numbers and Their Generalizations, Student Association of the Faculty of Sciences, University of Novi Sad, Novi Sad, Yugoslavia, 1972.

Amiram Eldar, Table of n, a(n) for n = 1..165
Andrzej Rotkiewicz, On pseudoprimes having special forms and a solution of K. Szymiczek's problem, Acta Mathematica Universitatis Ostraviensis, Vol. 13, No. 1 (2005), pp. 57-71.

Cf. A001567, A006935, A057942.

A290542 a(n) is the least integer k in the interval [2, sqrt(n)] such that k^n == k (mod n), or 0 if no such integer exists.

Original entry on oeis.org

0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 4, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 5, 3, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 4, 0, 0, 0, 2, 0

Offset: 4

Arkadiusz Wesolowski, Aug 05 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 4..20000

Cf. A010051, A290543.

lst:=[]; for n in [4..90] do r:=Floor(Sqrt(n)); for k in [2..r] do if Modexp(k, n, n) eq k then Append(~lst, k); break; end if; if k eq r then Append(~lst, 0); end if; end for; end for; lst;

Table[SelectFirst[Range[2, Sqrt@ n], PowerMod[#, n , n] == Mod[#, n] &] /. k_ /; MissingQ@ k -> 0, {n, 4, 90}] (* Michael De Vlieger, Aug 09 2017 *)

a(n) = for (k=2, sqrtint(n), if (Mod(k, n)^n == k, return(k));); return (0); \\ Michel Marcus, Aug 19 2017

a(A000040(n)) = 2 for n >= 3.
a(A001567(n)) = 2 for n >= 1.
a(A006935(n)) = 2 for n >= 2.
For n >= 3, a(x) = 2*A010051(x), where x = A000040(n).

A290543 Composite numbers n such that A290542(n) >= 2.

Original entry on oeis.org

28, 65, 66, 85, 91, 105, 117, 121, 124, 133, 145, 153, 154, 165, 185, 186, 190, 205, 217, 221, 231, 244, 246, 247, 259, 273, 276, 280, 286, 292, 301, 305, 310, 325, 341, 343, 344, 357, 364, 366, 369, 370, 377, 385, 396, 418, 425, 427, 429, 430, 435, 451

Offset: 1

Arkadiusz Wesolowski, Aug 05 2017

nonn

Is a(n) ~ n * log n as n -> infinity?

Cf. A001567, A006935, A122780, A122781, A122782, A122783, A122784, A122785, A122786, A290542.

lst:=[]; for n in [4..451] do if not IsPrime(n) then r:=Floor(Sqrt(n)); for k in [2..r] do if Modexp(k, n, n) eq k then Append(~lst, n); break; end if; end for; end if; end for; lst;

Select[Flatten@ Position[#, k_ /; k >= 2], CompositeQ] &@ Table[SelectFirst[Range[2, Sqrt@ n], PowerMod[#, n , n] == Mod[#, n] &], {n, 451}] (* Michael De Vlieger, Aug 09 2017 *)

A306451 Non-coprime pseudoprimes or primes to base 3: numbers k that are multiples of 3 and are such that k divides 3^k - 3.

Original entry on oeis.org

3, 6, 66, 561, 726, 7107, 8205, 8646, 62745, 100101, 140097, 166521, 237381, 237945, 566805, 656601, 876129, 1053426, 1095186, 1194285, 1234806, 1590513, 1598871, 1938021, 2381259, 2518041, 3426081, 4125441, 5398401, 5454681, 5489121, 5720331, 5961441

Offset: 1

Jianing Song, Feb 17 2019

nonn

Union of {3} and (A122780 - {1} - A005935).
Numbers of the form 3*m such that 3^(3*m-1) == 1 (mod m).
The squarefree terms are listed in A306450.

Jianing Song, Table of n, a(n) for n = 1..163 (all terms below 10^9)

Cf. A005935, A006935, A122780, A306450.

A258801 is a subsequence.

forstep(n=3, 1e7, 3, if(Mod(3, n)^n==3, print1(n, ", ")))

66 is a term because 66 divides 3^66 - 3 = 3*(3^65 - 1) = 3*(3^5 - 1)*(3^60 + 3^55 + ... + 3^5 + 1) and 66 is divisible by 3.

A091669 a(n) = (2^(n-1)/n!) * Product_{k=1..n-1} (2^k-1).

Original entry on oeis.org

1, 1, 2, 7, 42, 434, 7812, 248031, 14055090, 1436430198, 267176016828, 91151551074486, 57425477176926180, 67196011936600334340, 146782968474309770332296, 601204690999713530559792879

Offset: 1

Karol A. Penson, Jan 27 2004

nonn

Primes p such that 2^p-2 divides a(p) are A216838. - Amiram Eldar and Thomas Ordowski, Jan 16 2020
For odd n > 1, if a(n-1) divides a(n) and n does not divide a(n), then n is a prime (for which 2 is a primitive root, A001122). Composite numbers m such that a(m-1) divides a(m) are the pseudoprimes A001567 and A006935. Numbers n > 1 such that a(m) divides a(n) for all m < n are primes 2, 3, 5, 7, and 13. These are the primes p for which gpf(2^p-2) = p. - Thomas Ordowski, Jan 17 2020
If p is a prime with primitive root 2, A001122, then p | a(p-1) + 2^(p-2). Conjecture: (for n > 2), if n | a(n-1) + 2^(n-2), then n is a prime (A001122). Note that if p is an odd prime for which 2 is not a primitive root, A216838, then p | a(p-1). - Amiram Eldar and Thomas Ordowski, Jan 19 2020

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

Cf. A000142, A001122, A001567, A005329, A006935, A159353, A216838, A225101.

[1] cat [2^(n-1)/Factorial(n)*&*[(2^k-1):k in [1..n-1]]:n in [2..16]]; // Marius A. Burtea, Jan 16 2020

seq( (2^(n-1)/n!)*mul(2^j-1, j=1..n-1), n=1..20); # G. C. Greubel, Feb 05 2020

Table[QFactorial[n-1, 2] 2^(n-1)/n!, {n, 20}]

a(n) = (2^(n-1)/n!) * prod(k=1, n-1, 2^k-1); \\ Michel Marcus, Jan 16 2020

from sage.combinat.q_analogues import q_factorial
[2^(n-1)*q_factorial(n-1, 2)/factorial(n) for n in (1..20)] # G. C. Greubel, Feb 05 2020

a(n) = 2^(n-1)*A005329(n-1)/n!.

a(n) = Product_{k=2..n} (2^k-2)/k = Product_{k=2..n} A225101(k)/A159353(k). - Thomas Ordowski, Jan 16 2020

Corrected and edited by Thomas Ordowski, Jan 16 2020

A271669 Smallest k > n such that n divides k and n^k == n (mod k).

Original entry on oeis.org

2, 161038, 6, 12, 10, 30, 14, 56, 18, 30, 22, 132, 26, 182, 30, 48, 34, 306, 38, 380, 42, 66, 46, 552, 50, 130, 54, 84, 58, 870, 62, 992, 66, 102, 70, 180, 74, 1406, 78, 120, 82, 1722, 86, 1892, 90, 138, 94, 2256, 98, 350, 102, 156, 106, 2862, 110, 280, 114, 174, 118, 3540

Offset: 1

Thomas Ordowski, Apr 12 2016

nonn

			Because of the definition of (pseudo)primes to base 2, a(2) is the least element of A006935 greater than 2. - _Altug Alkan_, Apr 12 2016

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

Cf. A006935, A102457.

Table[SelectFirst[Range[n + 1, 10^6], Function[k, Divisible[k, n] && PowerMod[n, k, k] == Mod[n, k]]], {n, 60}] (* Michael De Vlieger, Apr 12 2016, Version 10 *)
skn[n_]:=Module[{k=2n},While[PowerMod[n,k,k]!=n,k=k+n];k]; Array[skn,60] (* Harvey P. Dale, Jan 20 2025 *)

a(n) = {k = n+1; while( !(((k % n)==0) && (Mod(n,k)^k == Mod(n, k))), k++); k;} \\ Michel Marcus, Apr 12 2016

a(n) = 2n for odd n. - Robert Israel, Apr 12 2016

a(n) = n * A102457(n) for n > 1. - Thomas Ordowski, Apr 13 2016

More terms from Michel Marcus, Apr 12 2016

A296117 Base-2 pseudoprimes of the form 2pq where p and q are primes.

Original entry on oeis.org

161038, 49699666, 760569694, 4338249646, 357647681422, 547551530002, 3299605275646, 22999986587854, 42820164121582, 55173914702146, 69345154539266, 353190859033982

Offset: 1

Max Alekseyev, Dec 05 2017

a(5) and a(10) are found by McDaniel (1989).

Terms in this sequence are of the form 2pq where p and q are distinct odd primes (A075819). - Charles R Greathouse IV, Dec 05 2017

W. L. McDaniel, Some pseudoprimes and related numbers having special forms, Math. Comp. 53:187 (1989), 407-409.

Subsequence of A006935 and hence of A015919.
The even terms of A215672.
Intersection of A006935 and A215672. - Felix Fröhlich, Dec 05 2017
Cf. A270973, A075819, A001220.

list(lim)=my(v=List(),pq); forprime(p=3,lim\6, forprime(q=3,min(lim\(2*p),p), pq=p*q; if(Mod(4,pq)^pq==2, listput(v,2*pq)))); Set(v) \\ Charles R Greathouse IV, Dec 05 2017

A306487 Poulet numbers which are not super-Poulet numbers.

Original entry on oeis.org

561, 645, 1105, 1729, 1905, 2465, 2821, 4371, 6601, 8481, 8911, 10585, 11305, 12801, 13741, 13981, 15841, 16705, 18705, 23001, 25761, 29341, 30121, 30889, 33153, 34945, 39865, 41041, 41665, 46657, 52633, 55245, 57421, 62745, 63973, 68101, 72885, 74665, 75361

Offset: 1

Amiram Eldar, Feb 18 2019

nonn

Subsequence of A080747 from which this differs for the first time at n=78, with A080747(78) = 294409, a term not present here.
Is this sequence infinite?
According to Sierpinski there are infinitely many Poulet numbers which are not super-Poulet numbers. But his definition of Poulet numbers includes the even pseudoprimes to base 2 (A006935), and the proof is based on the infinitude of this sequence and that super-Poulet numbers are never even.

			561 is in the sequence because 2^561 % 561 == 2 but 33|561 and 2^33 % 33 = 8 <> 2. - _David A. Corneth_, Feb 28 2019

W. Sierpinski, Elementary Theory of Numbers, ed. A. Schinzel, North-Holland Mathematical Library (2nd ed.), Amsterdam: North Holland, 1988, Chapter V, p. 234, Exercise 1.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Poulet Number
Eric Weisstein's World of Mathematics, Super-Poulet Numbers
Wikipedia, Super-Poulet number

Cf. A001567, A050217, A006935, A080747.

Cf. A215672 (differs from a(13) = 11305 on, which is not in A215672).

Select[Select[Range[3, 100000, 2], !PrimeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &], Union[PowerMod[2, Rest[Divisors[#]], #]] != {2}& ]

is_A001567(n) = {Mod(2, n)^(n-1)==1 && !isprime(n) && n>1}; \\ From A001567 by M. F. Hasler
is_A050217(n) = if(isprime(n), 0, fordiv(n, d, if(Mod(2, d)^d!=2, return(0))); (n>1)); \\ After Charles R Greathouse IV's Aug 27 2016 PARI-program in A050217.
is_A306487(n) = (is_A001567(n) && !is_A050217(n)); \\ (Probably could be reduced to a simpler program). - Antti Karttunen, Feb 28 2019

is(n) = {if(isprime(n) || n < 2 || n%2 == 0, return(0)); if(Mod(2, n)^n!=2, return(0) , d = divisors(n); for(i = 1, #d-1, if(Mod(2, d[i])^d[i]!=2, return(1) ) ) ); 0 } \\ David A. Corneth, Feb 28 2019

cp's OEIS Frontend

A287297 Fermat pseudoprimes n such that n+1 is prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A290542 a(n) is the least integer k in the interval [2, sqrt(n)] such that k^n == k (mod n), or 0 if no such integer exists.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A290543 Composite numbers n such that A290542(n) >= 2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Mathematica

A306451 Non-coprime pseudoprimes or primes to base 3: numbers k that are multiples of 3 and are such that k divides 3^k - 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A091669 a(n) = (2^(n-1)/n!) * Product_{k=1..n-1} (2^k-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A271669 Smallest k > n such that n divides k and n^k == n (mod k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A296117 Base-2 pseudoprimes of the form 2*p*q where p and q are primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A306487 Poulet numbers which are not super-Poulet numbers.

Views

Author

Keywords

A296117 Base-2 pseudoprimes of the form 2pq where p and q are primes.