A006935 -id:A006935 - cp's OEIS frontend

A158358 Pseudoprimes to base 2 that are not squarefree, including the even pseudoprimes.

1194649, 12327121, 3914864773, 5654273717, 6523978189, 22178658685, 26092328809, 31310555641, 41747009305, 53053167441, 58706246509, 74795779241, 85667085141, 129816911251, 237865367741, 259621495381, 333967711897, 346157884801, 467032496113, 575310702877, 601401837037, 605767053061

Offset: 1

Rick L. Shepherd, Mar 16 2009

nonn

Intersection of (A001567 U A006935) and A013929. Also, intersection of A015919 and A013929.
The first six terms are given by Ribenboim, who references calculations by Lehmer and by Pomerance, Selfridge & Wagstaff supporting "that the only possible factors p^2 (where p is a prime less than 6*10^9) of any pseudoprime, must be 1093 or 3511." Ribenboim states that the first four terms are strong pseudoprimes. The first two terms are squares of these Wieferich primes, 1093^2 and 3511^2.
Only Wieferich primes (A001220) can appear with an exponent greater than one. In particular, all members of this sequence are divisible by a square of a Wieferich prime. Up to 67 * 10^14 the only Wieferich primes are 1093 and 3511. - Charles R Greathouse IV, Sep 12 2012
The first term divisible by the squares of two (Wieferich) primes is a(11870) = 4578627124156945861 = 29 * 71 * 151 * 1093^2 * 3511^2. See A219346. - Charles R Greathouse IV, Sep 20 2012
Unless there are other Wieferich primes besides 1093 and 3511, the sequence is the union of A247830 and A247831. - Max Alekseyev, Nov 26 2017
The even terms are listed in A295740. - Max Alekseyev, Nov 26 2017 [Their indices in this sequence are 2882, 3476, 3573, 4692, 5434, 5581, 6332, 8349, 8681, 9515, ... - Jianing Song, Feb 08 2019]

			a(6) = 22178658685 = 5 * 47 * 79 * 1093^2 is a pseudoprime that is not squarefree.

P. Ribenboim, The Little Book of Big Primes. Springer-Verlag, NY, 1991, pp. 77, 83, 167.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10010 (The even terms inserted by Jianing Song)
Jan Feitsma, W search: non-squarefree pseudoprimes
R. G. E. Pinch, The pseudoprimes up to 10^13, Lecture Notes in Computer Science, 1838 (2000), 459-473. - _Felix Fröhlich_, Apr 16 2014
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
Index entries for sequences related to pseudoprimes

Cf. A001567, A013929, A001220, A001262, A219346, A247830, A247831, A295740.

list(lim)=vecsort(concat(concat(apply(p->select(n->Mod(2, n)^(n-1)==1, p^2*vector(lim\p^2\2, i, 2*i-1)), [1093, 3511])), select(n->Mod(2, n)^n==2, 2*3511^2*vector(lim\3511^2\2, i, i))), , 8) \\ valid up to 4.489 * 10^31, Charles R Greathouse IV, Sep 12 2012, changed to include the even terms by Jianing Song, Feb 07 2019

More terms from Max Alekseyev, May 09 2010

Name changed by Jianing Song, Feb 07 2019 to include the even pseudoprimes to base 2 (A006935) as was suggested by Max Alekseyev.

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

A130421 Numbers k such that 4^k == 2 (mod k).

Original entry on oeis.org

1, 2, 14, 1022, 20066, 80519, 107663, 485918, 1284113, 1510313, 2531678, 3677198, 3933023, 4557713, 8277458, 8893262, 21122318, 24849833, 26358638, 39852014, 42448478, 71871113, 76712318, 80646143, 98058097, 104832833, 106694033, 131492498, 144322478, 146987033, 164360606, 168204191, 175126478, 176647378, 188997463, 196705598

Offset: 1

Jon E. Schoenfield, May 26 2007

nonn

Some terms above 10^15: 26435035805519327, 158975398896178078, 64044049390757098943, 1063423126446412987081943, 1091220919655042176978844783, 81074850280355100090334498663, 6317483763950169936179578094903, 5672799393875320397186007124651847, 170923900137537174138295268515194974, 195746953975871672436191077726091399305155458, 325665752547333314939363628501536024940097079718953, 953533053776414279913696071891872697927468471633033, 85791212788381063775490416118630897060666265030605503, 334519297382630382793758729321508383611586565722054114034741260213364710519401967713. - Max Alekseyev, Jun 18 2014

Max Alekseyev, Table of n, a(n) for n = 1..2617 (all terms below 10^15)

Cf. A006935 (odd terms times 2), A130422, A347906 (odd terms), A347908 (even terms).

Join[{1,2},Select[Range[107000000],PowerMod[4,#,#]==2&]] (* Harvey P. Dale, Jun 13 2013 *)

Terms a(28) onward from Max Alekseyev, Jun 18 2014

b-file corrected by Max Alekseyev, Oct 09 2016

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 *)

A247831 Pseudoprimes to base 2 divisible by 3511^2, including the even pseudoprimes.

Original entry on oeis.org

12327121, 129816911251, 259621495381, 346157884801, 605767053061, 6317168754781, 6922923480721, 12634325182441, 18518799663001, 21634109682121, 24273469559431, 57114029344321, 65681131896901, 102718706568661, 135083316211741, 135818875521811, 153342494379361

Offset: 1

Felix Fröhlich, Sep 24 2014

nonn

Numbers k such that 2^k == 2 (mod k) and k is divisible by 3511^2.

Unless there are other Wieferich primes (A001220) besides 1093 and 3511, the intersection and the union of this sequence with A247830 are given by A219346 and A158358, respectively, and the even terms are given by A295740. - Max Alekseyev, Nov 26 2017 [The indices of the even terms in this sequence are 430, 525, 543, 701, 811, 826, 937, 1235, 1277, 1388, ... - Jianing Song, Feb 08 2019]

Jianing Song, Table of n, a(n) for n = 1..1470
R. G. E. Pinch, The pseudoprimes up to 10^13, Lecture Notes in Computer Science, 1838 (2000), 459-473.
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.

Subsequence of each of (A001567 U A006935), A015919, A158358 composed of the terms divisible by 3511^2.

Cf. A001220, A013929, A219346, A247830, A295740.

vi=readvec("b158358.txt")
for(n=1, #vi, if(Mod(vi[n], 3511^2)==0, print1(vi[n], ", ")))

list(N)=select(k->Mod(2, k)^k==2, 3511^2*vector(N\3511^2\2, i, i)) \\ Jianing Song, Feb 07 2019

Name changed by Jianing Song, Feb 07 2019 to include the even pseudoprimes to base 2 (A006935) at the suggestion of Max Alekseyev.

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

Original entry on oeis.org

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

A347906 Numbers k such that 2^(2*k-1) == 1 (mod k).

Original entry on oeis.org

1, 80519, 107663, 1284113, 1510313, 3933023, 4557713, 24849833, 71871113, 80646143, 98058097, 104832833, 106694033, 146987033, 168204191, 188997463, 205428713, 332693873, 333681761, 336327863, 380284847, 533039513, 552913169, 711999113, 725943719, 805031663, 1000519033, 1069441313, 1476327353, 1610020913

Offset: 1

Jianing Song, Sep 18 2021

nonn

Odd numbers k such that ord(2,k) divides 2*k-1, where ord(2,k) is the multiplicative order of 2 modulo k.
Numbers k such that 2*k is in A006935. For k > 1, k is a term if and only if 2*k is an even pseudoprime to base 2.
Odd terms in A130421. Complement of A347908 in A130421.
Terms > 1 must be composite, since for odd primes p we have 2^(2*p-1) == 2 (mod p). If k > 1 is a term, then 2*k-1 must also be composite, since ord(2,k) | (2*k-1) and ord(2,k) <= eulerphi(k) <= k-1 < 2*k-1.
If k > 1 is a term, then (2^(2*k-1) - 1)/k is composite. Proof: since 2*k-1 is composite, write 2*k-1 = u*v, u >= v > 1, then (2^(2*k-1) - 1)/k = (2^u - 1)*(2^(u*(v-1)) + ... + 2^u + 1)/k. Since k | 2^(2*k-1) - 1, there exist positive integers a,b such that a*b = k and that a | 2^u - 1 and b | 2^(u*(v-1)) + ... + 2^u + 1. Note that (2^u - 1)/a, (2^(u*(v-1)) + ... + 2^u + 1)/b >= (2^u - 1)/k >= (2^sqrt(2*k-1) - 1)/k > 1, so (2^(2*k-1) - 1)/k is the product of two integers > 1, so it is composite.
2^t - 1 is a term if and only if 2^(t+1) == 3 (mod t) (t = 1, 111481, 465793, ... in A296370).

			80519 is a term since 80519 divides 2^161037 - 1 (the multiplicative order of 2 modulo 80519 is 261, which is a divisor of 161037). Note that 2 * 80519 = 161038 = A006935(2) is the smallest even pseudoprime to base 2.

Jianing Song, Table of n, a(n) for n = 1..1319 (contains all terms below 10^15; based on Max Alekseyev's b-file for A006935)

Cf. A006935, A130421, A347908, A296370.

Cf. A347907 (a similar sequence).

isA347906(k) = if(k%2 && !isprime(k), Mod(2, k)^(2*k-1)==1, 0)

a(n) = A006935(n)/2.

A296370 Numbers m such that 2^m == 3/2 (mod m).

Original entry on oeis.org

1, 111481, 465793, 79036177, 1781269903307, 250369632905747, 708229497085909, 15673900819204067

Offset: 1

Max Alekseyev, Dec 11 2017

Equivalently, 2^(m+1) == 3 (mod m).
Also, numbers m such that 2^(m+1) - 2 is a Fermat pseudoprime base 2, i.e., 2^(m+1) - 2 belongs to A015919 and A006935.
Some larger terms (may be not in order): 2338990834231272653581, 341569682872976768698011746141903924998969680637.

OEIS Wiki, 2^n mod n

Solutions to 2^m == k (mod m): this sequence (k=3/2), A187787 (k=1/2), A296369 (k=-1/2), A000079 (k=0), A006521 (k=-1), A015919 (k=2), A006517 (k=-2), A050259 (k=3), A015940 (k=-3), A015921 (k=4), A244673 (k=-4), A128121 (k=5), A245318 (k=-5), A128122 (k=6), A245728 (k=-6), A033981 (k=7), A240941 (k=-7), A015922 (k=8), A245319 (k=-8), A051447 (k=9), A240942 (k=-9), A128123 (k=10), A245594 (k=-10), A033982 (k=11), A128124 (k=12), A051446 (k=13), A128125 (k=14), A033983 (k=15), A015924 (k=16), A124974 (k=17), A128126 (k=18), A125000 (k=19), A015925 (k=2^5), A015926 (k=2^6), A015927 (k=2^7), A015929 (k=2^8), A015931 (k=2^9), A015932 (k=2^10), A015935 (k=2^11), A015937 (k=2^12)

Select[Range[10^6], Divisible[2^(# + 1) - 3, #] &] (* Robert Price, Oct 11 2018 *)

a(n) = A296104(n) - 1.

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 *)

A296104 Numbers k such that 2^k == 3 (mod k-1).

Original entry on oeis.org

2, 111482, 465794, 79036178, 1781269903308, 250369632905748, 708229497085910, 15673900819204068

Offset: 1

Krzysztof Ziemak and Max Alekseyev, Dec 04 2017

Also, numbers k such that 2^k - 2 is a Fermat pseudoprime, i.e., 2^k - 2 belongs to A015919 and A006935.
a(3) was found by McDaniel (1989).
Some larger terms (maybe not in order): 2338990834231272653582, 341569682872976768698011746141903924998969680638.
Discovered huge even PSP(2) numbers of the form 2*M(n), where n=p*q and M(n)=2^n-1, ensure that the following numbers are also even pseudoprimes of the form 2*M(p)*M(q): 2*M(37)*M(12589), 2*M(131)*M(17854891864360859951), 2*M(179)*M(1398713032993), 2*M(2111)*M(335494787819), 2*M(35267)*M(50508121). - Krzysztof Ziemak, Jan 01 2018

W. L. McDaniel, Some Pseudoprimes and Related Numbers Having Special Forms, Math. Comp. 53:187 (1989), 407-409.

Cf. A000079, A015919, A006935, A014741, A050259, A055685, A296370.

k = 2; lst = {2}; While[k < 1000000001, If[ PowerMod[2, k, k -1] == 3, AppendTo[lst, k]]; k += 10; If[ PowerMod[2, k, k -1] == 3, AppendTo[lst, k]]; k += 2]; lst (* Robert G. Wilson v, Jan 01 2018 *)

is_A296104(n) = Mod(2, n-1)^n == 3; \\ Iain Fox, Dec 07 2017

A296104_list = [n for n in range(2,10**6) if pow(2,n,n-1) == 3 % (n-1)] # Chai Wah Wu, Dec 06 2017

a(n) = A296370(n) + 1.

cp's OEIS Frontend

A158358 Pseudoprimes to base 2 that are not squarefree, including the even pseudoprimes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A130437 Even pseudoprimes to base 19.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A130421 Numbers k such that 4^k == 2 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A247831 Pseudoprimes to base 2 divisible by 3511^2, including the even pseudoprimes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Extensions

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

A347906 Numbers k such that 2^(2*k-1) == 1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A296370 Numbers m such that 2^m == 3/2 (mod m).

Views

Author

Keywords