## Other

drummers-lowrise

Message boards : General discussion : Implementing an Algorithm?

Author Message
crowattorney

Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683

Message 152832 - Posted: 28 Dec 2021 | 2:27:44 UTC

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

crowattorney

Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683

Message 152833 - Posted: 28 Dec 2021 | 2:31:00 UTC - in response to Message 152832.

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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 705
ID: 164101
Credit: 305,166,630
RAC: 8

Message 152857 - Posted: 28 Dec 2021 | 18:35:46 UTC

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.

JeppeSN

Joined: 5 Apr 14
Posts: 1695
ID: 306875
Credit: 40,801,467
RAC: 11,879

Message 152858 - Posted: 28 Dec 2021 | 19:30:37 UTC

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

crowattorney

Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683

Message 152859 - Posted: 28 Dec 2021 | 19:54:33 UTC - in response to Message 152858.

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

JeppeSN

Joined: 5 Apr 14
Posts: 1695
ID: 306875
Credit: 40,801,467
RAC: 11,879

Message 152861 - Posted: 28 Dec 2021 | 21:48:09 UTC - in response to Message 152859.

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

crowattorney

Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683

Message 152862 - Posted: 28 Dec 2021 | 23:35:28 UTC - in response to Message 152861.

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

crowattorney

Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683

Message 152864 - Posted: 29 Dec 2021 | 2:23:34 UTC - in response to Message 152862.

Edit: This is quite easily provable, as 3^k - 1 / 2 can be incremented by multiplying 3 and adding 1.

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

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 407,815,873
RAC: 10,359

Message 153018 - Posted: 2 Jan 2022 | 16:14:03 UTC - in response to Message 152857.

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 Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 205
ID: 1108183
Credit: 11,783,558
RAC: 4,735

Message 153020 - Posted: 2 Jan 2022 | 18:23:09 UTC - in response to Message 153018.

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.

Message boards : General discussion : Implementing an Algorithm?