A130433 -id:A130433 - cp's OEIS frontend

A130441 Even pseudoprimes to base 37.

4, 6, 12, 18, 28, 36, 66, 246, 268, 396, 1476, 1876, 2044, 2556, 2706, 3556, 5986, 9514, 11034, 16236, 17466, 25626, 31956, 34716, 120786, 149076, 153756, 246484, 259588, 281886, 283276, 483636, 552926, 559966, 623566, 670186, 721846, 846076, 1050666

Offset: 1

Alexander Adamchuk, May 26 2007

nonn

Amiram Eldar, Table of n, a(n) for n = 1..548 (terms below 10^11; terms 1..243 from Robert G. Wilson v)
Eric Weisstein's World of Mathematics, Fermat Pseudoprime.
Index entries for sequences related to pseudoprimes.

Cf. A020165, A006935, A130433, A090082, A090083, A090084, A090085, A130434, A130435, A130436, A130437, A130438, A130439, A130440, A130442, A130443.

Do[ f=PowerMod[ 37, 2n-1, 2n ]; If[ f==1, Print[ 2n ] ], {n,2,500000} ]
lst = {}; Do[ If[ PowerMod[37, 2n - 1, 2n] == 1, AppendTo[lst, 2n]], {n, 2, 2^31}]; lst (* Robert G. Wilson v, Jun 01 2007 *)

is(k) = k > 2 && !(k % 2) &&  Mod(37, k)^(k-1) == 1; \\ Amiram Eldar, Sep 29 2024

A130437 Even pseudoprimes to base 19.

Original entry on oeis.org

6, 18, 906, 5466, 257302, 825366, 1880082, 6637546, 6765826, 8936722, 9483706, 34087054, 51914026, 54806454, 57663334, 57819882, 67372378, 91835206, 98963734, 102985926, 117697186, 134457346, 143888806, 172530646, 206623266

Offset: 1

Alexander Adamchuk, May 26 2007

nonn

Amiram Eldar, Table of n, a(n) for n = 1..145 (terms below 10^11; terms 1..51 from Robert G. Wilson v)
Eric Weisstein's World of Mathematics, Fermat Pseudoprime.
Index entries for sequences related to pseudoprimes.

Cf. A020147 = Pseudoprimes to base 19. Cf. A006935 = Even pseudoprimes (or primes) to base 2: n divides 2^n - 2, n even. Cf. A130433 = Even pseudoprimes to base 3. Cf. A090082 = Even pseudoprimes to base 5. Cf. A090083, A090084, A090085. Cf. A130434, A130435, A130436, A130438, A130439, A130440, A130441, A130442, A130443.

Cf. A020147, A006935, A130433, A090082, A090083, A090084, A090085, A130434, A130435, A130436, A130438, A130439, A130440, A130441, A130442, A130443.

lst = {}; Do[ If[ PowerMod[19, 2n - 1, 2n] == 1, AppendTo[lst, 2n]], {n, 2, 2*10^9}]; lst (* Robert G. Wilson v, Jun 01 2007 *)

is(k) = k > 2 && !(k % 2) &&  Mod(19, k)^(k-1) == 1; \\ Amiram Eldar, Sep 29 2024

More terms from Robert G. Wilson v, Jun 01 2007

A108162 Least even pseudoprime > p to base p, where p = prime(n).

Original entry on oeis.org

161038, 286, 124, 16806, 70, 244, 1228, 906, 154, 52, 66, 66, 344, 526974, 506, 286, 946, 130, 154, 370, 276, 2626, 1558, 19126, 176, 190, 946, 742, 186, 176, 3486, 190, 148, 246, 412, 10930, 186, 186, 3818, 14444, 1246, 316, 286, 276, 532, 426, 310, 246

Offset: 1

Alexander Adamchuk, May 26 2007

nonn

Some numbers appear as a multiple terms in a(n). For example, a(n) = 946 for n = {17,27,64,66,73,75,97,113,114,117,128,139,143,152,153,155} for corresponding prime p = {59,103,311,317,367,379,509,617,619,643,719,797,823,881,883,907}. There are some twin terms such that a(n) = a(n+1). For example, a(11) = a(12) = 66, a(37) = a(38) = 186, a(113) = a(114) = 946, a(152) = a(153) = 946, a(227) = a(228) = 2626.

The indices of records are 1, 14, 354, 549, 1302, 2679, 3743, 3998, 4627, 6880, ... with record values of 161038, 526974, 1234806, 1893126, 1930546, 3347398, 3860962, 5073706, 6376126, 61161946, ... - Amiram Eldar, Sep 10 2019

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Fermat Pseudoprime.
Index entries for sequences related to pseudoprimes

Cf. A006935 (Even pseudoprimes (or primes) to base 2: n divides 2^n - 2, n even).

Cf. A130433, A090082, A130434, A090084, A130435, A130436, A130437, A130438, A130439, A130440, A130441, A130442, A130443.

a[n_] := Module[{p = Prime[n]}, k = p+1; If[OddQ[k], k++]; While[GCD[p, k] != 1 || PowerMod[p, k, k] != p, k+=2]; k]; Array[a, 100] (* Amiram Eldar, Sep 10 2019 *)

A253233 Smallest even pseudoprime (>2n+1) in base 2n+1.

Original entry on oeis.org

4, 286, 124, 16806, 28, 70, 244, 742, 1228, 906, 1852, 154, 28, 286, 52, 66, 496, 442, 66, 1834, 344, 526974, 76, 506, 66, 70, 286, 1266, 2296, 946, 130, 5662, 112, 154, 14246, 370, 276, 8614, 2806, 2626, 112, 1558, 276, 2626, 19126, 1446, 322, 658, 176, 742, 190, 946, 5356, 742, 186, 190, 176, 8474, 2806, 2242, 148

Offset: 0

Eric Chen, May 17 2015

nonn

For an even base there are no even pseudoprimes.
Conjecture: There are infinitely many even pseudoprimes in every odd base.
Records: 4, 286, 16806, 526974, 815866, 838246, ..., and they occur at indices: 0, 1, 3, 21, 503, 691, ...

Eric Chen, Table of n, a(n) for n = 0..999 (a(0) corrected by _Georg Fischer_, Jan 20 2019)
Eric Weisstein's World of Mathematics, Fermat pseudoprime
Wikipedia, Fermat pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A005097, A090082, A090083, A090084, A090085, A090086, A090087, A090088, A090089, A108162, A130433, A130434, A130435, A130436, A130437, A130438, A130439, A130440, A139441, A130442, A130443, A007535.

f[n_] := Block[{k = 2 * n + 2}, While[PrimeQ[k] || OddQ[k] || PowerMod[2 * n + 1, k - 1, k] != 1, k++ ]; k]; Table[ f[n], {n, 0, 60}]

a(n) = for(k=n+1, 2^24, if(!isprime(2*k) && Mod(2*n+1, 2*k)^(2*k-1) == Mod(1, 2*k), return(2*k)))

a(A005097(n-1)) = A108162(n).

A363215 Integers p > 1 such that 3^d == 1 (mod p) where d = A000265(p-1).

Original entry on oeis.org

2, 11, 13, 23, 47, 59, 71, 83, 107, 109, 121, 131, 167, 179, 181, 191, 227, 229, 239, 251, 263, 277, 286, 311, 313, 347, 359, 383, 419, 421, 431, 433, 443, 467, 479, 491, 503, 541, 563, 587, 599, 601, 647, 659, 683, 709, 719, 733, 743, 757, 827, 829, 839, 863

Offset: 1

Jeppe Stig Nielsen, May 21 2023

nonn

Inspired by an incorrect definition of strong pseudoprime to base 3.

As is obvious from the data, it fails to include all primes. Does include some composite numbers (pseudoprimes), namely 121, 286, 24046, 47197, 82513, ...

Jeppe Stig Nielsen, Table of n, a(n) for n = 1..10000
Wikipedia, Strong pseudoprime

Cf. A000265, A005935, A020229, A130433.

is(p)=my(d=p-1);d/=2^valuation(d,2);Mod(3,p)^d==1

from itertools import count, islice
def inA363215(n): return pow(3,n-1>>(~(n-1)&n-2).bit_length(),n)==1
def A363215_gen(startvalue=2): # generator of terms >= startvalue
    return filter(inA363215,count(max(startvalue,2)))
A363215_list = list(islice(A363215_gen(),20)) # Chai Wah Wu, May 22 2023

A385073 a(n) = b^(n-1) mod n, where b = A053669(n) is the least integer greater than 1 and coprime to n.

Original entry on oeis.org

0, 1, 1, 3, 1, 5, 1, 3, 4, 3, 1, 5, 1, 3, 4, 11, 1, 11, 1, 7, 4, 3, 1, 5, 16, 3, 13, 27, 1, 7, 1, 11, 4, 3, 9, 29, 1, 3, 4, 27, 1, 17, 1, 27, 31, 3, 1, 29, 15, 33, 4, 27, 1, 11, 49, 3, 4, 3, 1, 43, 1, 3, 4, 43, 16, 23, 1, 27, 4, 13, 1, 29, 1, 3, 34, 27, 9, 5, 1, 27, 40, 3, 1, 17

Offset: 1

Robert G. Wilson v, Jun 16 2025

Inspired by Fermat's Little Theorem.

a(n) > 0 for n > 1 since n and b are coprime.

Wikipedia, Fermat's little theorem

Cf. A053669, A385074.

f:= proc(n) local b;
  b:= 2;
  while n mod b = 0 do b:= nextprime(b) od;
  b &^ (n-1) mod n
end proc:
f(1):= 0:
map(f, [$1..100]); # Robert Israel, Jun 18 2025

a[n_] := Block[{b = 2}, While[GCD[n, b] > 1, b++]; PowerMod[b, n - 1, n]]; Array[a, 84]

a(n) = forprime(p=2, , if(n%p, return(lift(Mod(p, n)^(n-1))))); \\ Michel Marcus, Jun 18 2025

a(n) = 0 iff n = 1.
a(n) = 1 iff n belongs to A000040, A001567, or A130433.
a(n) = 2 iff n>1 and belongs to A173572;
a(n) = 4 iff n belongs to A033553;
a(n) = 8 iff n>7 and belongs to either A033984 or A173138;
a(n) = 16 iff n>15 and belongs to A276968;
a(n) = 32 iff n>1 and belongs to A215610;
a(n) = 64 iff n>63 and belongs to A276969;
a(n) = 128 iff n>127 and belongs to A215611;
a(n) = 256 iff n>255 and belongs to A276970;
a(n) = 512 iff n>511 and belongs to A215612;
a(n) = 1024 iff n>1023 and belongs to A276971;
a(n) = 2048 iff n>2047 and belongs to A215613;
From Robert Israel, Jun 18 2025: (Start)
a(2*p) = 3 if p is a prime > 3.
a(3*p) = 4 if p is a prime > 2.
a(4*p) = 3^3 if p is a prime > 5.
a(6*p) = 5^5 if p is a prime > 509.
a(8*p) = 3^5 if p is a prime > 271.
a(10*p) = 3^9 if p is a prime > 1951.
a(12*p) = 5^11 if p is a prime > 4069003. (End)

A306144 Numbers k > 2 such that 3^(k-1) == 1 (mod k) and gcd(k, 2^(k-1)-1) = 1.

Original entry on oeis.org

286, 16531, 24046, 49051, 72041, 182527, 192713, 232726, 258017, 327781, 442471, 443713, 453259, 574397, 625873, 652879, 655051, 668431, 705091, 903631, 1236031, 1241143, 1250833, 1287091, 1304446, 1309111, 1351601, 1414639, 1563151, 1817743, 1899451, 1908397

Offset: 1

Thomas Ordowski, Aug 18 2018

nonn

The odd terms are "anti-Carmichael pseudoprimes (3,2)" defined as follows: numbers k > 1 such that 3^k == 3 (mod k) and gcd(k, 2^k-2) = 1. Cf. A300762 (2,3).

We impose k>2, since we want these to be pseudoprimes, thus composite numbers.

Subsequence of A005935.

Cf. A130433.

Select[Range[3, 2*10^6], PowerMod[3, #-1, #] == 1 && GCD[#, #-1 + PowerMod[2, #-1, #]] == 1 &] (* Giovanni Resta, Aug 18 2018 *)

isok(k) = (k>2) && (Mod(3, k)^(k-1) == Mod(1, k)) && (gcd(k, 2^(k-1)-1) == 1); \\ Michel Marcus, Aug 18 2018

More terms from Michel Marcus, Aug 18 2018

Further terms from Giovanni Resta, Aug 18 2018

cp's OEIS Frontend

A130441 Even pseudoprimes to base 37.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A130437 Even pseudoprimes to base 19.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A108162 Least even pseudoprime > p to base p, where p = prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A253233 Smallest even pseudoprime (>2n+1) in base 2n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A363215 Integers p > 1 such that 3^d == 1 (mod p) where d = A000265(p-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

A385073 a(n) = b^(n-1) mod n, where b = A053669(n) is the least integer greater than 1 and coprime to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A306144 Numbers k > 2 such that 3^(k-1) == 1 (mod k) and gcd(k, 2^(k-1)-1) = 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions