Good sieve for Generalized Pierpoint primes

[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.

[science_man_88]

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

[science_man_88]

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]

Triple post

You can also show things like:

2^(8x+4)*3^(16y+8)*5^(16z+8)+1 are always divisible by 17.

[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.

[science_man_88]

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).

[science_man_88]

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

[science_man_88]

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.

[carpetpool]

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.

[science_man_88]

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.

Go see my blog thread replies to this thread.