PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Implementing an Algorithm?

Author Message
Profile crowattorney
Avatar
Send message
Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683
321 LLR Bronze: Earned 10,000 credits (84,015)Cullen LLR Silver: Earned 100,000 credits (146,809)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (25,308)PPS LLR Amethyst: Earned 1,000,000 credits (1,343,369)PSP LLR Bronze: Earned 10,000 credits (42,335)SGS LLR Silver: Earned 100,000 credits (241,317)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,227,910)PPS Sieve Bronze: Earned 10,000 credits (80,904)AP 26/27 Amethyst: Earned 1,000,000 credits (1,176,513)GFN Turquoise: Earned 5,000,000 credits (8,280,640)PSA Bronze: Earned 10,000 credits (15,571)
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

Profile crowattorney
Avatar
Send message
Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683
321 LLR Bronze: Earned 10,000 credits (84,015)Cullen LLR Silver: Earned 100,000 credits (146,809)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (25,308)PPS LLR Amethyst: Earned 1,000,000 credits (1,343,369)PSP LLR Bronze: Earned 10,000 credits (42,335)SGS LLR Silver: Earned 100,000 credits (241,317)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,227,910)PPS Sieve Bronze: Earned 10,000 credits (80,904)AP 26/27 Amethyst: Earned 1,000,000 credits (1,176,513)GFN Turquoise: Earned 5,000,000 credits (8,280,640)PSA Bronze: Earned 10,000 credits (15,571)
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
Send message
Joined: 19 Aug 12
Posts: 705
ID: 164101
Credit: 305,166,630
RAC: 8
GFN Double Silver: Earned 200,000,000 credits (305,166,630)
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.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1695
ID: 306875
Credit: 40,801,467
RAC: 11,879
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (593,283)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (112,799)PPS LLR Jade: Earned 10,000,000 credits (15,960,475)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (210,142)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (4,228,147)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile crowattorney
Avatar
Send message
Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683
321 LLR Bronze: Earned 10,000 credits (84,015)Cullen LLR Silver: Earned 100,000 credits (146,809)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (25,308)PPS LLR Amethyst: Earned 1,000,000 credits (1,343,369)PSP LLR Bronze: Earned 10,000 credits (42,335)SGS LLR Silver: Earned 100,000 credits (241,317)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,227,910)PPS Sieve Bronze: Earned 10,000 credits (80,904)AP 26/27 Amethyst: Earned 1,000,000 credits (1,176,513)GFN Turquoise: Earned 5,000,000 credits (8,280,640)PSA Bronze: Earned 10,000 credits (15,571)
Message 152859 - Posted: 28 Dec 2021 | 19:54:33 UTC - in response to Message 152858.
Last modified: 28 Dec 2021 | 20:17:12 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


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

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1695
ID: 306875
Credit: 40,801,467
RAC: 11,879
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (593,283)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (112,799)PPS LLR Jade: Earned 10,000,000 credits (15,960,475)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (210,142)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (4,228,147)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile crowattorney
Avatar
Send message
Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683
321 LLR Bronze: Earned 10,000 credits (84,015)Cullen LLR Silver: Earned 100,000 credits (146,809)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (25,308)PPS LLR Amethyst: Earned 1,000,000 credits (1,343,369)PSP LLR Bronze: Earned 10,000 credits (42,335)SGS LLR Silver: Earned 100,000 credits (241,317)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,227,910)PPS Sieve Bronze: Earned 10,000 credits (80,904)AP 26/27 Amethyst: Earned 1,000,000 credits (1,176,513)GFN Turquoise: Earned 5,000,000 credits (8,280,640)PSA Bronze: Earned 10,000 credits (15,571)
Message 152862 - Posted: 28 Dec 2021 | 23:35:28 UTC - in response to Message 152861.
Last modified: 28 Dec 2021 | 23:57:38 UTC

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

Profile crowattorney
Avatar
Send message
Joined: 17 Apr 20
Posts: 12
ID: 1254355
Credit: 13,664,692
RAC: 40,683
321 LLR Bronze: Earned 10,000 credits (84,015)Cullen LLR Silver: Earned 100,000 credits (146,809)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (25,308)PPS LLR Amethyst: Earned 1,000,000 credits (1,343,369)PSP LLR Bronze: Earned 10,000 credits (42,335)SGS LLR Silver: Earned 100,000 credits (241,317)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,227,910)PPS Sieve Bronze: Earned 10,000 credits (80,904)AP 26/27 Amethyst: Earned 1,000,000 credits (1,176,513)GFN Turquoise: Earned 5,000,000 credits (8,280,640)PSA Bronze: Earned 10,000 credits (15,571)
Message 152864 - Posted: 29 Dec 2021 | 2:23:34 UTC - in response to Message 152862.
Last modified: 29 Dec 2021 | 2:35:50 UTC


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

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 407,815,873
RAC: 10,359
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Ruby: Earned 2,000,000 credits (2,315,295)ESP LLR Ruby: Earned 2,000,000 credits (2,151,088)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,620,968)PPS LLR Jade: Earned 10,000,000 credits (10,943,107)PSP LLR Ruby: Earned 2,000,000 credits (2,064,832)SoB LLR Ruby: Earned 2,000,000 credits (2,434,466)SR5 LLR Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Ruby: Earned 2,000,000 credits (2,027,649)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Ruby: Earned 2,000,000 credits (2,112,258)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Turquoise: Earned 5,000,000 credits (5,096,952)AP 26/27 Turquoise: Earned 5,000,000 credits (5,797,662)GFN Jade: Earned 10,000,000 credits (10,874,159)WW Double Silver: Earned 200,000,000 credits (349,980,000)PSA Amethyst: Earned 1,000,000 credits (1,042,601)
Message 153018 - Posted: 2 Jan 2022 | 16:14:03 UTC - in response to Message 152857.
Last modified: 2 Jan 2022 | 16:15:47 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.
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
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 205
ID: 1108183
Credit: 11,783,558
RAC: 4,735
321 LLR Gold: Earned 500,000 credits (942,037)Cullen LLR Bronze: Earned 10,000 credits (82,217)ESP LLR Bronze: Earned 10,000 credits (16,570)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (68,801)PPS LLR Ruby: Earned 2,000,000 credits (3,930,073)PSP LLR Silver: Earned 100,000 credits (106,263)SoB LLR Silver: Earned 100,000 credits (258,849)SR5 LLR Bronze: Earned 10,000 credits (76,537)SGS LLR Silver: Earned 100,000 credits (148,878)TRP LLR Silver: Earned 100,000 credits (195,905)Woodall LLR Bronze: Earned 10,000 credits (40,424)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,001,667)AP 26/27 Bronze: Earned 10,000 credits (72,774)GFN Gold: Earned 500,000 credits (824,200)WW Bronze: Earned 10,000 credits (12,000)
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.

Post to thread

Message boards : General discussion : Implementing an Algorithm?

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.60, 1.73, 1.50
Generated 4 Jul 2022 | 3:36:05 UTC