mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-12-03, 16:56   #1
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2×17×23 Posts
Default Speeding up 321

For the search 3 * 2^n - 1
I noticed the formula some similarity to Mersenne just of course that factor 3.

So maybe there is some additional logics possible.

3 * 2^n - 1 = 2^(n+1) + 2^n - 1

So in fact our 'n' should be 2x larger.

Maybe idea is speedup search by just checking all exponents n which holds true that 2n + 1 = prime

I checked that for the big exponents a number of them indeed is prime. 3 out of 4 i checked. Didn't check rest.

So it's a heuristic, not absolute truth.

Then we also initially just search for numbers n that are multiple of 5, though this is much weaker heuristic so maybe ignore that one at later stage.

Maybe can find quickly some prime numbers.

Idea for primegrid to filter those out and do those first?
diep is offline   Reply With Quote
Old 2012-12-03, 17:22   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by diep View Post
For the search 3 * 2^n - 1
I noticed the formula some similarity to Mersenne just of course that factor 3.

So maybe there is some additional logics possible.

3 * 2^n - 1 = 2^(n+1) + 2^n - 1

So in fact our 'n' should be 2x larger.

Maybe idea is speedup search by just checking all exponents n which holds true that 2n + 1 = prime

I checked that for the big exponents a number of them indeed is prime. 3 out of 4 i checked. Didn't check rest.

So it's a heuristic, not absolute truth.

Then we also initially just search for numbers n that are multiple of 5, though this is much weaker heuristic so maybe ignore that one at later stage.

Maybe can find quickly some prime numbers.

Idea for primegrid to filter those out and do those first?

3*2^n-1 is not 3*(2^n-1) , please follow PEDMAS , all n>0 create values that are 5 mod 6 .
science_man_88 is offline   Reply With Quote
Old 2012-12-03, 17:42   #3
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

30E16 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
3*2^n-1 is not 3*(2^n-1) , please follow PEDMAS , all n>0 create values that are 5 mod 6 .
I assume escaped your mind that

2n + 1 is prime for 3 out of 4 with n being: 2312734, 3136255, 4235414, 6090515

The idea is to speedup prime search by using heuristics - producing heuristics my expertise yet in math is bit more complicated thanks to all the math rules it follows usually :)

What's odds that if you pick 4 random numbers of 7 digits that 3 out of 4 of them are prime for 2n+1 ?

Last fiddled with by diep on 2012-12-03 at 17:45
diep is offline   Reply With Quote
Old 2012-12-03, 18:08   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by diep View Post
I assume escaped your mind that

2n + 1 is prime for 3 out of 4 with n being: 2312734, 3136255, 4235414, 6090515

The idea is to speedup prime search by using heuristics - producing heuristics my expertise yet in math is bit more complicated thanks to all the math rules it follows usually :)

What's odds that if you pick 4 random numbers of 7 digits that 3 out of 4 of them are prime for 2n+1 ?
n=3*2^(n-1) also it may be in some subgroup of n's but according to your math (3*(100/2))/4 = 37.5 primes under 100 that are odd. so with 2 there should be ~38 which when plugged in gives us 163 as the 38th prime.

Last fiddled with by science_man_88 on 2012-12-03 at 18:11
science_man_88 is offline   Reply With Quote
Old 2012-12-03, 18:17   #5
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

11000011102 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
n=3*2^(n-1) also it may be in some subgroup of n's but according to your math (3*(100/2))/4 = 37.5 primes under 100 that are odd. so with 2 there should be ~38 which when plugged in gives us 163 as the 38th prime.
I'm suggesting a way to heuristically speedup 321 and they're not busy with exponents under 100.

Go take your medicine and redo your math with 7 or 8 digit numbers please.
diep is offline   Reply With Quote
Old 2012-12-03, 18:22   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by diep View Post
What's odds that if you pick 4 random numbers of 7 digits that 3 out of 4 of them are prime for 2n+1 ?
I get (.12463044444)^4 which I get back as about 241 in a million
science_man_88 is offline   Reply With Quote
Old 2012-12-03, 20:36   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

25·11·17 Posts
Default

I wonder whether it would be possible to make a primality test for all Solinas primes.
Obviously 2^{n+1}+2^n\pm1 is in reality just 3*2^n\pm1.

I just worked out that 2^n\pm2^{n-m}\pm1 = (2^m\pm1)*2^{n-m}\pm1
This means that all Solinas primes are Riesel/Sierpinski primes. Solinas primes can all be proven prime by the same means. If (2^m\pm1) > 2^{n-m} then the llr and proth tests won't work. A N+1 or N-1 test can be used. (2^m\pm1) might need to be partially factored.

edit: In fact this can be generalized further to:
k*2^n+2^{n-m}\pm1 = (k*2^m+1)*2^{n-m}\pm1
and 2^n\pm k*2^{n-m}\pm1 = (2^m\pm k)*2^{n-m}\pm1

I wonder if a primality test is possible for any k*2^n+j*2^{n-m}\pm1

Last fiddled with by henryzz on 2012-12-03 at 21:34
henryzz is offline   Reply With Quote
Old 2012-12-04, 01:07   #8
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2·17·23 Posts
Default

Quote:
Originally Posted by henryzz View Post
I wonder whether it would be possible to make a primality test for all Solinas primes.
Obviously 2^{n+1}+2^n\pm1 is in reality just 3*2^n\pm1.

I just worked out that 2^n\pm2^{n-m}\pm1 = (2^m\pm1)*2^{n-m}\pm1
This means that all Solinas primes are Riesel/Sierpinski primes. Solinas primes can all be proven prime by the same means. If (2^m\pm1) > 2^{n-m} then the llr and proth tests won't work. A N+1 or N-1 test can be used. (2^m\pm1) might need to be partially factored.

edit: In fact this can be generalized further to:
k*2^n+2^{n-m}\pm1 = (k*2^m+1)*2^{n-m}\pm1
and 2^n\pm k*2^{n-m}\pm1 = (2^m\pm k)*2^{n-m}\pm1

I wonder if a primality test is possible for any k*2^n+j*2^{n-m}\pm1
Maybe you'll find one Henry.

Note i wrote the expression in 2^(n+1) + 2^n - 1 in order to get to the 2n + 1 as heuristic to dig up some of the gold quicker, no other reasons.

321 is binary 0b101111...111111 so it's pretty trivial that if we take the 2 top bits which is 10 that this represents 3-1 so that's 3 * 2^n -1

As we are just 1 bitflip away from having a mersenne here, and Mersenne has a fast way of trial factoring and also for its exponents only prime numbers apply, i wonder which clever constraints are there for 321 formula.

Now several Paul Underwoods, from which i met a few, have been sitting there in cabins at several locations in the UK pondering about this for years, so maybe there is no clever trick out there unlike with Mersenne.

Of course the dark december months are a good excuse to reevaluate all this again :)

Last fiddled with by diep on 2012-12-04 at 01:21
diep is offline   Reply With Quote
Old 2012-12-04, 15:32   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

176016 Posts
Default

Should have spotted this last night.
k*2^n\pm j*2^{n-m}\pm1=(k*2^m\pm j)*2^{n-m}\pm1
Assuming (k*2^m\pm j) is small/factorable enough it is now in N-1 or N+1 test form.
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Speeding up (n mod m) for very large fixed n and varying smaller m mickfrancis Computer Science & Computational Number Theory 9 2016-03-29 19:00
Speeding up Mersenne hunting m_f_h Math 8 2007-05-18 13:49
Speeding up double checking when first test returns "prime" Unregistered PrimeNet 16 2006-02-28 02:00
Speeding up ECM 10x clowns789 Software 2 2004-08-11 03:45

All times are UTC. The time now is 00:10.


Fri May 20 00:10:32 UTC 2022 up 35 days, 22:11, 2 users, load averages: 1.52, 1.34, 1.25

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.

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