some random dude

somerandomdude wrote:

ah yes, since my name has been registered for many years...btw, why are you using my name?

for the life of me I couldn't understand why somebody wanted me to answer something about primers...i do medicine, not math. :)

cheers, dude-

Yeah, for a moment I thought you were asking the question, and I was seriously concerned.

it may be cold here in abq but not cold enough to mess w/ my head like that....now boston on the other hand.... :)

SpaceOdyssey wrote:

Wise Guy wrote:

I don't know if you found this, but if you write out integers in a counterclockwise spiral, there will be many more prime numbers along the diagonals. It's called the Ulam Spiral.

http://www.hermetic.ch/pns/pns.htm

Interestingly, the sci-fi novelist Arthur C. Clarke unwittingly (sort of) described the Ulam Spiral in a novel a few years before Ulam discovered it.

What book was this described in??? I've read a lot of Arthur C. Clarke but don't remember this, but it's been a few years since I've read them...

The City and the Stars, about 50 pages in: "Jeserac sat motionless within a whirlpool of numbers. The first thousand primes.... Jeserac was no mathematician, though sometimes he liked to believe he was. All he could do was to search among the infinite array of primes for special relationships and rules which more talented men might incorporate in general laws. He could find how numbers behaved, but he could not explain why. It was his pleasure to hack his way through the arithmetical jungle, and sometimes he discovered wonders that more skillful explorers had missed. He set up the matrix of all possible integers, and started his computer stringing the primes across its surface as beads might be arranged at the intersections of a mesh."

I know, it only sort of (at best) describes the Ulam spiral, but it is still sort of cool.

Buttsniffer wrote:Since we are in polite company, that's Dr. Buttsniffer to you. You can send me my Fields medal later, thanks.

Haha, it's Dr. some random dude too, but not in math. I'm working on trying to describe what I see a little more formally in as concise a way as I can, and can try to share something later when I'm a little further along. My background in math is pretty weak (at least pretty old), and what I've come up with has been from an approach involving visualization through brute force mathematical experimentation, not elegant math. Still, I like it, and maybe others will too. But I have no equations to share. Maybe some graphs later on.

Anything by Terry Tao is pretty excellent. If you know how to program a bit, consider checking out projecteuler.net. They have some pretty excellent problems that make you think carefully about primes, how to find them, patterns, etc...

Have fun! If you are intrigued by either of those resources, let me know - I have many more...

Thanks gents, the Terry Tao suggestion was helpful. He has published some recent work on the topic, although it seems his writings are a compilation of the concepts I've seen elsewhere.

The angle I'm working - and I've found one guy writing similar ideas in a blog, but not published in a peer reviewed place that I've found - is identifying patterns within groups of numbers up to X, where X is a multiple of consecutive primes (e.g. 2x3x5x7x11), and trying to exploit those patterns to easily identify all non-primes up to X (and by extension all primes).

I think this yields a more (far more?) efficient search approach than the sieve of Erathosthenes, although it's based on the same underlying principles. But maybe I'm kidding myself.

da-dum-dum-bump!

Shameless self-serving bump :-)

Anything with sieve like behavior is -basically- going to have the same computational complexity as any other sieve (if you really want to know, O(nlog(log(n))) most of the time). You might stand to make certain gains by optimizing your sieve for patterns (e.g., find primes of the form (6m +- 1)), but for the most part, the best way to optimize a sieve is recursively; that is, find primes in small sets of numbers (maybe 1-1000) and from there, use those to determine primes of larger sets (1-1000000). For truly large sets and numbers, there are a bunch of neat ways to compute primality, and they vary in strength. Miller-Rabin is usually very fast and pretty strong, but so are elliptic curves, although for the life of me I have no idea how to use those - might be worth a look though, if you're interested. You also might consider looking up tests that determine whether a number is "probably" prime, if speed is your concern. ;)

Amateur Mathematician wrote: Anything with sieve like behavior is -basically- going to have the same computational complexity as any other sieve

Maybe yes, maybe no, I guess is where I'm coming from.

The thing is, there are similar recursive patterns (like 6m +-1) for every value of X (as defined previously) and these are quite easy to find, using a fairly small number of calculations, if you already have the pattern for X-1.

... where for X=3 you get the (6m+-1) pattern. And the pattern is similarly symmetric for every value of X.

slakcerdom wrote:

google.com might help.

________________________________________

I got nothing.

I keep googling ".com" and it does not have anything to do with prime numbers.

What gives.

Frustrated.

arxiv is a good place to look.

in particular,

http://arxiv.org/list/math.NT/recent

Thanks all, some really excellent suggestions! It never ceases to amaze me what kind of gold nuggets you can dig up in this place if you look carefully.

In case any of the helpful contributors are interested, I've described the idea in some detail here, at one of the resources your suggestions led me to:

http://www.primegrid.com/forum_thread.php?id=2991

Jeez on that other board Rogue isn't a real patient person. He was helpful helpful helpful then SNAP.

Bugs and things wrote:Jeez on that other board Rogue isn't a real patient person. He was helpful helpful helpful then SNAP.

I think he's the malmo of PrimeGrid. ;-)

Weird... thread was at 42 posts buried on the 3rd or 4th page, then somehow got snipped down to 5 posts. I don't recall seeing anything particular objectionable (certainly not by LR standards anyway). Overzealous mod with too much time on their hands?

some random dude wrote:...snipped down BY 5 posts...

Yes, but you are not gravitating away from sieve like behavior, is what I am saying. These patterns are easy to derive, yes, but they possess the same computational cost to implement as sieving. As I said, you may make short-term gains, but in the big picture, the complexity of your algorithm is still something on the order of O(nlog(log(n))).

Out of curiosity, what is the size of the numbers you are dealing with?