mersenneforum.org The "one billion minus 999,994,000" digits prime number
 Register FAQ Search Today's Posts Mark Forums Read

2015-10-26, 01:27   #45
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts

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

2015-10-26, 01:31   #46
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

1,931 Posts

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

2015-10-26, 01:34   #47
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

1,931 Posts

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

2015-10-26, 02:05   #48
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·7·163 Posts

Quote:
 Originally Posted by a1call Obviously I was wrong.
Good, we are in agreement then.

2015-10-26, 02:31   #49
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

1,931 Posts

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

2015-10-26, 03:07   #50
axn

Jun 2003

4,721 Posts

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

 2015-10-26, 05:42 #51 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2×3×151 Posts 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.
2015-10-26, 07:28   #52
ewmayer
2ω=0

Sep 2002
República de California

22·31·79 Posts

Quote:
 Originally Posted by a1call Theorem 1: For the set A of n consecutive prime numbers staring from 2 and ending at Pn. Let: B⊂A & 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.

2015-10-26, 07:39   #53
LaurV
Romulan Interpreter

Jun 2011
Thailand

22·7·317 Posts

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

2015-10-26, 07:48   #54
axn

Jun 2003

4,721 Posts

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

2015-10-26, 09:44   #55
R.D. Silverman

Nov 2003

26×113 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 RobertS Aliquot Sequences 9 2011-05-07 15:30 nitai1999 Software 7 2004-08-26 18:12 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