Prime generation method

mathsyperson · 2010-11-06 01:33:07

I came across this method of generating prime numbers recently.

It can be used to list every prime there is, in order, with nothing else.
It's too slow to have useful applications, but I thought it was really interesting, and my mind boggles at the fact that it works at all.

Here is a list of fractions that makes it work:

17/91

78/85

19/51

23/38

29/33

77/29

95/23

77/19

1/17

11/13

13/11

15/2

1/7

55/1

Using this list, you generate a sequence in the following way:

The first element of the sequence is 2.
To get from one element of the sequence to the next, you start at the top of the list of fractions, and try multiplying by each one in turn. The next member of the sequence is the first integer you get as a result.

So, all of the fractions from 17/91 down to 13/11 will not produce integers when multiplied by 2.
However, the next one produces 15, and so that is the next element in the sequence.

The sequence starts like this:

2, 15, 875, 725, 1925, 2275, 425, ...

The interesting part is that every so often, an element of the sequence will be a power of 2.
If you ignore all elements of the sequence other than powers of 2 (and also ignore the first 2), you get this:

2^2, 2^3, 2^5, 2^7, 2^11, ...

That is, the powers of two that are produced are precisely the list of prime numbers.

Like I said, this works far too slowly to have any actual use.
Generating the first thousand terms of this sequence will just get you 2, 3, 5, 7.
Generating the first million will list the primes up until 89.

I still think it's neat though.

MathsIsFun · 2010-11-06 09:29:14

Dare I ask why it works?

John E. Franklin · 2010-11-09 02:08:48

...so if we do this in binary, the power of 2 will be easier to detect as it will be a 1 followed by several zeros, and the number of zeros will be the prime number, is that correct?

John E. Franklin · 2010-11-09 03:37:56

...also I computed the 2, 15, 825, and 725 by looping around the list of fractions...
Are you suppossed to loop around continuously, or should you jump to the first fraction
after you find an integer and skip the remaining fractions below in the list?
Also do you know the author of this creation?

mathsyperson · 2010-11-13 01:29:08

I found that it was easier to write numbers in terms of their prime factors.
When I wrote my code to write the first million terms, I used vectors.

The first term is [1,0,0,0,0,0,0,0,0,0].

Then it goes to [0,1,1,0,0,0,0,0,0,0]
Then [0,1,2,0,1,0,0,0,0,0], and so on.

The nth element of the vector means that the number contains that many powers of the nth prime.
You can tell by looking that no number in the sequence will ever have a prime factor higher than 29, which is why we can have length-10 vectors.

A number in the sequence will be significant if and only if all elements of the vector except the first are equal to 0. [In the code, I used A(1) == sum(A)]

To answer your other questions, you should always jump back to the top of the list. So if a number is divisible by 91, you should always multiply it by 17/91.

And the method was designed by John Conway.

I probably should have given my source in the first place, so here it is.
(The closest I am to solving that is figuring out a likely order of magnitude though)

Math Is Fun Forum

#1 2010-11-06 01:33:07

Prime generation method

#2 2010-11-06 09:29:14

Re: Prime generation method

#3 2010-11-09 02:08:48

Re: Prime generation method

#4 2010-11-09 03:37:56

Re: Prime generation method

#5 2010-11-13 01:29:08

Re: Prime generation method

Board footer