A293394 -id:A293394 - cp's OEIS frontend

A070179 Primes p such that x^2 = 2 has a solution mod p, but x^(2^2) = 2 has no solution mod p.

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, 2297, 2377, 2417, 2521, 2609, 2617, 2633, 2713

Offset: 1

Klaus Brockhaus, Apr 29 2002

Complement of A014754 with regard to primes of the form 8*k+1.
These appear to be the primes p for which 4^((p-1)*n/8) mod p = (p-2)*( n mod 2)+1. For example, 4^(5*n) mod 41 = 1,40,1,40,1,40...= 39*(n mod 2)+1 and 4^(30*n) mod 241 = 1,240,1,240,1,240...= 239*(n mod 2) +1. - Gary Detlefs, Jul 06 2014
Primes p == 1 mod 8 such that 2^((p-1)/4) == -1 mod p. - Robert Israel, Jul 06 2014
A very similar sequence is A293394. - Jonas Kaiser, Nov 08 2017

Bruno Berselli, Table of n, a(n) for n = 1..1000

Cf. A038873, A040098, A040100, A059667, A070180-A070188, A014754.

[p: p in PrimesUpTo(3000) | not exists{x: x in ResidueClassRing(p) | x^4 eq 2} and exists{x: x in ResidueClassRing(p) | x^2 eq 2}]; // Vincenzo Librandi, Sep 21 2012

select(p -> isprime(p) and 2 &^((p-1)/4) mod p = p-1, [8*k+1$k=1..10000]); # Robert Israel, Jul 06 2014

PARI
```
forprime(p=2,2720,x=0; while(x
				
```

{a(n) = local(m, c, x); if( n<1, 0, c = 0; m = 1; while( cMichael Somos, Mar 22 2008 */

ok(p, r, k1, k2)={
if ( Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
if ( Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
return(1);
}
forprime(p=2,10^4, if (ok(p,2,2,2^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

is(n)=n%8==1 && Mod(2,n)^(n\4)==-1 && isprime(n) \\ Charles R Greathouse IV, Nov 10 2017

Primes of the form 8*k + 1 but not x^2 + 64*y^2. - Michael Somos, Mar 22 2008

a(n) ~ 8n log n. - Charles R Greathouse IV, Nov 10 2017

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

A295835 Numbers k == 3 (mod 4) such that 2^((k-1)/2), 3^((k-1)/2) and 5^((k-1)/2) are congruent to 1 (mod k).

Original entry on oeis.org

71, 191, 239, 311, 359, 431, 479, 599, 719, 839, 911, 1031, 1151, 1319, 1439, 1511, 1559, 1871, 2039, 2111, 2351, 2399, 2591, 2711, 2879, 2999, 3119, 3191, 3359, 3671, 3719, 3911, 4079, 4271, 4391, 4679, 4751, 4799, 4871, 4919, 5039, 5231, 5279, 5351, 5399, 5471

Offset: 1

Jonas Kaiser, Nov 28 2017

nonn

There are very few composite numbers in this sequence: The probability of catching a pseudoprime number (A001567) with this definition is estimated at 1 in 263 billion.
Composite numbers in the sequence include the Carmichael numbers 131314855918751, 23282264781147191, 70122000249565031, 104782993259720471, 583701149409931151, 870012810301712351. - Robert Israel, Nov 28 2017
With the exception of the pseudoprimes, it seems that this is a subsequence of A139035. Primes of this form (A139035) have two special properties. 1. There exists a smallest m of the form m = (A139035 - 1)/2 such that 2^m == 1 (mod A139035). 2. m is odd. The core of this definition is based on these two properties. The term 2^((k-1)/2) == 1 (mod n) is based on the first property, while the term k == 3 (mod 4) is based on the second property. The terms 3^((k-1)/2) == 1 (mod n) and 5^((k-1)/2) == 1 (mod n) I just tried freely to Fermat.
Prime terms are congruent to 71 or 119 modulo 120. - Jianing Song, Nov 22 2018 [This is because 2, 3, and 5 must be quadratic residues modulo every prime number in this sequence. - Jianing Song, Sep 01 2024]
From Jianing Song, Sep 03 2024: (Start)
Compare this sequence to the sequence of absolute Euler pseudoprimes (A033181): odd composite numbers k such that a^((k-1)/2) == +-1 (mod k) for every a coprime to k. Such numbers k satisfy 2*psi(k) | (k-1), where psi = A002322, so we must have k == 1 (mod 4).
All terms in this sequence are congruent to 7 modulo 8. In fact, taking the Jacobi symbol modulo k (which only depends on the remainder modulo k) of both sides of 2^((k-1)/2) == 1 (mod k) yields (2/k)^((k-1)/2) = 1. Since k == 3 (mod 4), we have that (k-1)/2 is odd, so (2/k) = 1, which means that k == 7 (mod 8). (End)
Those numbers given above by Robert Israel are all congruent to 71 modulo 120. There are no known composite terms congruent to 119 modulo 120; cf. A294092. - Bill McEachen and Jianing Song, Sep 05 2024

Robert Israel, 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. A001567, A293394, A294717, A294993, A294919, A294912.

A294092 is a subsequence.

filter:= proc(n) [2&^((n-1)/2),3&^((n-1)/2), 5&^((n-1)/2)] mod n = [1,1,1]  end proc:
select(filter, [seq(i,i=3..10000,4)]); # Robert Israel, Nov 28 2017, corrected Feb 26 2018

fQ[n_] := PowerMod[{2, 3, 5}, (n - 1)/2, n] == {1, 1, 1}; Select[3 + 4Range@ 1500, fQ] (* Michael De Vlieger, Nov 28 2017 and slightly modified by Robert G. Wilson v, Feb 26 2018 based on the renaming *)

is(n) = n%4==3 && Mod(2, n)^(n\2)==1 && Mod(3, n)^(n\2)==1 && Mod(5, n)^(n\2)==1 && Mod(2, n)^logint(n+1,2)!=1 \\ Charles R Greathouse IV, Nov 28 2017

Definition corrected by Jonas Kaiser, Feb 05 2018

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

A070179 Primes p such that x^2 = 2 has a solution mod p, but x^(2^2) = 2 has no solution mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

PARI

PARI

PARI

PARI

Formula

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

A295835 Numbers k == 3 (mod 4) such that 2^((k-1)/2), 3^((k-1)/2) and 5^((k-1)/2) are congruent to 1 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A295196 Numbers n > 1 such that 2^(n-1) and (2*n-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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

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.