Speeding up 321

diep · 2012-12-03, 16:56

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?

science_man_88 · 2012-12-03, 17:22

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 .

diep · 2012-12-03, 17:42

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 ?

science_man_88 · 2012-12-03, 18:08

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.

diep · 2012-12-03, 18:17

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.

science_man_88 · 2012-12-03, 18:22

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

henryzz · 2012-12-03, 20:36

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$

diep · 2012-12-04, 01:07

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 :)

henryzz · 2012-12-04, 15:32

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.

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, 20:36	#7
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 2⁵·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 $32^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: $k2^n+2^{n-m}\pm1 = (k2^m+1)2^{n-m}\pm1$ and $2^n\pm k2^{n-m}\pm1 = (2^m\pm k)2^{n-m}\pm1$ I wonder if a primality test is possible for any $k2^n+j2^{n-m}\pm1$ Last fiddled with by henryzz on 2012-12-03 at 21:34*

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

2012-12-04, 15:32	#9
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 1760₁₆ Posts	Should have spotted this last night. $k2^n\pm j2^{n-m}\pm1=(k2^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.