mersenneforum.org > Math Speeding up 321
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2012-12-03, 16:56 #1 diep     Sep 2006 The Netherlands 2×17×23 Posts 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?
2012-12-03, 17:22   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by diep 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 .

2012-12-03, 17:42   #3
diep

Sep 2006
The Netherlands

30E16 Posts

Quote:
 Originally Posted by science_man_88 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

2012-12-03, 18:08   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by diep 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

2012-12-03, 18:17   #5
diep

Sep 2006
The Netherlands

11000011102 Posts

Quote:
 Originally Posted by science_man_88 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.

2012-12-03, 18:22   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by diep 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

 2012-12-03, 20:36 #7 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 25·11·17 Posts 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
2012-12-04, 01:07   #8
diep

Sep 2006
The Netherlands

2·17·23 Posts

Quote:
 Originally Posted by henryzz 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

 2012-12-04, 15:32 #9 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 176016 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Computer Science & Computational Number Theory 9 2016-03-29 19:00 m_f_h Math 8 2007-05-18 13:49 Unregistered PrimeNet 16 2006-02-28 02:00 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

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.

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