A244626 -id:A244626 - cp's OEIS frontend

A375918 Composite numbers k == 5, 7 (mod 12) such that 3^((k-1)/2) == -1 (mod k).

703, 1891, 3281, 8911, 12403, 16531, 44287, 63139, 79003, 97567, 105163, 152551, 182527, 188191, 211411, 218791, 288163, 313447, 320167, 364231, 385003, 432821, 453259, 497503, 563347, 638731, 655051, 658711, 801139, 859951, 867043, 973241, 994507, 1024651, 1097227

Offset: 1

Jianing Song, Sep 02 2024

nonn

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

			3281 is a term because 3281 = 17*193 is composite, 3281 == 5 (mod 12), and 3^((3281-1)/2) == -1 (mod 3281).

Jianing Song, Table of n, a(n) for n = 1..1000

                                   |        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 | this seq | A375916 |
-----------------------------------+-------------------+----------+---------+
 b^((k-1)/2)==-(b/k) (mod k), also |      A306310      | 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)        |                   |          |         |

isA375918(k) = !isprime(k) && (k%12==5 || k%12==7) && Mod(3,k)^((k-1)/2) == -1

A293394 Numbers k such that (2k-1)(2^((k-1)/4)) == 1 (mod k).

Original entry on oeis.org

1, 17, 41, 97, 137, 193, 241, 313, 401, 409, 433, 449, 457, 521, 569, 641, 673, 761, 769, 809, 857, 929, 953, 977, 1009, 1129, 1297, 1321, 1361, 1409, 1489, 1657, 1697, 1873, 1993, 2017, 2081, 2137, 2153, 2161

Offset: 1

Jonas Kaiser, Nov 09 2017

nonn

It appears that many elements of this sequence are prime. The first "pseudoprime" in this sequence is 74665.

Charles R Greathouse IV, 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. A001133, A244626, A294717.

Select[Range[1, 3001, 4], #==1 || Mod[-PowerMod[#-2, (#-1)/4, #], #]==1&] (* Jean-François Alcover, Nov 18 2018 *)

is(n)=n%4==1 && (2*n-1)*Mod(2,n)^(n>>2)==1 \\ Charles R Greathouse IV, Nov 09 2017

A294717 Numbers k such that 2^((k-1)/3) == 1 (mod k) and (2k-1)(2^((k-1)/6)) == 1 (mod k).

Original entry on oeis.org

1, 43, 109, 157, 229, 277, 283, 307, 397, 499, 643, 691, 733, 739, 811, 997, 1021, 1051, 1069, 1093, 1459, 1579, 1597, 1627, 1699, 1723, 1789, 1933, 2179, 2203, 2251, 2341, 2347, 2731, 2749, 2917, 2971, 3061, 3163, 3181, 3229, 3259, 3277, 3331, 3373, 3541, 4027

Offset: 1

Jonas Kaiser, Nov 07 2017

nonn

Most of the elements of this sequence are prime. The "pseudoprimes" of these sequence are part of A244626.

Charles R Greathouse IV, 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. A001133, A244626.

Select[Range[1, 6001, 6], # == 1 || PowerMod[2, (#-1)/3, #] == 1 && Mod[-PowerMod[2, (#-1)/6, #], #] == 1&] (* Jean-François Alcover, Nov 18 2018 *)

is(n)=n%6==1 && Mod(2,n)^(n\3)==1 && (2*n-1)*Mod(2,n)^(n\6)==1 \\ Charles R Greathouse IV, Nov 08 2017

A270698 Composite numbers k == 1 (mod 4) such that (1 + i)^k == 1 + i (mod k), where i = sqrt(-1).

Original entry on oeis.org

561, 1105, 1729, 1905, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, 12801, 15841, 16705, 18705, 25761, 29341, 30121, 33153, 34945, 41041, 46657, 49141, 52633, 62745, 65281, 74665, 75361, 80581, 85489, 87249, 88357, 104653, 113201, 115921, 126217, 129921

Offset: 1

José María Grau Ribas, Mar 21 2016

nonn

From Jianing Song, Sep 05 2018: (Start)
Numbers in A047713 that are congruent to 1 mod 4. Most terms are congruent to 1 mod 8. For terms congruent to 5 mod 8, see A244626.
Also composite k == 1 (mod 4) such that (-4)^((k-1)/4) == 1 (mod k). Note that this is satisfied by all primes == 1 (mod 4), see A318898. (End)

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..889 from Jianing Song using data from A047713)

Subsequence of A001567 and A047713.
A244626 is a proper subsequence.
Cf. A006971, A270697, A318898.

Select[1 + 4*Range[100000], PrimeQ[#] == False && PowerMod[1 + I, #, #] == 1 + I &]

forstep(n=5, 10^5, 4, if(Mod(2, n)^((n-1)/2)==kronecker(2, n) && !isprime(n), print1(n, ", "))) \\ Jianing Song, Sep 06 2018

A294912 Numbers n such that 2^(n-1), (2n-1)(2^((n-1)/2)), (4ceiling((3/4)n)-2), and (2^((n+1)/2) + floor((1/4)n)2^(((n+1)/2)+1)) are all congruent to 1 (mod n).

Original entry on oeis.org

3, 11, 19, 43, 59, 67, 83, 107, 131, 139, 163, 179, 211, 227, 251, 283, 307, 331, 347, 379, 419, 443, 467, 491, 499, 523, 547, 563, 571, 587, 619, 643, 659, 683, 691, 739, 787, 811, 827, 859, 883, 907, 947, 971, 1019, 1051, 1091, 1123, 1163, 1171, 1187, 1259

Offset: 1

Jonas Kaiser, Nov 10 2017

nonn

It appears that A007520 is a subsequence.
The first composite term is a(9969) = 476971 = 11*131*331. - Alois P. Heinz, Nov 10 2017
From Hilko Koning, Dec 03 2019: (Start)
The next composite terms < 1999979 are
a(17428) = 877099  = 307*2857
a(25090) = 1302451 = 571*2281
a(25518) = 1325843 = 499*2657
a(26785) = 1397419 = 67*20857
a(27549) = 1441091 = 347*4153
a(28715) = 1507963 = 971*1553
a(29117) = 1530787 = 619*2473
a(35635) = 1907851 = 11*251*691
(End)
From Hilko Koning, Dec 05 2019: (Start)
The next composite terms < 24999971 are
a(37344) = 2004403 = 307*6529
a(55773) = 3090091 = 1163*2657
a(56189) = 3116107 = 883*3529
a(91332) = 5256091 = 811*6481
a(102027) = 5919187 = 1777*3331
a(133230) = 7883731 = 811*9721
a(156407) = 9371251 = 1531*6121
a(182911) = 11081459 = 227*48817
a(189922) = 11541307 = 1699*6793
a(201043) = 12263131 = 811*15121
a(213203) = 13057787 = 467*27961
a(217484) = 13338371 = 3163*4217
a(257526) = 15976747 = 3739*4273
a(274961) = 17134043 = 1097*15619
a(299096) = 18740971 = 1531*12241
a(308928) = 19404139 = 2011*9649
a(321676) = 20261251 = 2251*9001
a(341902) = 21623659 = 1163*18593
a(348622) = 22075579 = 163*135433
a(380162) = 24214051 = 281*86171
The composite terms < 25*10^6 match the terms of A244628.
(End)
It appears that composites of the form 2k+1 such that 3*(2k+1) divides 2^k+1 are the composite terms of this sequence. - Hilko Koning, Dec 09 2019

Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A244626, A294717, A293394, A070179, A007520.

okQ[n_] := AllTrue[{2^(n-1), (2*n-1)*(2^((n-1)/2)), (4*Ceiling@((3/4)*n) - 2), (2^((n+1)/2) + Floor@(n/4)*2^(((n+1)/2)+1))}, Mod[#, n] == 1&];
Select[Range[1300], okQ] (* Jean-François Alcover, Feb 18 2019 *)

isok(n) = (n%2) && lift((Mod(2, n)^(n-1))==1)&&lift((Mod((2*n-1), n)*Mod(2, n)^((n-1)/2)) == 1)&&lift((Mod(((4*ceil((3/4)*n)-2)), n) )== 1)&&lift((Mod(2, n)^((n+1)/2) +Mod(floor((1/4)*n),n)*Mod(2, n)^(((n+1)/2)+1 ))== 1)

More terms from Alois P. Heinz, Nov 10 2017

A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).

Original entry on oeis.org

3277, 3281, 29341, 49141, 80581, 88357, 104653, 121463, 196093, 314821, 320167, 458989, 476971, 489997, 491209, 721801, 800605, 838861, 873181, 877099, 973241, 1004653, 1251949, 1268551, 1302451, 1325843, 1373653, 1397419, 1441091, 1507963, 1509709, 1530787, 1590751, 1678541, 1809697

Offset: 1

Thomas Ordowski, Apr 27 2019

nonn

As is well known, for an odd prime p, b(p) is the smallest quadratic non-residue b modulo p if and only if b(p) is the smallest base b such that b^((p-1)/2) == -1 (mod p). Note that b(n) is always a prime.
Conjecture: If 2^((n-1)/2) == -1 (mod n), then b(n) = 2, where b(n) as above. This is true for odd primes n; is it for odd composites n? If so, then all composite numbers n such that 2^((n-1)/2) == -1 (mod n) are in this sequence.
It seems that, for defined pseudoprimes n (similar to the odd primes p),
b(n) is the smallest base b such that b^((n-1)/2) == -1 (mod n), although this is not required by their definition.
Note: a "non-residue" pseudoprime n is a strong pseudoprime to base b(n); the Jacobi symbol (b(n)/n) = -1, where b(n) is the smallest non-residue modulo n; such a pseudoprime n is not a Proth number, so n = k*2^m + 1 with odd k > 2^m.
Problem: are there infinitely many such numbers?

			2^((3277-1)/2) == -1 (mod 3277), 3^((3281-1)/2) == -1 (mod 3281), ...

Cf. A001262, A006970, A020649, A047713, A053760, A244626, A307798 (the "residue" pseudoprimes), A307809.

residueQ[n_, m_] := Module[{ans = 0}, Do[If[Mod[k^2, m] == n, ans = True; Break[]], {k, 0, Floor[m/2]}]; ans]; A020649[n_] := Module[{m = 0}, While[ residueQ[m, n], m++]; m]; aQ[n_] := CompositeQ[n] && PowerMod[A020649[n], ((n - 1)/2), n] == n - 1; Select[Range[3, 110000, 2], aQ] (* Amiram Eldar, Apr 27 2019 *)

More terms from Amiram Eldar, Apr 27 2019

A307798 The "residue" pseudoprimes: odd composite numbers n such that q(n)^((n-1)/2) == 1 (mod n), where base q(n) is the smallest prime quadratic residue modulo n.

Original entry on oeis.org

121, 561, 1105, 1541, 1729, 1905, 2465, 4033, 5611, 8321, 8481, 10585, 15709, 15841, 16297, 18705, 18721, 19345, 25761, 28009, 29341, 30121, 31697, 33153, 34945, 42799, 44173, 46657, 49141, 52633, 55969, 62745, 63973, 65077, 69781, 75361, 76627, 79381, 82513, 85489, 88573, 90241, 102311

Offset: 1

Thomas Ordowski, Apr 29 2019

nonn

As is well known, for an odd prime p, a prime q is a quadratic residue modulo p if and only if q^((p-1)/2) == 1 (mod p). Hence the above definition of these pseudoprimes.
Such pseudoprimes n which are both "residue" and "non-residue", obviously to different bases q(n) and b(n), are particularly interesting: 29341, 49141, 1251949, 1373653, 2284453, ... These five numbers are in A244626.
Note that the absolute Euler pseudoprimes are odd composite numbers n such that b^((n-1)/2) == 1 (mod n) for every base b that is a quadratic residue modulo n and coprime to n. There are no odd composite numbers n such that b^((n-1)/2) == -1 (mod n) for every base b that is a quadratic non-residue modulo n and coprime to n. The absolute Euler-Jacobi pseudoprimes do not exist.

			3^((121-1)/2) == 1 (mod 121), 2^((561-1)/2) == 1 (mod 561), ...

Cf. A002997, A033181, A306530, A307767 (the "non-residue" pseudoprimes).

q[n_] := Module[{p = 2, pn = Prime[n]}, While[JacobiSymbol[p, pn] != 1, p = NextPrime[p]]; p]; aQ[n_] := CompositeQ[n] && PowerMod[q[n], (n - 1)/2, n] == 1; Select[Range[3, 110000, 2], aQ] (* Amiram Eldar, Apr 29 2019 *)

More terms from Amiram Eldar, Apr 29 2019

A294919 Numbers n such that 2^(n-1), (2n-1)(2^((n-1)/2)), (4ceiling((1/4)n)-2), and (2^((n+1)/2) + floor((3/4)n)2^(((n+1)/2)+1)) are all congruent to 1 (mod n).

Original entry on oeis.org

5, 13, 29, 37, 53, 61, 101, 109, 149, 157, 173, 181, 197, 229, 269, 277, 293, 317, 349, 373, 389, 397, 421, 461, 509, 541, 557, 613, 653, 661, 677, 701, 709, 733, 757, 773, 797, 821, 829, 853, 877, 941, 997, 1013, 1021, 1061, 1069, 1093, 1109, 1117, 1181, 1213

Offset: 1

Jonas Kaiser, Nov 10 2017

nonn

It appears that A007521 is a subsequence.

a(118) = 3277 = 29*113 is the first nonprime term.

Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A007521, A070179, A244626, A293394, A294717.

okQ[n_] := AllTrue[{2^(n-1), (2*n-1)*(2^((n-1)/2)), (4*Ceiling@(n/4) - 2), (2^((n+1)/2) + Floor@((3/4)*n)*2^(((n+1)/2) + 1))}, Mod[#, n] == 1&];
Select[Range[1300], okQ] (* Jean-François Alcover, Feb 18 2019 *)

isok(n) = (n%2) && lift((Mod(2, n)^(n-1))==1)&&lift((Mod((2*n-1), n)*Mod(2, n)^((n-1)/2)) == 1)&&lift((Mod(((4*ceil((1/4)*n)-2)), n) )== 1)&&lift((Mod(2, n)^((n+1)/2) +Mod(floor((3/4)*n),n)*Mod(2, n)^(((n+1)/2)+1 ))== 1)

More terms from Alois P. Heinz, Nov 10 2017

A294993 Numbers n > 1 such that all of 2^(n-1), 3^(n-1), 5^(n-1), (2n-1)(2^((n-1)/2)), 4ceiling((3/4)n)-2, and (2^((n+1)/2) + floor(n/4)*2^((n+3)/2)) are congruent to 1 (mod n).

Original entry on oeis.org

11, 19, 43, 59, 67, 83, 107, 131, 139, 163, 179, 211, 227, 251, 283, 307, 331, 347, 379, 419, 443, 467, 491, 499, 523, 547, 563, 571, 587, 619, 643, 659, 683, 691, 739, 787, 811, 827, 859, 883, 907, 947, 971, 1019, 1051, 1091, 1123, 1163, 1171, 1187, 1259, 1283

Offset: 1

Jonas Kaiser, Nov 12 2017

nonn

It appears that A007520 is a subsequence. Up to 10^7 there are no composites in this sequence.

The first composite is a(17465859) = 1397357851; there are probably infinitely many. - Charles R Greathouse IV, Nov 12 2017

Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A244626, A294717, A293394, A070179, A007520.

Select[Range[2, 1300], Function[n, AllTrue[Join[Prime[Range@3]^(n - 1), {(2 n - 1) (2^((n - 1)/2)), 4 Ceiling[3 n/4] - 2, (2^((n + 1)/2) + Floor[n/4]*2^((n + 3)/2))}], Mod[#, n] == 1 &]]] (* Michael De Vlieger, Nov 15 2017 *)

is(n) = n%2 && Mod(2, n)^(n-1)==1 && Mod(3, n)^(n-1)==1 && Mod(5, n)^(n-1)==1 && (2*n-1)*Mod(2, n)^((n-1)/2)== 1 && Mod(4*ceil((3/4)*n)-2, n)==1 && Mod(2, n)^((n+1)/2)+floor(n/4)*Mod(2, n)^((n+3)/2)==1

A295196 Numbers n > 1 such that 2^(n-1) and (2n-m)2^(((n-1)/2) - floor(log_2(n))) are congruent to 1 (mod n) for at least one of m = 3, m = 7 and m = 15.

Original entry on oeis.org

7, 23, 31, 47, 71, 79, 263, 271, 1031, 1039, 2063, 4111, 32783, 65543, 65551, 262151, 1048583, 4194319, 8388623, 67108879, 268435463, 1073741831, 1073741839, 4294967311

Offset: 1

Jonas Kaiser, Nov 16 2017

This definition arises from the conjecture that pseudoprime numbers (A001567) occur only at certain distances m from the next smaller number of the form 2^n. So, if we know that a certain distance does not appear with pseudoprime numbers, we are able to calculate these numbers using Fermat's little theorem and we know that it has to be prime. To "plot" the distance of pseudoprime numbers to 2^n use m = A001567(n) - 2^floor(log_2(A001567(n))). So, the first values of m which do not have a "safe prime number distance" (values with "safe prime number distance" are those values for m which pseudoprime numbers never have) should be m = 1, 49, 81, 85, 129, 133, 273, 275, 289, 321, ....
Conjecture 1: There are no composite numbers in this sequence and perhaps infinitely many primes.
Conjecture 2: For m = 7 this definition generates A104066 and for m = 15 this definition generates A144487 (A057197).
Conjecture 3: There are (infinitely many?) m for which this definition generates nothing but (infinitely many?) primes of the form p = 2^k + m.
It appears that this sequence is a subsequence of A139035.

Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A057197, A104066, A139035, A144487, A244626, A294717, A293394.

twoDistableQ[n_] := MemberQ[Mod[(2n - {3, 7, 15}) PowerMod[2, (n - 1)/2 - Floor@ Log2@ n, n], n], 1]; p = 3; twoDistablesList = {}; While[p < 1000000000, If[twoDistableQ@ p, AppendTo[ twoDistablesList, p]]; p = NextPrime@ p]; twoDistablesList (* Robert G. Wilson v, Nov 17 2017 *)

a(n) = (n%2) && lift((Mod(2, n)^(n-1))==1) && (lift((Mod((2*n-3), n)*Mod(2, n)^(((n-1)/2)-floor(log(n)/log(2)))) == 1)||lift((Mod((2*n-7), n)*Mod(2, n)^(((n-1)/2)-floor(log(n)/log(2)))) == 1)||lift((Mod((2*n-15), n)*Mod(2, n)^(((n-1)/2)-floor(log(n)/log(2)))) == 1))

is(n)=if(Mod(2,n)^(n-1)!=1, return(0)); my(m=Mod(2,n)^(n\2-logint(n,2))); ((2*n-3)*m==1 || (2*n-7)*m==1 || (2*n-15)*m==1) && n>1 \\ Charles R Greathouse IV, Nov 17 2017

a(17)-a(24) from Charles R Greathouse IV, Nov 17 2017

cp's OEIS Frontend

A375918 Composite numbers k == 5, 7 (mod 12) such that 3^((k-1)/2) == -1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A293394 Numbers k such that (2*k-1)*(2^((k-1)/4)) == 1 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A294717 Numbers k such that 2^((k-1)/3) == 1 (mod k) and (2*k-1)*(2^((k-1)/6)) == 1 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A270698 Composite numbers k == 1 (mod 4) such that (1 + i)^k == 1 + i (mod k), where i = sqrt(-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A294912 Numbers n such that 2^(n-1), (2*n-1)*(2^((n-1)/2)), (4*ceiling((3/4)*n)-2), and (2^((n+1)/2) + floor((1/4)*n)*2^(((n+1)/2)+1)) are all congruent to 1 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A307798 The "residue" pseudoprimes: odd composite numbers n such that q(n)^((n-1)/2) == 1 (mod n), where base q(n) is the smallest prime quadratic residue modulo n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A294919 Numbers n such that 2^(n-1), (2*n-1)*(2^((n-1)/2)), (4*ceiling((1/4)*n)-2), and (2^((n+1)/2) + floor((3/4)*n)*2^(((n+1)/2)+1)) are all congruent to 1 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

A293394 Numbers k such that (2k-1)(2^((k-1)/4)) == 1 (mod k).

A294717 Numbers k such that 2^((k-1)/3) == 1 (mod k) and (2k-1)(2^((k-1)/6)) == 1 (mod k).

A294912 Numbers n such that 2^(n-1), (2n-1)(2^((n-1)/2)), (4ceiling((3/4)n)-2), and (2^((n+1)/2) + floor((1/4)n)2^(((n+1)/2)+1)) are all congruent to 1 (mod n).

A294919 Numbers n such that 2^(n-1), (2n-1)(2^((n-1)/2)), (4ceiling((1/4)n)-2), and (2^((n+1)/2) + floor((3/4)n)2^(((n+1)/2)+1)) are all congruent to 1 (mod n).

A294993 Numbers n > 1 such that all of 2^(n-1), 3^(n-1), 5^(n-1), (2n-1)(2^((n-1)/2)), 4ceiling((3/4)n)-2, and (2^((n+1)/2) + floor(n/4)*2^((n+3)/2)) are congruent to 1 (mod n).

A295196 Numbers n > 1 such that 2^(n-1) and (2n-m)2^(((n-1)/2) - floor(log_2(n))) are congruent to 1 (mod n) for at least one of m = 3, m = 7 and m = 15.