mersenneforum.org (https://www.mersenneforum.org/index.php)
-   sweety439 (https://www.mersenneforum.org/forumdisplay.php?f=137)
-   -   Irregular primes and other types of primes (https://www.mersenneforum.org/showthread.php?t=25963)

 sweety439 2020-09-15 07:57

Irregular primes and other types of primes

Primes related to Fermat's Last Theorem:

Bernoulli-irregular primes: 37, 59, 67, 101, 103, 131, 149, 157, 233, 257, 263, 271, 283, 293, 307, 311, 347, 353, 379, 389, 401, 409, 421, 433, 461, 463, 467, 491, 523, 541, 547, 557, 577, 587, 593, 607, 613, 617, 619, 631, 647, 653, 659, 673, 677, 683, 691, 727, 751, 757, 761, 773, 797, 809, 811, 821, 827, 839, 877, 881, 887, 929, 953, 971, 1061, ... [set A]

Euler-irregular primes: 19, 31, 43, 47, 61, 67, 71, 79, 101, 137, 139, 149, 193, 223, 241, 251, 263, 277, 307, 311, 349, 353, 359, 373, 379, 419, 433, 461, 463, 491, 509, 541, 563, 571, 577, 587, 619, 677, 691, 709, 739, 751, 761, 769, 773, 811, 821, 877, 887, 907, 929, 941, 967, 971, 983, 1013, 1019, ... [set B]

Primes such that k*p+1 is composite for all k in {2,4,8,10,14,16}: 197, 223, 227, 229, 257, 263, 283, 311, 317, 379, 383, 389, 457, 461, 463, 467, 521, 541, 569, 607, 661, 701, 751, 773, 787, 839, 859, 863, 881, 887, 907, 971, 991, ... [set C]

Consider the odd primes p, found the smallest n such that k*p^n+1 is prime for k in {2,4,8,10,14,16} (the primes in set C are the primes p such that these numbers are all composite for n=1): ([I]italic[/I] if n>10000)

[CODE]
p k=2 k=4 k=8 k=10 k=14 k=16
3: 1, 1, 2, 1, 1, 3,
5: 1, 2, 1, 2, 1, 2,
7: covering set, 1, covering set, 1, covering set, 1,
11: 1, covering set, 1, 10, covering set, 8,
13: covering set, 1, covering set, 1, covering set, 3,
17: 47, 6, 1, 1356, 1, 4,
19: covering set, 3, covering set, 1, covering set, 6, [E-irregular]
23: 1, 342, [I][COLOR="Red"]119215[/COLOR][/I], covering set, 5, 4,
29: 1, covering set, 1, 4, 3, 2,
31: covering set, covering set, covering set, 1, covering set, 2, [E-irregular]
37: covering set, 1, covering set, 2, covering set, 1, [B-irregular]
41: 1, covering set, covering set, 2, covering set, 4,
43: covering set, 1, covering set, 1, covering set, 3, [E-irregular]
47: 175, 2, covering set, 2, 1, covering set, [E-irregular]
53: 1, [I][COLOR="red"]>1610000[/COLOR][/I], [I][COLOR="red"]227183[/COLOR][/I], 16, 1, 4
59: 3, covering set, 5, 36, 1, 2, [B-irregular]
61: covering set, covering set, covering set, 165, covering set, 1, [E-irregular]
67: covering set, 1, covering set, covering set, covering set, 3, [B-irregular] [E-irregular]
71: 3, covering set, 1, 2, covering set, 2, [E-irregular]
73: covering set, 1, covering set, 3, covering set, 40,
79: covering set, 1, covering set, 5, covering set, 8, [E-irregular]
83: 1, 5870, covering set, 2, 1, 348,
89: 1, covering set, 5, covering set, 3, [I]unknown[/I]
97: covering set, 1, covering set, 1, covering set, 1,
101: [I][COLOR="red"]192275[/COLOR][/I], covering set, 1, 1506, covering set, covering set [B-irregular] [E-irregular]
103: covering set, 2, covering set, 1, covering set, covering set, [B-irregular]
107: 3, [I][COLOR="red"]32586[/COLOR][/I], 1, 42, 1, 12
109: covering set, 3, covering set, 1, covering set, 2,
113: 1, 2958, 47, 2, 1, 40
127: covering set, 1, covering set, 4, covering set, 4,
131: 1, covering set, 1, covering set, covering set, 8, [B-irregular]
137: 327, 18, 1, 102, 93, covering set, [E-irregular]
139: covering set, 1, covering set, 18, covering set, 2, [E-irregular]
149: 3, covering set, 1, 2, 1, 18, [B-irregular] [E-irregular]
151: covering set, covering set, covering set, 1, covering set, 1,
157: covering set, 2, covering set, 1, covering set, 3,
163: covering set, 1, covering set, 3, covering set, 1,
[/CODE]

 sweety439 2020-09-15 08:19

Also,

Primes p such that (p^q-1)/(p-1) is composite for all primes q<2000: 269, 281, 311, 331, 487, 499, 541, ... [set D]

Primes p such that (p^q+1)/(p+1) is composite for all primes q<2000: 53, 97, 103, 113, 311, 313, 373, 421, 433, 479, ... [set E]

There are no generalized Wieferich prime base p less than 10^12: 29, 47, 61, 139, 311, 347, 983, ... [set F]

Consider in base b, a prime p is "much more" irregular if it satisfy more of these conditions:

* p is Bernoulli-irregular ([URL="https://oeis.org/A000928"]A000928[/URL])
* p is Euler-irregular ([URL="https://oeis.org/A120337"]A120337[/URL])
* p^n followed by a 1 in base b (i.e. numbers of the form b*p^n+1) is composite for all small n (usually n<10000), but b*p^n+1 do not have a trivial prime factor of all n nor have a covering set of primes
* k*p+1 is composite for k = 2, 4, 8, 10, 14, 16
* (p^q-1)/(p-1) is composite for all small prime q (usually q<2000)
* (p^q+1)/(p+1) is composite for all small prime q (usually q<2000)
* there are no small generalized Wieferich prime base p (usually < 10^12)

The primes satisfying conditions 1, 2, 4 are

263, 311, 379, 461, 463, 541, 751, 773, 887, 971, 1283, 1319, 1381, 1621, 1637, 1759, 1787, ...

Which prime is much more irregular for any given base (radix)?

Consider the first such prime p=263, base 10 have a covering set of {3,11} thus not irregular, in base 2 we have 2*263^957+1 is prime thus not irregular (if our bound of exponent n is greater than 957), it also have an easy prime for bases 4, 6, 12, 14, 16, but in base 8, 8*263^n+1 is composite for n<1000000, thus 263 is much more irregular if we use octal (263 = 407 in base 8), but not much more irregular if we use other bases <= 16

Next such prime is p=311, trivial bases are 1 mod 2, 4 mod 5, or 30 mod 31, we do not consider these bases, if our bound of exponent n is 10000, 311 is much more irregular in only 2 bases for bases b<142 (the smallest base b having a covering set): 10 and 76, thus 311 is much more irregular if we use either base 10 or base 76, but not much more irregular if we use other bases <= 142

The third such prime is p=379, trivial bases are 1 mod 2, 2 mod 3, or 6 mod 7, we do not consider these bases, if our bound of exponent n is 10000, 379 is much more irregular in only 3 bases for bases b<246 (the smallest base b having a covering set): 24, 136 and 156, thus 311 is much more irregular if we use either base 24 or base 136 or base 156, but not much more irregular if we use other bases <= 246

Next such prime is p=461, which is the first "much more irregular" prime in binary: 111001101 in base 2, since 2*461^n+1 is composite for n<=400000, and base 8 already have a covering set, base 4 is a trivial base, base 6 have an easy prime with n=1

 sweety439 2020-09-15 08:35

Many of these primes p have an easy prime of the form either (p^q-1)/(p-1) or (p^q+1)/(p+1):

(p^q-1)/(p-1): (=Rq(p))

p=263 q=5
p=311 first q is 36497 and not an easy prime
p=379 q=17
p=461 q=7
p=463 q=313 (more hard)
p=541 first q is 8951 and not an easy prime
p=751 q=967 (more hard)
p=773 q=3
p=887 q=1201 (more hard)
p=971 q=19

(p^q+1)/(p+1): (=Rq(-p))

p=263 q=13
p=311 first q is 2707 and not an easy prime
p=379 q=3
p=461 q=1889 (more hard)
p=463 q=283 (more hard)
p=541 q=3
p=751 q=23
p=773 q=7
p=887 q=1231 (more hard)
p=971 q=7

Thus, the most irregular prime p<1024 is 311

Also, for generalized Wieferich prime base p:

p=29 no known such prime
p=47 no known such prime
p=61 no known such prime
p=139 q=1822333408543
p=311 no known such prime
p=347 q=14034413930219
p=983 no known such prime

(the only B-irregular primes in this list are 311 and 347, but all of these primes except 29 and 347 are E-irregular primes, thus, 311 is the only prime in this list which is both B-irregular and E-irregular)

And more reasons:

311 is the only one small primes in the sequence: a(1)=38, a(k+1)=2*a(k)+1 (this sequence (39*2^n-1) is also the smallest k divisible by 3 without known Sophie Germain primes pair of the forms k*2^n-1 and k*2^(n+1)-1)
311 is the only one small primes in the sequence: a(1)=12, a(k+1)=3*a(k)-1
311 and 311+2 may be the only twin prime pair of the form 39*2^n+-1
(311*9^n+1)/gcd(311+1,9-1) do not have an easy prime, 311 is the first such odd number for extended Sierpinski base 9
(Let Rn(b) be the generalized repunit base b with length n = (b^n-1)/(b-1)) R311(12) has no known prime factor and be the smallest Rn(12) with no known prime factor for a long time, R311(11) and R311(10) also ever be the smallest Rn(11) and Rn(10) with no known prime factor, also the number R311(-311), it is the smallest (p^p+-1)/(p+-1) with prime p with aurifeuillean factors but both the two aurifeuillean factors have no known prime factor.
Also, 311 is much more irregular since 311^n followed by 1 is not primes for all n<=30K, it is the only such prime < 773

 All times are UTC. The time now is 02:23.