Prime numbers

[Qfwfq]

But I suppose the amazing thing is that there are primes of that size at all...

It's easy to show that there are arbitrarily large primes.

 

Consider any set A of primes. If the cardinality of A is finite the product of all of them will be finite. Add 1 to this product and call the result N. None of the primes in A will be a factor of N, as they are factors of 1 less than N. Therefore the prime factors of N are not elements of A, so A cannot be the set of all primes.

 

This easily implies that there are arbitrarily large primes as an infinite set of natural numbers can't have an upper bound.

[CraigD]

If you want a very simple way to generate primes without resorting to any of the usual random guess-and-check schemes, try this:

1) (Initialize) N=2

2) N=(N-1)*N+1

3) Repeat step 2

 

N gets very big very fast:

1:3 2:7 3:43 4:1807 5:3263443 6:10650056950807 (43 bits) … 25:? (~45,000,000 bits) …

 

This algorithm is just a trivial implementation of the proof in Qfwfg’s post #18 (a proof that’s been around about 2300 years, usually credited to Euclid). Since it only generates 24 primes before generating one bigger than the current world record of 2^25964951 – 1, it’s useless for cryptography or much of anything else. It is, however, wonderfully tiny, and completely non-random.

 

PS: Alas, my tiny algorithm generates only numbers that can fool me into believing their prime! 1807=13*139.

 

It’s still wonderfully tiny, at least, and may suggest an interesting line of inquiry into prime number generators.

[Turtle]

___Nice CraigD! I amend by saying, sometimes every stone counts. :) Your tiny algorithm is useful for amendment.

[CraigD]

Alas, my tiny algorithm generates only numbers that can fool me into believing they're prime! 1807=13*139. :(

 

It’s still wonderfully tiny, at least, and may suggest an interesting line of inquiry into prime number generators. :)

[Qfwfq]

What's lacking is to factor the result.

 

I'll give it a thought, as the iteration seems like a good idea, once your results are very high they should likely have some large prime factors. I'm not sure how likely, but I'll give the idea a thought.

 

The Rabin-Miller test is a good heuristic, i. e. it's quicker to apply it before factoring for an certain determination of primality. Even if the probability of the candidate passing RM without being prime is comparable to the probability of a mistake in the factoring test, these two events are independent, so it is still makes sense statistically to try factoring candidates that pass RM.

[IDMclean]

New Pattern Found In Prime Numbers

 

Distribution of prime numbers related to the first and last digit? This seems like it will lead to a whole plethora of search strategies.

[phillip1882]

if you just want to know whether a given number is prime, the most guaranteed way, would be of course to divide by all primes less than the square root of the number.

if you are willing to gamble a little, you can use a probabilistic approach described here:

Rabin-Miller Strong Pseudoprime Test -- from Wolfram MathWorld

if your looking to generate a list of prime numbers, sieves are the best way to go.

for example if you wanted every prime number up to one million, then simply declare an array of size 1 million, eliminate all factors of 2, then all factors of 3, then all factors of 5, etc.

[Boerseun]

If you want a very simple way to generate primes without resorting to any of the usual random guess-and-check schemes, try this:

1) (Initialize) N=2

2) N=(N-1)*N+1

3) Repeat step 2

 

N gets very big very fast:

1:3 2:7 3:43 4:1807 5:3263443 6:10650056950807 (43 bits) … 25:? (~45,000,000 bits)

Hey! Awesome thread resuscitation!

 

Seems like I missed this post from Craig circa 2005...

 

I don't follow the logic here (if you don't mind me replying to a zombie thread...)

 

In the first loop, N is initialized as 2. Then, in the second line, N is N-1 (2-1=1) times 2+1 (3) which results in 3. Then the step gets repeated.

In the second loop, N is once again N-1 (3-1=2) times 3+1(4). That gives me 8. The mere fact that there's a two involved destroys what you're trying to achieve, here.

 

Man, don't Mondays suck!

[IDMclean]

This is the method I use:

[math]p[/math] is a potential number to check for primality.

For any fixed [math]i, j \in \mathbb{N}^+ \wedge f(n) = 2n + 1 \wedge i, j < (p-1)/2 \wedge g(i, j) = f(i) \circ f(j)[/math]

If [math]p = g(i, j)[/math]

[math]p[/math] is not prime.

 

A couple examples:

[math]p = 293[/math]

[math]\{i, j = (1, ... 145)\} < 146[/math]

[math]p \not= g (i,j)[/math]

[math]293[/math] is prime.

 

[math]p = 2793[/math]

[math]\{i, j = (1, ... 465)\} < 1396[/math]

[math]p = g (1, 465) = 3 \cdot 931 = 2793[/math]

[math]2793[/math] is not prime.

 

It's computationally cheaper than the trial division method. The most expensive part of the computation is checking primes because you have to go through all combinations of i and j before you know they are prime. For composites, you'll stop the moment a combination of i and j satisfies [math]g(i, j) = f(i) \circ f(j)[/math]

 

I know this check can be further optimized by discovering a method for reducing the number of combinations that need to be checked before we know that no combination of factors will ever equal p.

[CraigD]

New Pattern Found In Prime Numbers

The paper mentioned in the Slashdot discussion is available via this arxiv preprint.

 

I recommend it over most discussion threads about it, because it’s fairly non-technical and accessible to people with typical statistics backgrounds, especially those with access to good numeric analysis software, such as an easy-to-use programming language. Discussion sites sometimes go in confusing and essentially wrong directions, so can be more difficult to follow than what they’re discussing. ;)

Distribution of prime numbers related to the first and last digit?

Luque and Lacasa’s paper involves only the first digit of sample of primes and other sequences, not the last. According to the empirical generalized Benford’s law, the distribution of last digits of most number sequences is uniform – though, in the case of primes, this is obviously not the case, as only one prime, 2, has an even last digit, and only one, 5 has a last digit of 5 in base 10. The remaining base 10 last digits, 1, 3,7 and 9, appear uniformly distributed.

This seems like it will lead to a whole plethora of search strategies.

I don’t see any obvious applications of a Benford’s law variation for generating primes of factoring composites. It immediately gives a means of determining if a particular sequence consists of more primes than a random sequence, but as best I can tell with a quick analysis, using this to test prime candidates is much less efficient than other common methods, such as Rabin-Miller.

 

The paper’s a must-read for the prime-obsessed, however, as everything about primes is a must-read for the prime obsessed. :confused: Speaking of which, for any prime-obsessed readers, especially beginners in the subject, John Derbyshire’s Prime Obsession is, IMHO, a must read (no matter what you may think of John Derbyshire).

[CraigD]

If you want a very simple way to generate primes without resorting to any of the usual random guess-and-check schemes, try this:

1) (Initialize) N=2

2) N=(N-1)*N+1

3) Repeat step 2

 

N gets very big very fast:

1:3 2:7 3:43 4:1807 5:3263443 6:10650056950807 (43 bits) … 25:? (~45,000,000 bits)

I don't follow the logic here (if you don't mind me replying to a zombie thread...)

Being more explicit with parenthesis, step 2 would read: N=((N-1)*N)+1

 

So, starting with 2,

((2-1)2)+1 = 3

((3-1)3)+1 = 7

((7-1)7)+1 = 43

((43-1)43)+1 = 1807

etc.

 

The proof is left as an exercise to the reader :confused:

[CraigD]

This is the method I use

…

I think you only need to check the two or three highest numbers satisfying [math]f(n) \leq \sqrt{p}[/math].

I quickly found a couple of counter example to this:

[math]7429 = 17 \cdot 19 \cdot 23[/math]

and

[math]9367 = 17 \cdot 19 \cdot 29[/math]

 

Unless the method is really as failure-prone as it appears, I must misunderstand it. :confused:

[IDMclean]

I quickly found a couple of counter example to this:

[math]7429 = 17 \cdot 19 \cdot 23[/math]

and

[math]9367 = 17 \cdot 19 \cdot 29[/math]

 

Unless the method is really as failure-prone as it appears, I must misunderstand it. :confused:

 

The problem is you have three factors. The method only allows for two factors; hence, i and j.

 

I just figured out where I made an inductive leap. I need to reformulate the above method to check for any product combination of the list of possible factors. :doh:

 

I've only been generating prime number lists with my method. I'm still getting my grip on using the math to check for primality.

 

Thank you CraigD as usual,

The Clown.

[Boerseun]

Being more explicit with parenthesis...

...

((3-1)3)+1 = 7

...

The proof is left as an exercise to the reader :confused:

Whoops! I did not see the +1 bit when I calculated the second loop.

 

Told ya Mondays suck. And I haven't even had coffee yet!