mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2018-02-17, 17:58   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Post 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.
carpetpool is offline   Reply With Quote
Old 2018-02-17, 18:15   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-02-18, 13:26   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

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 ...
science_man_88 is offline   Reply With Quote
Old 2018-02-18, 17:52   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Triple post

You can also show things like:

2^(8x+4)*3^(16y+8)*5^(16z+8)+1 are always divisible by 17.
science_man_88 is offline   Reply With Quote
Old 2018-02-18, 19:06   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

167416 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2018-02-18, 19:42   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-02-19, 01:30   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

202618 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-02-19, 21:34   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2018-02-24, 21:19   #9
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Post

Quote:
Originally Posted by science_man_88 View Post
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.
carpetpool is offline   Reply With Quote
Old 2018-02-24, 21:41   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
Go see my blog thread replies to this thread.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
generalized minimal (probable) primes sweety439 sweety439 68 2020-11-26 16:20
Generalized Repunit primes Bob Underwood Math 12 2020-10-11 20:01
Generalized Fermat numbers (in our case primes) pepi37 Conjectures 'R Us 4 2015-10-09 14:49
Generalized Mersenne Primes Unregistered Homework Help 6 2012-10-31 14:16
Generalized Mersenne Primes Cyclamen Persicum Math 1 2004-01-30 15:11

All times are UTC. The time now is 00:15.

Fri Nov 27 00:15:33 UTC 2020 up 77 days, 21:26, 4 users, load averages: 1.49, 1.48, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.