A001567 -id:A001567 - cp's OEIS frontend

A062568 a(n) is the smallest n-digit strong pseudoprime (in base 2).

2047, 15841, 104653, 1004653, 10323769, 100463443, 1002261781, 10000321321, 100004790097, 1000002977551, 10000130243671, 100002236680837, 1000003918690669, 10000008250001701, 100000150553089531, 1000000274500018837, 10000003599249373469

Offset: 4

Shyam Sunder Gupta, Feb 13 2002

			a(1)=2047 because 2047 is the smallest 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, A062852.

Edited by Charles R Greathouse IV, Nov 01 2009

a(17)-a(20) from Charles R Greathouse IV, Mar 14 2011

A122781 Nonprimes n such that 4^n==4 (mod n).

Original entry on oeis.org

1, 4, 6, 12, 15, 28, 66, 85, 91, 186, 276, 341, 435, 451, 532, 561, 645, 703, 946, 1068, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2044, 2046, 2047, 2071, 2465, 2701, 2821, 2926, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795

Offset: 1

Farideh Firoozbakht, Sep 12 2006

If both numbers q and 2q-1 are prime, then q*(2q-1) is in the sequence. So, A005382(n)*(2*A005382(n)-1) = A129521(n) form a subsequence.

Vincenzo Librandi, Table of n, a(n) for n = 1..500

Contains A020136, A001567, A006935 (except n=2), and A129521 as subsequences.

Cf. A005382.

for n from 1 to 5000 do if 4^n mod n = 4 mod n and not isprime(n) then print(n) fi od; # Gary Detlefs, May 14 2012

Select[Range[4800], ! PrimeQ[ # ] && Mod[4^#, # ] == Mod[4, # ] &]
Join[{1,4},Select[Range[5000],!PrimeQ[#]&&PowerMod[4,#,#]==4&]] (* Harvey P. Dale, Apr 09 2018 *)

A240719 Numbers k such that 2^k == 1 (mod (k+1)^2).

Original entry on oeis.org

1092, 3510

Offset: 1

Felix Fröhlich, Apr 11 2014

There are only two known terms.
If p is in A001220, then p-1 is in the sequence. If k is in the sequence and k+1 is composite, then any prime factor of k+1 is in A001220 (see fifth comment for a proof). In that case, k+1 could be called a 'Wieferich pseudoprime'.
Any further terms are greater than 1.2 * 10^17. - Charles R Greathouse IV, Apr 12 2014
Both known terms have a periodic binary representation (i.e., 1092 = 010001000100, 3510 = 110110110110), so they are terms of A242139. Also, the ratio between those numbers and their divisor sums is 112/39 in both cases (see Dobson's website in the links and also A239875). Are those facts just coincidences? - Felix Fröhlich, Apr 15 2014
Proof of second part of second comment above: Let q be any odd prime factor of (k+1). Since 2 and q^2 are coprime, it follows from Euler's totient theorem (also known as Euler's theorem or Fermat-Euler theorem) that 2^(phi(q^2)) == 1 (mod q^2). Writing phi(q^2) = q^2 - q = q(q-1), one gets 2^(q(q-1)) == 1 (mod q^2). Taking the q-th root of both sides of the congruence yields 2^(q-1) == 1 (mod q^2). Q.E.D. - Felix Fröhlich, Jun 08 2015
If a(3) exists, it corresponds to A001220(3) - 1, i.e., a(3) + 1 must be prime. This can be shown the following way: Assume that a(3) + 1 is composite. Then the theorem from previous comment implies that a(3) + 1 is of the form 1093^x * 3511^y for some x, y >= 0 and x, y not both 0. If x or y is an integer k > 1, then p = 1093 or p = 3511 satisfies 2^(p-1) == 1 (mod p^(2k)). A quick check with PARI shows that neither 1093 nor 3511 satisfies this congruence for any k > 1. This leaves the case where x = y = 1, which can be excluded as well, since 3837523 is not in A001567. Q.E.D. - Felix Fröhlich, Jun 08 2015

J. Dobes and M. Kures, Search for Wieferich primes through the use of periodic binary strings, Serdica J. Computing, Volume 4, Number 3, 2010, 293-300.
J. B. Dobson, A note on the two known Wieferich primes
W. Johnson, On the nonvanishing of Fermat quotients (mod p), J. reine angew. Math., Issue 292 (Jan 1977), 196-200.
L. C. Washington, On Fermat's last theorem, J. reine angew. Math., Issue 289 (Jan 1977), 115-117.

Cf. A001220, A239875.

fQ[n_] := PowerMod[2, n, (n + 1)^2] == 1; Select[ Range@ 3600, fQ] (* Robert G. Wilson v, Jun 17 2015 *)

isok(n) = lift(Mod(2, (n+1)^2)^n) == 1; \\ Michel Marcus, Apr 12 2014

test(lim)=my(t=1); for(i=0, log(lim)\log(1093), my(n=t); while(n<=lim, if(Mod(2,n^2)^(n-1)==1&&n>1, print(n-1)); n*=3511); t*=1093)
test(1.2e17) \\ Test up to the current search bound for Wieferich primes; Charles R Greathouse IV, Apr 12 2014

A306310 Odd numbers k > 1 such that 2^((k-1)/2) == -(2/k) = -A091337(k) (mod k), where (2/k) is the Jacobi (or Kronecker) symbol.

Original entry on oeis.org

341, 5461, 10261, 15709, 31621, 49981, 65077, 83333, 137149, 176149, 194221, 215749, 219781, 276013, 282133, 534061, 587861, 611701, 653333, 657901, 665333, 688213, 710533, 722261, 738541, 742813, 769757, 950797, 1064053, 1073021, 1109461, 1141141, 1357621, 1398101

Offset: 1

Jianing Song, Feb 06 2019

nonn

All terms are composite because for odd primes p we always have 2^((p-1)/2) == (2/p) = A091337(p) (mod p).
Note that if k is odd and b^((k-1)/2) == -(b/k) (mod k), then taking Jacobi symbol modulo k (which depends only on the remainder modulo k) yields (b/k)^((k-1)/2) = -(b/k), or (b/k)^((k+1)/2) = -1. This implies that (k+1)/2 is odd, so k == 1 (mod 4). Moreover, if k > 1, then (b/k) = -1 (see the Math Stack Exchange link below), so b^((k-1)/2) == 1 (mod k). In particular, this sequence is equivalent to "numbers k == 5 (mod 8) such that 2^((k-1)/2) == 1 (mod k)". [Comment rewritten by Jianing Song, Sep 07 2024]
Also numbers k in A001567 and congruent to 5 modulo 8 such that k - 1 divided by the multiplicative order of 2 modulo k is an even number.
Euler pseudoprimes (A006970) that are not Euler-Jacobi pseudoprimes (A047713). - Amiram Eldar, Oct 28 2019

			341 is a term because (2/341) = -1, and 2^((341-1)/2) == 1 (mod 341).

Amiram Eldar, Table of n, a(n) for n = 1..1000
Mathematics Stack Exchange, There are no a in Z and odd k > 1 such that (a/k) = 1 and a^((k-1)/2) == -1 (mod k)

Cf. A091337, A001567, A007814.
                                   |        b=2        |   b=3   |   b=5   |
-----------------------------------+-------------------+---------+---------+
  (b/k)=1, b^((k-1)/2)==1 (mod k)  |      A006971      | A375917 | A375915 |
-----------------------------------+-------------------+---------+---------+
 (b/k)=-1, b^((k-1)/2)==-1 (mod k) | A244628 U A244626 | A375918 | A375916 |
-----------------------------------+-------------------+---------+---------+
 b^((k-1)/2)==-(b/k) (mod k), also |      this seq     | A375490 | A375816 |
 (b/k)=-1, b^((k-1)/2)==1 (mod k)  |                   |         |         |
-----------------------------------+-------------------+---------+---------+
     Euler-Jacobi pseudoprimes     |      A047713      | A048950 | A375914 |
       (union of first two)        |                   |         |         |
-----------------------------------+-------------------+---------+---------+
        Euler pseudoprimes         |      A006970      | A262051 | A262052 |
       (union of all three)        |                   |         |         |

isA306310(k)=(k%8==5) && Mod(2, k)^((k-1)/2)==1

isok(k) = (k>1) && (k%2) && (Mod(2, k)^((k-1)/2) == Mod(-kronecker(2, k), k)); \\ Michel Marcus, Feb 07 2019

A293623 Fermat pseudoprimes to base 2 that are pentagonal.

Original entry on oeis.org

7957, 241001, 1419607, 1830985, 1993537, 2134277, 2163001, 2491637, 2977217, 4864501, 5351537, 6952037, 10084177, 11367137, 11433301, 14609401, 21306157, 22591301, 26470501, 26977001, 29581501, 35851037, 44731051, 46517857, 53154337, 55318957, 55610837

Offset: 1

Amiram Eldar, Oct 13 2017

nonn

Rotkiewicz proved that this sequence is infinite.
Intersection of A001567 and A000326.
The corresponding indices of the pentagonal numbers are 73, 401, 973, 1105, 1153, 1193, 1201, 1289, 1409, 1801, 1889, 2153, 2593, 2753, 2761, ...

			7957 = (3*73^2 - 73)/2 is in the sequence since it is pentagonal, composite, and 2^7956 == 1 (mod 7957).

Andrzej Rotkiewicz, Sur les nombres pseudopremiers pentagonaux, Bull. Soc. Roy. Sci. Liège, Vol. 33 (1964), pp. 261-263.

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

Cf. A000326, A001567.

p[n_]:=(3n^2-n)/2; Select[p[Range[3, 10^4]], PowerMod[2, (# - 1), #]==1 &]

A293624 Fermat pseudoprimes to base 2 that are square pyramidal numbers.

Original entry on oeis.org

24301222105, 34200607741, 194305088689, 7362505969365, 19702357790989, 2985533798982149, 6091629437910701, 24781034010920641, 98129837465651129, 99860491537987361, 105697961209955269, 154533752639483489, 406611602100644641, 714567498159333701

Offset: 1

Amiram Eldar, Oct 13 2017

nonn

Rotkiewicz proved that under Schinzel's Hypothesis H this sequence is infinite.
Intersection of A001567 and A000330.
The corresponding indices of A000330 are 4177, 4681, 8353, 28057, 38953, 207673, 263401, 420481, 665233, 669121, 681913, 773953, ...

Amiram Eldar, Table of n, a(n) for n = 1..10000
Andrzej Rotkiewicz, On pyramidal numbers of order 4, Elemente der Mathematik, Vol. 28 (1973), pp. 14-16.
Wikipedia, Schinzel's Hypothesis H.

Cf. A000330, A001567, A293625.

p[n_]:=n(n+1)(2n+1)/6; Select[p[Range[3, 10^6]],PowerMod[2,(#-1),#] == 1 &]

A020137 Pseudoprimes to base 8.

Original entry on oeis.org

9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097

Offset: 1

David W. Wilson

nonn

This sequence is a subsequence of the sequence A122785. In fact the terms are odd composite terms of A122785. Theorem: If both numbers q and 2q-1 are primes (q is in the sequence A005382) and n=q*(2q-1) then 8^(n-1)==1 (mod n) (n is in the sequence) iff q is of the form 12k+1. 2701,18721,49141,104653,226801,665281,721801,... is the related subsequence. This subsequence is also a subsequence of the sequence A122785. - Farideh Firoozbakht, Sep 15 2006
Composite numbers k such that 8^(k-1) == 1 (mod k). - Michel Lagneau, Feb 18 2012
If q and 3q-2 are odd primes, then q*(3q-2) is in the sequence. - Davide Rotondo, May 25 2021

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..613 from R. J. Mathar, terms 614..1000 from T. D. Noe)
Index entries for sequences related to pseudoprimes

Cf. A001567 (pseudoprimes to base 2), A005382, A122783, A122785.

Select[Range[4100], ! PrimeQ[ # ] && PowerMod[8, (# - 1), # ] == 1 &] (* Farideh Firoozbakht, Sep 15 2006 *)

A067845 Largest n-digit pseudoprime (to base 2).

Original entry on oeis.org

645, 8911, 93961, 997633, 9995671, 99971821, 999828727, 9999109081, 99983971501, 999986341201, 9999946514845, 99999856404001, 999994510007533, 9999999191658001, 99999984319096601, 999999995115616561, 9999999995077192591

Offset: 3

Shyam Sunder Gupta, Feb 14 2002

			a(2)=8911, so largest pseudoprime (base 2) of 4 digits is 8911.

Patrick De Geest, Smallest n-digit Pseudoprimes
Index entries for sequences related to pseudoprimes

Cf. A001567, A068216, A001262, A062568, A062852.

More terms from Farideh Firoozbakht, Jan 11 2007

a(17)-a(19) from Amiram Eldar, Jun 30 2019

A084653 Pseudoprimes whose prime factors do not divide any smaller pseudoprime.

Original entry on oeis.org

341, 1387, 2047, 8321, 13747, 18721, 19951, 31621, 60701, 83333, 88357, 219781, 275887, 422659, 435671, 513629, 514447, 587861, 604117, 653333, 680627, 710533, 722261, 741751, 769757, 916327, 1194649, 1252697, 1293337, 1433407, 1441091

Offset: 1

T. D. Noe, Jun 02 2003

nonn

Here pseudoprime means a Fermat base-2 pseudoprime; sequence A001567, a composite number n such that n divides 2^(n-1) - 1. All numbers in this sequence seem to have only two prime factors - a conjecture that has been tested for all pseudoprimes < 10^15. The two prime factors are given in A084654 and A084655. The two prime factors are the same when the pseudoprime is the square of a Wieferich prime (A001220).

			a(2) = 1387 because 1387 = 19*73 and the smaller pseudoprimes (341, 561, 645, 1105) do not have the factors 19 or 73.

T. D. Noe, Table of n, a(n) for n = 1..10000
R. G. E. Pinch, Pseudoprimes and their factors (FTP)
Eric Weisstein's World of Mathematics, Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A001220, A001567, A084654, A084655.

A135590 Numbers k such that k^2 + 1 is a Sarrus number (pseudoprime to base 2).

Original entry on oeis.org

216, 948, 1560, 4872, 8208, 9828, 18200, 29640, 37024, 65536, 89550, 283800, 535920, 592956, 649800, 825930, 1042320, 1382400, 1536220, 3688230, 4215120, 4321800, 5103210, 19078930, 21415680, 24471720, 214067490, 435457620, 535019100

Offset: 1

Jason Earls, Feb 25 2008

nonn

Note that A000215(5) corresponds to a(10), and A000215(6) corresponds to a(33), and in general when A000215(n) is composite, this sequence has corresponding entry. - Jeppe Stig Nielsen, Mar 26 2016

Amiram Eldar, Table of n, a(n) for n = 1..40 (terms 1..33 from Jeppe Stig Nielsen)

Cf. A000215, A001567, A002522, A005574.

fQ[n_] := ( !PrimeQ[n^2 + 1] && PowerMod[2, n^2, n^2 + 1] == 1); lst = {}; Do[ If[ fQ@ n, AppendTo[lst, n]], {n, 2, 440000000, 2}]; lst (* Robert G. Wilson v, Apr 18 2008 *)

is(n) = {Mod(2, n)^(n-1)==1 && !ispseudoprime(n) && n > 1};
for(n=1, 1e10, if(is(n^2+1), print1(n, ", "))); \\ Altug Alkan, Mar 26 2016

More terms from Robert G. Wilson v, Apr 18 2008

cp's OEIS Frontend

A062568 a(n) is the smallest n-digit strong pseudoprime (in base 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A122781 Nonprimes n such that 4^n==4 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A240719 Numbers k such that 2^k == 1 (mod (k+1)^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A306310 Odd numbers k > 1 such that 2^((k-1)/2) == -(2/k) = -A091337(k) (mod k), where (2/k) is the Jacobi (or Kronecker) symbol.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

A293623 Fermat pseudoprimes to base 2 that are pentagonal.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A293624 Fermat pseudoprimes to base 2 that are square pyramidal numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A020137 Pseudoprimes to base 8.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A067845 Largest n-digit pseudoprime (to base 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A084653 Pseudoprimes whose prime factors do not divide any smaller pseudoprime.

Views