mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Closed Thread
 
Thread Tools
Old 2015-10-26, 01:27   #45
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts
Default

Quote:
Originally Posted by Batalov View Post
A rhetorical question if there ever was one.

Not seeing your messages saves so much of my page space!
You really needed to quote the whole message to ask [I]that[/I]?
the reason I asked it because they very slightly mentioned something in PM that was supposed to speed it up at very least.
science_man_88 is offline  
Old 2015-10-26, 01:31   #46
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

1,931 Posts
Default

Quote:
Originally Posted by alpertron View Post
Although the method generates primes as expected, the minuend and subtrahend are almost as big as in the previous version. For more interesting ranges, you should subtract extremely huge numbers and the timing would be worse than trial division.

You could use modular arithmetic in order to speed up your algorithm, but again this will be worse than trial division. Why? The union of the sets A and B must include all prime numbers below n. So you need to perform about n/log(n) multiplications mod prime greater than n2. So the number of steps is the same as the worst case of trial division. Notice also that to find a prime p<n2 first you will need to compute a prime larger than n2 in order to use it as the modulus. So again this is not useful at all.
I agree
I don't think it is necessarily worse than trial division in general though. There should be a medium range where less trials than trial division would result in primes specially if you write the routine intelligently by keeping the sums as low as possible but for very large primes the sums will diverge very rapidly.
You don't really need to calculate the base primes either. you can use the theorem to come up with solutions to that such as using double factorials of a composite odd integer, rather than primes multiplied. the double factorial can be calculated using product of sequence formula.
To further keep the sum from diverging you can factor out large number of known primes.
But all this would not do for a billion plus digits. As I mentioned before there are better approaches to this.
BTW, thank you for being one of the few intelligent posters to this thread.
a1call is offline  
Old 2015-10-26, 01:34   #47
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

1,931 Posts
Default

Quote:
Originally Posted by Batalov View Post
So, you are saying that for you method to work you need to store somewhere all primes up to 10500000000, right?
Good luck with that.
This universe is not equipped to store all primes up to 101000, is it?
Please read the red comment in my earlier post. I thought it was distinct enough. Obviously I was wrong.
a1call is offline  
Old 2015-10-26, 02:05   #48
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·7·163 Posts
Default

Quote:
Originally Posted by a1call View Post
Obviously I was wrong.
Good, we are in agreement then.
Batalov is offline  
Old 2015-10-26, 02:31   #49
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

1,931 Posts
Default

Quote:
Originally Posted by Batalov View Post
Good, we are in agreement then.
There are 3 types of people in the world. There are those who can count, and there are those who can't.
a1call is offline  
Old 2015-10-26, 03:07   #50
axn
 
axn's Avatar
 
Jun 2003

4,721 Posts
Default

Quote:
Originally Posted by a1call View Post
But all this would not do for a billion plus digits.
Understatement of the century. Your method will not scale to 20 digit primes, never mind a billion digits.
axn is online now  
Old 2015-10-26, 05:42   #51
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

This makes me think of Maurer or Shawe-Taylor methods for generating proven primes. There we get to double or triple the bits every round. One could do something similar with other BLS75 theorems (Maurer's algorithm can be seen as a case of theorem 3) or even ECPP. Just build up the proof backwards to get larger and larger numbers. It makes nice large proven primes, but I seriously doubt it would scale well to millions of digits.
danaj is offline  
Old 2015-10-26, 07:28   #52
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22·31·79 Posts
Default

Quote:
Originally Posted by a1call View Post
Theorem 1:
For the set A of n consecutive prime numbers staring from 2 and ending at Pn.
Let:
BA & C=A-B

Let the number b be equal to multiples of any-integer-power greater-than 0 of all-the-elements of B.

Let the number c be equal to multiples of any-integer-power greater-than 0 of all-the-elements of C.

Then d = b±c| is a prime number,
False. Here is a pair of simple counterexamples:

Counter #1: A = {2,3}, B = 2, C = 3. Let b = 2^1, c = 3^3. Then b+c = 29 is prime, but -b+c = 25 is not.

Counter #2: A = {2,3,5,7,11}, B = 2, C = {3,5,7,11}. Let b = 2^1, c = 3*5*7*11 = 1155. Then -b+c = 1153 is prime, but b+c = 1157 = 13*89 is not.
ewmayer is offline  
Old 2015-10-26, 07:39   #53
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·317 Posts
Default

Quote:
Originally Posted by ewmayer View Post
False. Here is a pair of simple counterexamples:

Counter #1: A = {2,3}, B = 2, C = 3. Let b = 2^1, c = 3^3. Then b+c = 29 is prime, but -b+c = 25 is not.

Counter #2: A = {2,3,5,7,11}, B = 2, C = {3,5,7,11}. Let b = 2^1, c = 3*5*7*11 = 1155. Then -b+c = 1153 is prime, but b+c = 1157 = 13*89 is not.
Won't suffice, both are higher than n^2 (in the first case 9, second case 121). What he calls "Pn2". His theorem is true, but not useful to generate primes, as Serge said, it will need to store primes to 10^500M.
LaurV is offline  
Old 2015-10-26, 07:48   #54
axn
 
axn's Avatar
 
Jun 2003

4,721 Posts
Default

Quote:
Originally Posted by ewmayer View Post
False. Here is a pair of simple counterexamples:
You've accidentally left out a critical part of the theorem (because of poor typography on OP's part, mind you)

Quote:
Then d = |±b±c| is a prime number,
∀d: d < Pn2
axn is online now  
Old 2015-10-26, 09:44   #55
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by Batalov View Post
So, you are saying that for you method to work you need to store somewhere all primes up to 10500000000, right?
Good luck with that.
This universe is not equipped to store all primes up to 101000, is it?
BTW, the idea of partitioning a set of primes into two sets and looking at combinations of products
is hardly new. See the paper "Primes at a Glance" by John Selfridge et.al.
R.D. Silverman is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really. CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
"Subproject" #10: 200k-300k to 110 digits RobertS Aliquot Sequences 9 2011-05-07 15:30
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12
Search for a number theoretic function related to "prime divisor sums" juergen Math 2 2004-07-10 23:01

All times are UTC. The time now is 13:26.

Fri Oct 30 13:26:58 UTC 2020 up 50 days, 10:37, 1 user, load averages: 3.82, 3.08, 2.85

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