Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
General discussion :
Implementing an Algorithm?
| Author |
Message |
|---|
|
|
|
I found a conjecture on OEIS for a prime form that I've been thinking about for a while:
Conjecture: The number n = 3^k + 2 is prime if and only if 2^((n-1)/2) == -1 (mod n). - Maheswara Rao Valluri
https://oeis.org/A051783
I was wondering if anybody knows how I can implement this in to code so I can test it out, or better yet, some helpful resources that'll help me prove it to be True / False.
____________
Ahoy | |
|
|
|
|
I can imagine a basic way of implementing it in to code, just compute 3^n + 2 with a for loop and a variable-length array (or a library perhaps), and then make an array of the same length, which stored 2^g mod n. Iterate squaring the modulo-containing array, and adding previous values. If this were done enough times, you would have 2^((n-1)/2) mod n.
Perhaps?
____________
Ahoy | |
|
Yves GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 705
ID: 164101
Credit: 305,166,630
RAC: 8
|
|
You can write a simple Pari GP program:
for (k=1, oo, n=3^k+2; if (Mod(2, n)^((n-1)/2) == -1, print(k); if (!ispseudoprime(n), print("Failed!"))));
The test checks if n is an Euler–Jacobi pseudoprime. Because 3^k + 2 increases exponentially, if n is a PRP then it is most likely prime.
You can generate easily an infinite number of conjectures in this way. Nobody knows how to prove them. Note that many of them are true but few of them are false: for that reason, a simple proof should not exist.
A more interesting problem is to find (for each K) a such that n = 3^k + a is a PRP => n is prime for k < K but 3^K + a is a PRP and not a prime. | |
|
|
|
|
And we can even conjecture that the number n = 3^k + 2 is prime if and only if 2^(n-1) == 1 (mod n). /JeppeSN | |
|
|
|
And we can even conjecture that the number n = 3^k + 2 is prime if and only if 2^(n-1) == 1 (mod n). /JeppeSN
I did find that result too, as (x-1)^2 == 1 (mod x), but also (x+1)^2 == 1 (mod x) as well, so you would have to prove that the latter caser never exists in order to conjecture.
after some equation restructuring, I found that the conjecture can be restated as 2 * 2^(3^k)) == 1 (mod 3^k + 2)
you could write some pseudocode:
int n = 3 ^ k + 2;
int m = 2;
for (int i = 0; i < k; ++i) {
m = (m * m * m) % n;
}
if (2 * m == n + 1) {
cout << "3^" << k << "+2 is prime if above conjecture is true!";
}
(Yes I know my pseudocode looks like c++, thats the language I learned first blah blah blah)
____________
Ahoy | |
|
|
|
I did find that result too, as (x-1)^2 == 1 (mod x), but also (x+1)^2 == 1 (mod x) as well, so you would have to prove that the latter caser never exists in order to conjecture.
Do remember that when x is NOT prime there can be more square roots of 1 than just ±1.
For example, modulo x=77, we have (±1)^2 == 1 (mod 77), but also (±34)^2 == 1 (mod 77).
So my bolder conjecture could fail in such a way too.
If x is prime, or if x is 1 or 4, or a power of an odd prime, or twice a power of an odd prime, then the multiplicative group modulo x is a cyclic group, and in a cyclic group the neutral element has no more than two square roots. In all other cases, 1 will have "exotic" square roots as well.
/JeppeSN | |
|
|
|
|
Can it be agreed upon that in order to find the modulus of the two goliathic numbers that we would need to do the exponentiate and add iterative approach, of doing:
2^(a+b) mod n = [(2^a mod n) + (2^b mod n)] mod n, or
2^ab mod n = (2^a mod n) ^ b mod n?
(possibly others I am forgetting about)
Because that is the only way we can generate code, and more ambitiously, a proof, without having to perform say, a square root on the 2^n-1 to get 2^(n-1)/2, etc.
If so, then we would need to write an algorithm for generating 3^k + 1 / 2 only using the operations we can apply in to the above exponent-modulus format.
Edit: This is quite easily provable, as 3^k - 1 / 2 can be incremented by multiplying 3 and adding 1. Here is what the pseudocode would look like:
int n = 3 ^ k + 2;
int m = 2;
for (int i = 0; i < (k - 1); ++i) {
m = (m * m * m * 2) % n;
}
if (2 * m == n + 1) {
cout << "3^" << k << "+2 is prime if above conjecture is true!";
}
____________
Ahoy | |
|
|
|
Edit: This is quite easily provable, as 3^k - 1 / 2 can be incremented by multiplying 3 and adding 1.
Dummy Alert weewoo weewoo
I mistook (3^k + 1) / 2 for (3^k - 1) / 2.
The real iterative operation would have been multiply by three and then subtract one, if that matters
____________
Ahoy | |
|
 Bur Volunteer tester
Send message
Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 407,815,873
RAC: 10,359
                
|
You can write a simple Pari GP program:
for (k=1, oo, n=3^k+2; if (Mod(2, n)^((n-1)/2) == -1, print(k); if (!ispseudoprime(n), print("Failed!"))));
The test checks if n is an Euler–Jacobi pseudoprime. So this first checks whether n is prime under the assumption that the conjecture is true and then, additionally, does a PRP test as a means to potentially disprove the conjecture?
Because 3^k + 2 increases exponentially, if n is a PRP then it is most likely prime. Why is that? Couldn't any number be written as 3^k + m and thus increase exponentially with increasing k?
Is the test for primality under the assumption of the conjecture to be true computationally faster than a PRP test? If so, it could be an interesting way to generate large PRPs.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000 | |
|
Ravi FernandoProject administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 205
ID: 1108183
Credit: 11,783,558
RAC: 4,735
              
|
Is the test for primality under the assumption of the conjecture to be true computationally faster than a PRP test? If so, it could be an interesting way to generate large PRPs. The test for primality assuming the conjecture is a PRP test (basically a base-2 strong PRP test). I'm not the right person to ask, but I assume it's one of the faster PRP tests out there. And I certainly agree that prime searches should run the fastest available PRP test before verifying primes with a deterministic primality test (or in this case a more reliable PRP test)--large PRPs are so rare that the verification step takes a negligible fraction of the overall time.
Because 3^k + 2 increases exponentially, if n is a PRP then it is most likely prime. Why is that? Couldn't any number be written as 3^k + m and thus increase exponentially with increasing k?
Just to further explain Yves's comment: generally speaking, if n is a PRP then it is most likely prime, period. (PRP is short for...) Pseudoprimes are rare, and they become rarer as the numbers get larger. Accordingly, in a very dense sequence (such as the linear sequence 3^k + m with k fixed and m changing), you will likely find infinitely many pseudoprimes. But in a very sparse sequence (such as the exponential sequence 3^k + m with m fixed and k changing), you will likely find very few or no pseudoprimes: the chance of finding one drops too quickly as you go.
So if you pick a value of m and ask whether there exists a pseudoprime of the form 3^k + m, the answer will very often be no. But since base-2 strong pseudoprimes exist, the answer is yes for some values of m. Accordingly, you should not expect there to be an easy way to prove there are no pseudoprimes of the form 3^k + m for any particular m. | |
|
Post to thread
Message boards :
General discussion :
Implementing an Algorithm? |
