Could this be used to iteratively figure out primes?

Factual Questions
1

This probably isn’t a real good way to figure out primes, but it’s something I’ve wondered about for a while and I thought some of the math experts here might know more about it.

If you take the function:

sin((x-p) * pi/2p)

where p is a prime number, you’ll get a function which is equal to zero whenever x is odd and a multiple of p. For example:

sin((x-3) * pi/6) is 0 at 3, 9, 15, 21, …
sin((x-5) * pi/10) is 0 at 5, 15, 25, 35, …
sin((x-7) * pi/14) is 0 at 7, 21, 35, 49, …

These functions avoid the even multiples of a number since I was just wanted to find odd numbers. So just 3,9,15,21 instead of 3,6,9,12,15,18,21.

Given the three equations above, the way to figure out the next prime would be to find the odd value of x greater than the greatest prime we already know (7) where all the known equations do not equal 0. For example, 9 is out because the equation for 3 is zero at 9. The next value that works is 11. None of the above equations equal 0 for x=11. Furthermore, all the odd values of x between 11 and 33 (11 + 2*11) which do not evaluate to 0 from all the known equations will also be prime. If you graph out the three equations above you’ll see this as the x values between 11 and 33 where no sine curve goes through it.

There’s not any magic going on here since essentially all that’s happening is that the prime multiples are being scratched off the x axis. Figuring out primes this way would not be very efficient. You’d have one equation for each number and it’d be much simpler to just do the straight division.

But the thing I was wondering is if all the equations can be combined somehow into one equation that can be used to iteratively figure out the next prime. For example, knowing that 3,5,7, and 11 are prime, can a single equation be created which equals 0 at all those values and all multiples of those values. Like in this made up equation:

sin( (x - 35711 ) * pi/(2357*11))

(That’s not the right equation, but hopefully you get the idea.)

So as I figure out each successive prime, I tweak the single equation to include that prime. This would give me an efficient mechanism to find all the prime numbers up to some maximum.

So anyway, I was wondering if there’s anything to all that. I’m not a math expert so feel free to tell me I’m bonkers.

2

Since we already know how to generate all primes in sequence quite efficiently, what is the possible advantage of your method??? Are actually suggesting that finding the sine of large numbers is a basic step?

Note: generating all primes in order is trivial. Determining if a very large number is prime is a bit on the hard side. The former is a homework problem, the latter is a research problem.

3

A simple iterative approach that does not require trigonometric functions is to take the first n primes:

p1, p2, p3, … pn

and to test a particular value T for primailty, test for division without remainder against p1, p2, … pk, where pk is less than or equal to the square root of T. If any of p1 through pk divides T evenly, then T is not prime, else T is prime. If you do this by testing T=pn+1, T=pn+2, and so forth until T bcomes prime, then T becomes the very next prime in the list, and so becomes p(n+1), and the process can start again.

Its by no means the fastest mechanism for huge primes, but it describes an iterative approach to finding primes based on the previous primes, as you’ve outlined.

However, your solution most resembles the Sieve of Eratosthenes. Up to some limit N, you write down all the integers. Starting at 2, you can circle 2, and then cross off the multiples after that. You then circle the next non-crossed-off-value, 3, and cross off the multiples after that. You then circle the next non-crossed-off-value, 5, and cross off the multiples after that, and so on. The values that ‘fall through’, and are circled, are the primes.

However, I don’t agree with ftg… even new methods that have no inherent speed advantage over existing methods may yield new clues or techniques, so I suggest you keep at it. :slight_smile:

Seems to me, though, that finding the zeros of this complex equation you propose would be brutally more difficult than other methods available at the low primes.

4

The point of my post was to see if it could lead to an efficient method. I understand that the method I described was horribly inefficient. I was wondering if someone with more math experience would have an insight on how to get the same results by combining all the equations in an efficient manner. I don’t know enough about trig functions to simplify the equations.

5

What makes you think this characterizes primes? Are you trying to claim that
sin((x-9)*(pi/18)
is not 0 when x = 9, 27, 45,…? Since sin vanishes at every multiple of pi, this has nothing to do with primes. There are many reasonably efficient ways of finding primes, including just taking an odd number and applying some of the well-known tests involving elliptic curves. There is also an even simpler test that is nearly certain, but not quite.

6

Finding all primes up to n: The standard seive method is quadratic. Time proportional to n[sup]2[/sup]. Using linked lists and other standard tricks can drop the time down to linear. Given the density of primes, you can’t really do a lot better than that.

7

The other problem you would run into implementing this method is floating point error. Is sin(x) = 0, or is it very close to 0? Unless you’re willing to devote a lot of work to it, you won’t be able to tell.

8

ultrafilter is right: The epsilon of whatever machine you’re using (be it hand calculator or beowulf cluster of nitrogen-cooled supercomputers) might be high enough to give you false zeroes on these equations. Floating-point math is not very precise, even if you’re using a relatively good machine.

Anyway, an interest in math is its own reward, IMHO. :slight_smile: Just don’t get your hopes too high. We can’t all be John Nash or Ramanujan.