mersenneforum.org Good sieve for Generalized Pierpoint primes
 Register FAQ Search Today's Posts Mark Forums Read

 2018-02-17, 17:58 #1 carpetpool     "Sam" Nov 2016 2·3·53 Posts Good sieve for Generalized Pierpoint primes What is a good sieve program for Generalized Pierpoint primes which do not have the form k*b^n+-1 where (k < 2^32) is small? That is, a sieve which works on primes of the form 2^a*p^b*q^c*r^d...(r_n)^(d_n) where p, q, r..., r_n are distinct odd primes and there are NO restrictions on the exponents a, b, c, d,... d_n, such as their size. Does the sieve work when trying to find primes of the form 2^a*p^b*q^c*r^d...(r_n)^(d_n) where all the primes (p, q, r,..., r_n) are fixed, and all the exponents for the primes are fixed (except only one, two, or even three primes). For example, I found a prime of the form 2^a*3^b*5^c*7^d+1 with no definite ratio, pattern, or restrictions for the exponents a, b, c, d. Here is what my sieve file looked like: (I chose the fixed exponents for 2 and 3 randomly and the exponent ranges for 5 and 7 randomly) sieve.txt: --- ABC2 2^1473*3^2731*5^$a*7^$b+1 a: from 1000 to 1000 b: from 400 to 500 --- Running the program up to b = 415, I only found one PRP (which was later proved prime): 2^1473*3^2731*5^1020*7^408+1 --- If I wanted to try higher fixed exponents and ranges, what would be a good sieve program to use so I know which numbers I should test? Thanks for help.
2018-02-17, 18:15   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by carpetpool What is a good sieve program for Generalized Pierpoint primes which do not have the form k*b^n+-1 where (k < 2^32) is small? That is, a sieve which works on primes of the form 2^a*p^b*q^c*r^d...(r_n)^(d_n) where p, q, r..., r_n are distinct odd primes and there are NO restrictions on the exponents a, b, c, d,... d_n, such as their size. Does the sieve work when trying to find primes of the form 2^a*p^b*q^c*r^d...(r_n)^(d_n) where all the primes (p, q, r,..., r_n) are fixed, and all the exponents for the primes are fixed (except only one, two, or even three primes). For example, I found a prime of the form 2^a*3^b*5^c*7^d+1 with no definite ratio, pattern, or restrictions for the exponents a, b, c, d. Here is what my sieve file looked like: (I chose the fixed exponents for 2 and 3 randomly and the exponent ranges for 5 and 7 randomly) sieve.txt: --- ABC2 2^1473*3^2731*5^$a*7^$b+1 a: from 1000 to 1000 b: from 400 to 500 --- Running the program up to b = 415, I only found one PRP (which was later proved prime): 2^1473*3^2731*5^1020*7^408+1 --- If I wanted to try higher fixed exponents and ranges, what would be a good sieve program to use so I know which numbers I should test? Thanks for help.
Also a superset to https://en.wikipedia.org/wiki/Primorial_prime

 2018-02-18, 13:26 #3 science_man_88     "Forget I exist" Jul 2009 Dumbassville 202618 Posts You can use quadratic reciprocity to help some all even powers clump to form a quadratc residue. All powers not in those, but divisble by 3 form cubic residues, 5 pentic residues ...
 2018-02-18, 17:52 #4 science_man_88     "Forget I exist" Jul 2009 Dumbassville 8,369 Posts Triple post You can also show things like: 2^(8x+4)*3^(16y+8)*5^(16z+8)+1 are always divisible by 17.
 2018-02-18, 19:06 #5 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 34×71 Posts I am not sure that there is a particularly good example. polysieve from http://mersenneforum.org/showthread....lysieve&page=8 would probably sieve it although it is not what it was designed for.
2018-02-18, 19:42   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts

Quote:
 Originally Posted by henryzz I am not sure that there is a particularly good example. polysieve from http://mersenneforum.org/showthread....lysieve&page=8 would probably sieve it although it is not what it was designed for.
No ,not to my extremely limited knowledge either. You can ( as I've shown) do better than brute force though ( okay I brute forced enough, to show certain forms don't work, and the exponents need be pairwise coprime to not group under forms like a^5+1 potentially).

Last fiddled with by science_man_88 on 2018-02-18 at 19:51

2018-02-19, 01:30   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

836910 Posts

Quote:
 Originally Posted by science_man_88 No ,not to my extremely limited knowledge either. You can ( as I've shown) do better than brute force though ( okay I brute forced enough, to show certain forms don't work, and the exponents need be pairwise coprime to not group under forms like a^5+1 potentially).
Of course, without restrictions on exponents (number of them, minimum), you can prove that the first part can be all even composites, meaning all odd primes can be made this way

Last fiddled with by science_man_88 on 2018-02-19 at 01:33

 2018-02-19, 21:34 #8 science_man_88     "Forget I exist" Jul 2009 Dumbassville 8,369 Posts Code: forprime(x=1,10,forprime(y=x+1,100, for(z=1,y-1,if(lift(Mod(x,y)^z)==n-1,print(x","y","z);next(2))))) Here's a code to help you carpetpool.
2018-02-24, 21:19   #9
carpetpool

"Sam"
Nov 2016

2×3×53 Posts

Quote:
 Originally Posted by science_man_88 Triple post You can also show things like: 2^(8x+4)*3^(16y+8)*5^(16z+8)+1 are always divisible by 17.
What you are doing is taking each of the prime powers mod 17 and multiplying them such that the result is always -1. Then add 1 to get 0:

2^(8x+4) = 2^4 = -1 (mod 17)

3^(16y+8) = 3^8 = 1 (mod 17)

5^(16z+8) = 5^8 = -1 (mod 17)

Add these up and you get (-1)+(-1)+1 = -1 (mod 17)
Then adding 1, you get (-1)+1 = 0 (mod 17)

The congruence holds for any values of x, y, z.

Here is another example:

2^(22x+11)*3^(31y)+1 cannot be prime for any integers x, y.

Now as a quick exercise, show that this is true.

2018-02-24, 21:41   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts

Quote:
 Originally Posted by carpetpool What you are doing is taking each of the prime powers mod 17 and multiplying them such that the result is always -1. Then add 1 to get 0: 2^(8x+4) = 2^4 = -1 (mod 17) 3^(16y+8) = 3^8 = 1 (mod 17) 5^(16z+8) = 5^8 = -1 (mod 17) Add these up and you get (-1)+(-1)+1 = -1 (mod 17) Then adding 1, you get (-1)+1 = 0 (mod 17) The congruence holds for any values of x, y, z. Here is another example: 2^(22x+11)*3^(31y)+1 cannot be prime for any integers x, y. Now as a quick exercise, show that this is true.

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 82 2020-11-29 19:26 Bob Underwood Math 12 2020-10-11 20:01 pepi37 Conjectures 'R Us 4 2015-10-09 14:49 Unregistered Homework Help 6 2012-10-31 14:16 Cyclamen Persicum Math 1 2004-01-30 15:11

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

Sun Nov 29 23:48:17 UTC 2020 up 80 days, 20:59, 3 users, load averages: 1.09, 1.32, 1.36