Method for generating prime numbers

Post Reply New Topic

If my method turns out not to be much, I will demonstrate it here. I am working with someone to explore it further. Fuleri's formulation approaches my simplicity, but is not like my method at all.

Rethinking: Fuleri's equation is beginning to look a lot like an equivalent statement. I'll be back.

Last edited by jackmt on 19 Feb 2012, 2:09 pm, edited 1 time in total.

i do not have enough time to explore some methods i am interested in.

i would like to make a number pyramid )where 1 is the apex and 2 and 3 are the second row and 4,5,and 6 are the third row etc, and i would like to make the base of the pyramid 1 million numerals or more, and then plot all the prime number positions within that pyramid to see if there is some sort of trigonometrical recursive rule in the positions of the prime number plots in a vectorial sense.
there must be some pattern that can be found in a pyramid of numbers with precalculated (using simple ways) primes highlighted that can yield a law that is true for prediction of other highlightable points not yet assessed using trigonometry.

i have a business to run and dollars to make and a tummy to fill with food, and i have a brain that needs sleep, but soon i will look at the problem further, and i will give up then.

There isn't. People tend to look at primes in the wrong way - they aren't following a pattern. They are what's left when you take away the pattern. Unfortunately this means we can't predict them!

My little snippet earlier (I didn't invent it, by the way) won't report all prime numbers, but it IS a way you can potentially cut down on the ones to check. Rather than looking at every number up to N, you can simply look at every n and n+2 up to N, where n starts at 5 and goes up by 6 each iteration. That could make things faster.

You can also ignore any even numbers other than 2, of course, but the above suggestion already does.

Nobody believes that the prime numbers are random! They are obviously deterministic.

But they are pseudorandom, in many senses. This isn't just an opinion, it has been proven.

Technically, they are emergent. That is, they are determined - but the only way to work them out is to go through from the beginning.

@jackmt: I think I have a pretty good test for your method.

I'm going to abbreviate 1 billion as b.

There are 3 primes between b+100 and b+200, 21 primes between 100 and 200, and 12 between 1100 and 1200. If your method is similar to previously known methods, it will generate closer to 21 or 12 candidates than 3 over the b+100 to b+200 range.

There are approximately n/(ln n) primes less than n, so we can get the approximate number of primes in a range by hi/(ln hi) - lo/(ln lo), which is about 4.59 over 100 integers near a billion. So from b+100 to b+200, we have slightly fewer than expected, but over b to b+100 there are 7 primes, so a few more than expected.

I'm not sure what you mean by this. If you mean "it is impossible to check whether a number n is prime without first checking whether all numbers less than n are prime", then it is false.

For example, to check whether 1031 is prime, we might just go through all the numbers from 2 to floor(1031/2), and check whether they are factors of 1031. We don't ever have to check whether 1029 is prime.

The range should be from 2 to floor (sqrt (1031)).

ruveyn

Sure, that's an even cleverer way to do it. But I wasn't trying to give the cleverest possible way, I was just trying to show that it is possible to check whether a number is prime without first checking whether every number below it is prime.

I'm working on the assumption that you are actually looking for all the primes. Testing a single number is straightforward (though if you already have a list of primes below that number, it's a lot quicker).

I'm trying to understand what you meant by



It seems like an interesting thing to say, but I'm not sure what it means. Could you express it more carefully?

The only two readings that I can think of are "In order to find all of the primes from 1 to N, you need to find all of the primes from 1 to N", which is trivial, and "In order to check whether N is a prime, you need to check whether every number below N is a prime", which is false.

Another might be: in order to find all the primes less than n, you either have to check whether any of the primes below sqrt(n) divides the number (without skipping any of the primes < sqrt(n)), or else you have to do something else that is at least as complicated.

I guess you made a typo and actually meant: "in order to check whether n is prime, ..."

This is definitely a good reading. However, it isn't true, at least if "complicated" is measured in terms of asymptotic time complexity.

http://en.wikipedia.org/wiki/AKS_primality_test

This is a way to check whether or not a number is prime that is actually asymptotically quicker than finding out whether or not every number from 1 to sqrt(n) goes into n.

You talked about finding out whether every prime from one to sqrt(n) goes into n, as opposed to every number. But this is begging the question, isn't it? An algorithm for determining primality shouldn't already know which numbers are prime, that's cheating.

Wait, I just thought of a good reading for it! It's actually really simple.

What we are trying to say is:

In other words, it is generally easier to check the primality of small numbers than it is to check the primality of large ones.

I think that this statement is definitely true.

After discussing my method with someone tonight I was about to give up, thinking I was right at first to have thought it wasn't anything more than interesting. Then after awhile it occurred to me how to make it even simpler: generate any n length number x and check if it has the prime property. This can be done while the number is being generated. If so, check for prime factors 7 to x/14. If not, apply my trick and check for prime factors 7 to x/14. This will produce about n^2+n prime candidates, most of which (I believe about 88%. I will get back.) will be prime.

Is this anything?

Last edited by jackmt on 20 Feb 2012, 1:17 am, edited 3 times in total.

Nope. I think a bit in the middle of what I said might have been unclear, but I was definitely talking about finding all primes < n.


If you used AKS to find them all from 2 to n, then you'd have AKS(2), AKS(3) ... AKS(n-1), AKS(n), which would probably be a lot slower.


Yes, it is cheating. It's my favorite type of cheating: recursion.

Say we want to build a function that returns every prime <= n. It will return a list of primes. We'll call it like this: list = primes(n). We'll write lists as something like this: [1,2,3], and empty lists as [].

For the algorithm, we'll just use what I suggested before, and we'll have a helper function indivisible(list, n) that returns true if none of the numbers in the list evenly divides n.



If we call primes(100), it calls primes(10), which calls primes(4), which calls primes(2), which calls primes(1), which returns an empty list. So primes(2) dutifully checks all numbers from 2 to 2 for any numbers in an empty list which evenly divide 2. Finding none, it puts 2 in the list and returns it. Then primes(4) checks from 3 to 4 using [2], and puts 3 in the list. Primes(10) checks from 5 to 10 using [2,3], and puts 5 and 7 in the list, which it hands to primes(100), which checks from 11 to 100 with the list [2,3,5,7], and gives us the list of primes we want.

Basically, it works because we're not asking for the whole list of primes, just a smaller sublist, and eventually you get down to a simple situation where you immediately know the answer. (An empty list contains every prime < 2)