The "one billion minus 999,994,000" digits prime number

[science_man_88]

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.

[a1call]

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 n². So the number of steps is the same as the worst case of trial division. Notice also that to find a prime p<n² first you will need to compute a prime larger than n² 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]

Originally Posted by Batalov

So, you are saying that for you method to work you need to store somewhere all primes up to 10^500000000, right?
Good luck with that.
This universe is not equipped to store all primes up to 10¹⁰⁰⁰, is it?

Please read the red comment in my earlier post. I thought it was distinct enough. Obviously I was wrong.

[Batalov]

Originally Posted by a1call

Obviously I was wrong.

Good, we are in agreement then.

[a1call]

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.

[axn]

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.

[danaj]

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.

[ewmayer]

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.

[LaurV]

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.

[axn]

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)

Then d = |±b±c| is a prime number,
∀d: d < Pn2

[R.D. Silverman]

Originally Posted by Batalov

So, you are saying that for you method to work you need to store somewhere all primes up to 10^500000000, right?
Good luck with that.
This universe is not equipped to store all primes up to 10¹⁰⁰⁰, 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.