mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-03-05, 18:49   #1
jovada
 
Aug 2016

2×3 Posts
Default Prime next to multiple of 6

I'm not a mathematician, but I just saw a Tweet by fermatslibrary stating that
every prime is next to a multiple of 6. Isn't this a way faster way of figuring out whether a number is prime or not, instead of attacking it with lengthy tests?
https://primes.utm.edu/notes/faq/six.html
jovada is offline   Reply With Quote
Old 2022-03-05, 19:05   #2
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

22·7·132 Posts
Default

Quote:
Originally Posted by jovada View Post
I'm not a mathematician, but I just saw a Tweet by fermatslibrary stating that
every prime is next to a multiple of 6. Isn't this a way faster way of figuring out whether a number is prime or not, instead of attacking it with lengthy tests?
https://primes.utm.edu/notes/faq/six.html
I'm not a mathematician, either, but whether this is true or not, it wouldn't mean that every number next to a multiple of 6 is prime. In fact, this is not the case. e.g. 25 is next to 24, but is clearly not prime.
EdH is offline   Reply With Quote
Old 2022-03-05, 19:12   #3
slandrum
 
Jan 2021
California

23×5×11 Posts
Default

Quote:
Originally Posted by jovada View Post
I'm not a mathematician
Clearly

Quote:
I just saw a Tweet by fermatslibrary stating that
every prime is next to a multiple of 6. Isn't this a way faster way of figuring out whether a number is prime or not, instead of attacking it with lengthy tests?
https://primes.utm.edu/notes/faq/six.html
No, all primes above 2 are odd. Therefore every prime (above 2) has to be 6n+1, 6n+3 or 6n+5. 3 is the only prime that's 6n+3 because all numbers of the form 6n+3 are divisible by 3. Therefore all primes above 3 are 6n+1 or 6n+5 (6n+5 is equivalent to 6n-1) so all prime numbers above 3 must be adjacent to a multiple of 6. There's nothing earth shattering about this.
slandrum is offline   Reply With Quote
Old 2022-03-06, 15:41   #4
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts
Default

For any positive integer n, all primes not dividing n are coprime to n, and the remainder of them to n must be in the reduced residue system mod n, e.g. for n=15, the reduced residue system is {1, 2, 4, 7, 8, 11, 13, 14}, and for your case of n=6, the reduced residue system is {1, 5}, thus all primes p not dividing 6 must == 1 or 5 mod 6, and if p == 1 mod 6, then p-1 is multiple of 6, if p == 5 mod 6, then p+1 is multiple of 6, thus all primes p not dividing 6 (i.e. other than 2 and 3) are next to multiple of 6
sweety439 is online now   Reply With Quote
Old 2022-03-11, 11:21   #5
jovada
 
Aug 2016

2×3 Posts
Default

Quote:
Originally Posted by slandrum View Post
Clearly
Thanks for being so polite.

And you just re-iterated my statement, however I was looking for an answer to the question whether it would be easier to test first if a given assignment is indeed of the form 6n+1 or 6n-1, instead of brutally attacking it with a lengthy test.
Assuming that checking the 6n+1 or 6n-1 is less brutal off course.
jovada is offline   Reply With Quote
Old 2022-03-11, 13:37   #6
Dobri
 
"Καλός"
May 2018

2×52×7 Posts
Default

Quote:
Originally Posted by jovada View Post
..., however I was looking for an answer to the question whether it would be easier to test first if a given assignment is indeed of the form 6n+1 or 6n-1, instead of brutally attacking it with a lengthy test.
Assuming that checking the 6n+1 or 6n-1 is less brutal off course.
Concerning the exponents of known Mersenne primes, except for the exponents 2 and 3, 24 exponents are of the type 6k+1 and 25 exponents are of the type 6k-1, see https://mersenneforum.org/showpost.p...1&postcount=37.


However, as stated by drkirkby in another thread, within the known sample size there are "more twin primes below Mersenne exponents than above Mersenne exponents", see https://mersenneforum.org/showthread.php?t=26812 and OEIS346645.
Dobri is offline   Reply With Quote
Old 2022-03-11, 16:04   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

538910 Posts
Default

Quote:
Originally Posted by jovada View Post
Thanks for being so polite.

And you just re-iterated my statement, however I was looking for an answer to the question whether it would be easier to test first if a given assignment is indeed of the form 6n+1 or 6n-1, instead of brutally attacking it with a lengthy test.
Assuming that checking the 6n+1 or 6n-1 is less brutal off course.
As Slandrum explained to you a couple posts ago, you are asking if candidates should be trial-divided by 2 and 3 before doing a primality test. It seems you have no idea what sieving or trial-factoring is- so, the answer to your question is "yes". Yes, we check whether a number is even before doing a primality test. We also check whether it is divisible by 3, and 5, and quite a few more primes, before brutally (?) running a lengthy algorithm.
VBCurtis is offline   Reply With Quote
Old 2022-03-12, 19:56   #8
Dobri
 
"Καλός"
May 2018

15E16 Posts
Default

Quote:
Originally Posted by jovada View Post
..., however I was looking for an answer to the question whether it would be easier to test first if a given assignment is indeed of the form 6n+1 or 6n-1,...
Note that 2p - 1 = 6n + 1 for all odd positive integers p = 1, 3, 5, 7, 9,...
because 2p - 1 = (2 - 1)(2p-1 + 2p-2 + ... + 22 + 21 + 20) = ((3-1)p-1 + (3-1)p-2) + ... + ((3-1)2 + (3-1)1) + 1
and after applying the binomial theorem (see https://en.wikipedia.org/wiki/Binomial_theorem)
the terms (1p-1 - 1p-2) + ... + (12 - 11) within the parentheses cancel each other.
Dobri is offline   Reply With Quote
Old 2022-03-12, 20:50   #9
slandrum
 
Jan 2021
California

23×5×11 Posts
Default

Well, if you are going to specifically talk about Mersenne primes, the candidates can't have any "small" factors (like 3) because all factors of 2^p-1 are of the form 2kp+1, so when looking at Mersenne candidates with exponents over 100 million (which is the low end of the search right now), the smallest possible factor will be over 200 million.

But there are lots of other types of primes that people are looking for, that's just the main project.
slandrum is offline   Reply With Quote
Old 2022-03-13, 02:20   #10
tuckerkao
 
"Tucker Kao"
Jan 2020
Head Base M168202123

2F016 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
As Slandrum explained to you a couple posts ago, you are asking if candidates should be trial-divided by 2 and 3 before doing a primality test. It seems you have no idea what sieving or trial-factoring is- so, the answer to your question is "yes". Yes, we check whether a number is even before doing a primality test. We also check whether it is divisible by 3, and 5, and quite a few more primes, before brutally (?) running a lengthy algorithm.
Any exponents or the numbers themselves divisible by 2 or 3 can be easily identified with the last digit. Factors of 5 or 7 can be trial divided within the matter of seconds from the trial factoring software. The GPU trial factoring usually refer to the factors of the numerical sizes of quadrillions to quintillions before the PRP tests which run the lengthy algorithm.
tuckerkao is offline   Reply With Quote
Old 2022-03-13, 03:05   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

17·317 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
Any exponents or the numbers themselves divisible by 2 or 3 can be easily identified with the last digit.
As usual, you reply to a post with incorrect mathematical content.

Or, please tell us how the last digit allows you to identify whether a number is divisible by 3.

Here are numbers not divisible by 3: 10, 11, 22, 23, 34, 35, 46, 47, 58, 59. There's all ten last digits. So, explain.

Last fiddled with by VBCurtis on 2022-03-13 at 03:06
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How do I calculate chances of finding a prime, while testing multiple exponents? drkirkby Math 4 2021-04-13 12:58
Linux and multiple GPU bgbeuning GPU Computing 52 2016-06-09 05:26
Using multiple PCs numbercruncher Information & Answers 18 2014-04-17 00:17
Are multiple gpu's necessary for CUDA... WraithX GPU Computing 16 2012-03-22 10:44
Multiple systems/multiple CPUs. Best configuration? BillW Software 1 2003-01-21 20:11

All times are UTC. The time now is 03:14.


Fri Aug 19 03:14:30 UTC 2022 up 1 day, 43 mins, 0 users, load averages: 0.98, 1.28, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔