The Straight Dope

Go Back   Straight Dope Message Board > Main > General Questions

Reply
 
Thread Tools Display Modes
  #1  
Old 08-12-2005, 12:27 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Ulam's Spiral: Has it been explained or not?

Regarding Ulam's Spiral: http://mathworld.wolfram.com/PrimeSpiral.html

OK, first off, yes, we've done this before. But I've yet to discern any concensus, and rather than resurrect the old thread, I'm asking the question again: has the effect been explained? There seem to be three schools of thought at work here:

A) There's no pattern here at all. A plot of random numbers with the same distribution could easily display the same amount of "structure" because humans are used to seeing structure in images whether said structure is really there or not.

B) The "pattern" is no big suprise. Many of the "lines" visible in the spiral satisfy some of Euler's prime-generating equations, so that's nothing new. We know that primes greater than 3 all take the form p = 6n - 1 or p = 6n + 1, which itself forces a certain kind of arrangement, but the fact that the lines in the spiral are broken and chaotic and that those irregularities can't be explained essentially mean that it's not a pattern (it's almost a pattern, but we already know there's "almost" a pattern to the primes).

C) The reasons for pattern have not yet been found.

Personally, I can't swallow explanation A. I think you could produce a hundred such comparable plots using random data and see nothing like the structure in the Ulam Spiral. Besides, the pattern becomes absolutely striking the more numbers one plots. To me, explanation A might work for the Bible Code, but not for this.

I realize that the structures in the spiral are largely artefacts of the graphing process, but I don't think that's significant. You can see similar effects when the spiral is constructed according to different rules. Which makes me wonder, is there some as-yet-unexplored graphing process, perhaps in three dimensions, that would reveal a truly unexpected and regular pattern?
Reply With Quote
Advertisements  
  #2  
Old 08-12-2005, 06:02 PM
kniz kniz is offline
Guest
 
Join Date: Mar 2001
Quote:
Originally Posted by Sequent
Which makes me wonder, is there some as-yet-unexplored graphing process, perhaps in three dimensions, that would reveal a truly unexpected and regular pattern?
How could anyone know facts about an as-yet-unexplore graphing process in three, four or more dimensions. Unexplored pretty much means unknown. IANA geek
Reply With Quote
  #3  
Old 08-12-2005, 06:17 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Quote:
Originally Posted by kniz
How could anyone know facts about an as-yet-unexplore graphing process in three, four or more dimensions. Unexplored pretty much means unknown. IANA geek
Unexplored in the context of this application; not unexplored as in Balboa staring at the Pacific. After all, Ulam came up with the thing doodling to pass the time during a boring lecture.
Reply With Quote
  #4  
Old 08-12-2005, 07:20 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Quote:
Originally Posted by Sequent
Personally, I can't swallow explanation A. I think you could produce a hundred such comparable plots using random data and see nothing like the structure in the Ulam Spiral. Besides, the pattern becomes absolutely striking the more numbers one plots. To me, explanation A might work for the Bible Code, but not for this.
A hundred? Please. Generate 1010100 and then we'll have a sample worth talking about. And I'd lay dollars to donuts that a few of them will have much more striking patterns.

The problem here is that humans are extremely poor judges of what's random and what's not. In a true random sequence, you will see patterns.
Reply With Quote
  #5  
Old 08-12-2005, 07:44 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Quote:
Originally Posted by ultrafilter
A hundred? Please. Generate 1010100 and then we'll have a sample worth talking about.
...and we'd be talking about it for quite a while, indeed. Many thousands of years, by my guess. Let's say we just did, oh, 1010, for starters. And lets be wildly optimistic and give ourselves one second to evaluate each one for patterns. Then we'll come back after the 317 years it would take to do that and compare notes.
Reply With Quote
  #6  
Old 08-12-2005, 08:01 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Quote:
Originally Posted by ultrafilter
The problem here is that humans are extremely poor judges of what's random and what's not. In a true random sequence, you will see patterns.
A true random sequence, then. I take it we'll only need one of those? You're right, humans are poor judges of lots of things. Could a computer do it?
Reply With Quote
  #7  
Old 08-12-2005, 08:13 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
not so unexplored

http://yoyo.cc.monash.edu.au/~bunyip/primes/index.html
Reply With Quote
  #8  
Old 08-12-2005, 08:19 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Quote:
Originally Posted by Sequent
A true random sequence, then. I take it we'll only need one of those? You're right, humans are poor judges of lots of things. Could a computer do it?
Nope. The statement "x is a random sequence" is in general undecidable.
Reply With Quote
  #9  
Old 08-12-2005, 08:22 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
The other thing you have to keep in mind is that, no matter how long you're looking at Ulam's spiral, you're only considering an insignificant portion of the sequence of prime numbers. It may well be that any appearance of order in the primes disappears above a certain number that we can't even reasonably talk about. I'd like as much anyone to be able to predict prime numbers, but until somebody proves that we can, I'm not seeing anything.
Reply With Quote
  #10  
Old 08-12-2005, 08:55 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
I guess one connection I'm not making is that in order for there to be a pattern, the pattern would have to predict all the primes perfectly. I'd love to be able to predict the primes, too, but better minds than mine have tried. That's a long way off from discerning a pattern. I mean, the twin primes are patterned. The whole p = 6n - 1 | p = 6n + 1 is a pattern. They're not perfect patterns, but they're certainly useful.

And why should any pattern have to hold at all? Why can't it change? We consider fractals to be mathematical patterns, right? But they don't hold...self-similar but always changing depending on the numbers you're talking about. I wouldn't even expect the pattern to hold beyond certain numbers we can talk about, because that's not what patterns in nature seem to do.

I mean, we already know this one doesn't hold. Zoomed in close, it looks like a spiral. The 400x400 representation looks like some kind of fuzzy grid to me. The striking image to which I linked in the OP (a better version here ), representing the first 262,000+ primes, displays a completely different, flower-like pattern. Obviously, this image must be scaled, but still...pretty cool. I've generated lots of random images and backgrounds, and I've never come across anything like that.
Reply With Quote
  #11  
Old 08-12-2005, 08:59 PM
wolf_meister wolf_meister is offline
Charter Member
 
Join Date: May 2003
Location: Where the owls say "Whom"
Posts: 5,376
I think that people try to find patterns where none actually exist, be it the Biblical Code, Bode's Law , the "face" on Mars and so on.
Reply With Quote
  #12  
Old 08-12-2005, 09:55 PM
Bryan Ekers Bryan Ekers is offline
Guest
 
Join Date: Nov 2000
As an experiment, and figuring there wasn't any point drawing a spiral on a table with even numbers in it since none of them (except 2) could be prime, I drew up a table starting at 3 and spiralling outward by twos, i.e. 5, 7, 9, etc. Then I identified the prime numbers, and you know what the pattern revealed?

SPOILER:
A guy with waaaaay too much time on his hands on a Friday night.
Reply With Quote
  #13  
Old 08-12-2005, 10:18 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Montreal, eh?
Reply With Quote
  #14  
Old 08-12-2005, 10:25 PM
Bryan Ekers Bryan Ekers is offline
Guest
 
Join Date: Nov 2000
Quote:
Originally Posted by Sequent
Montreal, eh?
If one wasn't raised to watch hockey or get blind drunk, this can actually be an occasionally boring town.
Reply With Quote
  #15  
Old 08-12-2005, 10:31 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Quote:
Originally Posted by Bryan Ekers
If one wasn't raised to watch hockey or get blind drunk, this can actually be an occasionally boring town.
Doh. Hockey, or beer. I keep hearing about what an awesome local music scene you guys have, too...
Reply With Quote
  #16  
Old 08-12-2005, 10:36 PM
Bryan Ekers Bryan Ekers is offline
Guest
 
Join Date: Nov 2000
Quote:
Originally Posted by Sequent
Doh. Hockey, or beer. I keep hearing about what an awesome local music scene you guys have, too...
Well, there wasn't a lot of youthful rebellion in my house, either. We were too lazy.
Reply With Quote
  #17  
Old 08-12-2005, 11:32 PM
wolf_meister wolf_meister is offline
Charter Member
 
Join Date: May 2003
Location: Where the owls say "Whom"
Posts: 5,376
I heard there was some youthful rebellion in Montreal. But the guy moved away.
Reply With Quote
  #18  
Old 08-13-2005, 11:27 AM
Mathochist Mathochist is offline
Member
 
Join Date: Feb 2004
Location: New Orleans, LA
Posts: 3,031
Quote:
Originally Posted by ultrafilter
A hundred? Please. Generate 1010100 and then we'll have a sample worth talking about. And I'd lay dollars to donuts that a few of them will have much more striking patterns.

The problem here is that humans are extremely poor judges of what's random and what's not. In a true random sequence, you will see patterns.
Also, please to note that that image appears on a website purporting to unseat mathematics in favor of Christianity. I call bullshit.

In fact, the density around a point distance r from the center should be on the order of r/ln(r), and that plot seems to go up faster that that with distance. Again: bullshit.
Reply With Quote
  #19  
Old 08-13-2005, 01:26 PM
kniz kniz is offline
Guest
 
Join Date: Mar 2001
Quote:
Originally Posted by Sequent
Unexplored in the context of this application; not unexplored as in Balboa staring at the Pacific. After all, Ulam came up with the thing doodling to pass the time during a boring lecture.
unexplored means something is undiscovered. Ulam was unknowingly exploring with his doodles and he discovered something new. You have asked for something that hasn't been discovered.

What I didn't suggest in my first post, but will suggest here is that the OP take out a piece of paper, grab a pencil and start doodling, preferably in three dimensions.
Reply With Quote
  #20  
Old 08-13-2005, 03:12 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Quote:
Originally Posted by kniz
unexplored means something is undiscovered. Ulam was unknowingly exploring with his doodles and he discovered something new. You have asked for something that hasn't been discovered.

What I didn't suggest in my first post, but will suggest here is that the OP take out a piece of paper, grab a pencil and start doodling, preferably in three dimensions.
Interesting. In your previous post, you say "unexplored" = "unknown." Here you mention that someone can "unknowingly explore." Now, you claim it means "undiscovered." So I guess "explored" means "discovered" then? I'll be delighted to take credit for having discovered the Ozarks. I think I'll rename them the Lowzarks, since they're decidedly unimpressive in terms of height.

Techincally, I wasn't asking for anything, certainly not facts concerning our as-yet-undiscovered, unknowable, or unexplored plotting method. I was simply wondering about one, if it's possible that one might exist. I wasn't asking you to give me one, friend. No, the actual solicitation for cold hard facts came at the beginning of the OP: has this been explained?

What I didn't suggest in my previous post, but will suggest here, is that you take out a dictionary and look up the word whose meaning you've quite nicely explored: nitpick. I guess you can claim to have discovered it, too.
Reply With Quote
  #21  
Old 08-13-2005, 03:25 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Quote:
Originally Posted by Mathochist
Also, please to note that that image appears on a website purporting to unseat mathematics in favor of Christianity. I call bullshit.

In fact, the density around a point distance r from the center should be on the order of r/ln(r), and that plot seems to go up faster that that with distance. Again: bullshit.
True dat. I was looking for a better source for the image, too. I found it on a site about math, though; indeed, one that was attempting to show that there wasn't anything remarkable about the pattern? "Ulam's Rose? Get a grip!" was how it described the image, I think.

Yes, I've got big problems with that image's source, too. The one-pixel-per-integer image is easy enough to recreate, but I don't know what scaling method was used for that one. I'd actually be interested to try to recreate it, though, to see if what I came up with was anywhere near as striking.
Reply With Quote
  #22  
Old 08-13-2005, 06:26 PM
Derleth Derleth is offline
Guest
 
Join Date: Apr 2000
Quote:
Originally Posted by Sequent
A true random sequence, then. I take it we'll only need one of those? You're right, humans are poor judges of lots of things. Could a computer do it?
Only with external help. There's no way to go from the deterministic (a computer plodding though a predefined series of steps) to the nondeterministic (a sequence of random numbers) without adding a nondeterministic element.

I'd also like to amplify ultrafilter's reply: There is no way to know a sequence of numbers is random unless you know the sequence's origin. And even if you do know the sequence came from something like a geiger counter turned towards a decaying hunk of metal, it still might not have the properties you want in a random sequence.

The thing to understand is that looking random has nothing to do with being random. The sequence '55555' could well come out of that geiger counter. If you are having a bad day when you try to generate a new cryptographic key, it could keep coming out until you think you have a good 2048-bit key. It is no more unlikely than any other specific sequence.

It is, however, part of a rare group of sequences. The vast majority of possible 2048-bit random numbers behave as expected when we apply standard statistical tests, which is why we have those tests at all. It's a crapshoot, but the odds of a sequence that pathological coming from a true hardware random-number generator are lower than shooting 20 7s in a row with unloaded dice.

My point being, of course, that you can't hold a sequence, even a large one, up to the light and say for sure if it's random or not. You aren't interested in that anyway, most of the time: What you want is a sequence that exhibits certain properties we can test for.
__________________
"Ridicule is the only weapon that can be used against unintelligible propositions. Ideas must be distinct before reason can act upon them."
If you don't stop to analyze the snot spray, you are missing that which is best in life. - Miller
I'm not sure why this is, but I actually find this idea grosser than cannibalism. - Excalibre, after reading one of my surefire million-seller business plans.
Reply With Quote
  #23  
Old 08-13-2005, 06:38 PM
Omphaloskeptic Omphaloskeptic is offline
Guest
 
Join Date: Oct 2001
Quote:
Originally Posted by Mathochist
In fact, the density around a point distance r from the center should be on the order of r/ln(r), and that plot seems to go up faster that that with distance.
I noticed that too (in fact, the density seems to vary nonmonotonically with the Manhattan distance from the center). My only guess (assuming the image ever was a real Ulam's spiral) is that at some point the image was rescaled and interpolated and "enhanced" somehow. Note that the claim (on the page that links to that image) is that the image is the spiral for the primes from 1 to 262144=218; so the image ought to be 512x512 pixels. Actually it's 771x751 (not even square!), so the primes aren't single pixels.

I created a 2000x2000 Ulam's spiral last night (200K PNG; if you want to look at it or host it somewhere I'll email it to you if you'd like), and indeed it looks nothing like that image (though it should contain the spiral in question). If you dither it (or look at it from far away) it looks like a fuzzy point in the center, very gradually dimming with distance (as Mathochist said, the prime density should be about 1/(2ln(r)) near the edge of a centered square of size r). To my eyes the diagonal lines are fairly obvious near the center but get somewhat less clear near the edges of this square (i.e., for primes ~4e6).

The integers along straight lines in the Ulam spiral are given by the values of quadratic equations f(x)=ax2+bx+c, for whole x (or by the union over several such equations). It's known that some such equations produce a lot of early primes (e.g. n2+n+41); these are the obvious lines near the center. These lines all start getting breaks after a while (it's known that no single-variable polynomial produces only prime values), though some do seem to have more primes than average all the way to the edges of my image. I don't know what is known about the asymptotic density of primes along such lines (i.e., whether any of these lines continue to have more primes than expected).
Reply With Quote
  #24  
Old 08-13-2005, 07:06 PM
kniz kniz is offline
Guest
 
Join Date: Mar 2001
Quote:
Originally Posted by Sequent
What I didn't suggest in my previous post, but will suggest here, is that you take out a dictionary and look up the word whose meaning you've quite nicely explored: nitpick. I guess you can claim to have discovered it, too.
I copied and pasted this from WordNet
Quote:
Overview of adj unexplored
The adj unexplored has 1 sense (first 1 from tagged texts)
1. (3) undiscovered, unexplored -- (not yet discovered; ``undiscovered islands'' )
I actually looked it up before I posted on [URL=http://dictionary.reference.com/search?r=66&q=unexplored]Dictionary.com
Quote:
unexplored

adj : not yet discovered; "undiscovered islands" [syn: undiscovered]
Reply With Quote
  #25  
Old 08-14-2005, 12:14 PM
Mathochist Mathochist is offline
Member
 
Join Date: Feb 2004
Location: New Orleans, LA
Posts: 3,031
I didn't bother looking at how many numbers they worked out, but at that few you should still see the primes fitting into a checkerboard. All the even numbers (but one) have to be composite.

Quote:
Originally Posted by Omphaloskeptic
the prime density should be about 1/(2ln(r)) near the edge of a centered square of size r)
Are you sure it's not r/ln(r)? I did a quick BotE before. If nothing else, this'll show people how this sort of stuff is really done.

Let the numbers be big enough to approximate by continua and all statements more about orders of magnitude than anything else.

number of numbers inside circle of radius r, thus less than the number at radius r
pi*r2

number of those that are prime
pi*r2/(ln(pi*r2))

take differential to find the number in an annulus of width dr
dr*2pi*r*(ln(pi*r2)-1)/ln(pi*r2)2

divide by area of annulus to get density
(ln(pi*r2)-1)/ln(pi*r2)2

at the relevant size of r, the "-1" term is swamped, so we ignore it and get
1/(ln(pi)+2ln(r))

and the ln(pi) is insignificant, so we're left with
1/2ln(r)

Yep, you're right. I wonder where I got that extra r...
Reply With Quote
  #26  
Old 08-14-2005, 01:48 PM
AHunter3 AHunter3 is offline
Charter Member
 
Join Date: Mar 1999
Location: NY (Manhattan) NY USA
Posts: 16,107
Why is an "explanation" needed? You're not graphing random numbers, you're graphing primes (or, more specifically, you're graphing the places that primes appear in the stream of integers). Why should it not form a pattern, simply because it does not form a simple cyclical/repetitive pattern? Anyone here ever read about chaos theory? Chaotic phenomena (i.e., phenomena not conforming to the kind of pattern that lets you predict the next occurrence) does tend to have patterns. Static in phone lines. Distribution of curves in shorelines. Etc. Old news at this point.
Reply With Quote
  #27  
Old 08-14-2005, 02:03 PM
AHunter3 AHunter3 is offline
Charter Member
 
Join Date: Mar 1999
Location: NY (Manhattan) NY USA
Posts: 16,107
Sorry, that came off more know-it-all than I have any right to be in a mathematics thread. If there's a reason why the existence of a pattern within such a graph of primes should still be surprising, feel free to tell me I'm an irrelevant kibitzer and move on.
Reply With Quote
  #28  
Old 08-14-2005, 03:19 PM
Mathochist Mathochist is offline
Member
 
Join Date: Feb 2004
Location: New Orleans, LA
Posts: 3,031
Quote:
Originally Posted by AHunter3
Sorry, that came off more know-it-all than I have any right to be in a mathematics thread. If there's a reason why the existence of a pattern within such a graph of primes should still be surprising, feel free to tell me I'm an irrelevant kibitzer and move on.
Done, and done.

Basically, prime numbers haven't yet yielded any predictable pattern in their distribution, other than the fact that there are roughly x/ln(x) of them less than x. If we knew a pattern, factoring would be a lot easier, among other things.

As for the whole "chaos" red herring, you fall into the (depressingly) standard pit of confounding chaos with disorder or randomness. Chaos is a jargon term, not a standard English word, and it refers to the sensitive dependance of the long-term behavior of a dynamical system on its initial conditions, among other things. Basically, prime distribution and chaos theory have a priori nothing to do with each other. That isn't to say there isn't a connection nobody's seen yet, but it's certainly not the obvious fact you call us short-sighted dolts out for not seeing.
Reply With Quote
  #29  
Old 08-14-2005, 08:53 PM
AHunter3 AHunter3 is offline
Charter Member
 
Join Date: Mar 1999
Location: NY (Manhattan) NY USA
Posts: 16,107
Predictable pattern <> pattern. Static on long-distance telephone lines doesn't follow any predictable pattern either, but if you graph the interval between one burst and the next against the interval between the latter and that one next to follow, you don't get a random smear of dots but rather patterns. Data points are said to be drawn to "strange attractors".

I am not telling you all this to educate you, I assume you know all this, and I'm just pointing to it to say "this stuff, this is what I was talking about".

I see no reason to assume that prime numbers, which are not being distributed in a predictable pattern, are therefore distributed at true random. So as it turns out there's a pattern (as the graph indicates), it's just a pattern akin to the pattern of waterdrop intervals from the chaotically dripping faucet and so forth.
Reply With Quote
  #30  
Old 08-14-2005, 09:54 PM
Mathochist Mathochist is offline
Member
 
Join Date: Feb 2004
Location: New Orleans, LA
Posts: 3,031
Quote:
Originally Posted by AHunter3
I see no reason to assume that prime numbers, which are not being distributed in a predictable pattern, are therefore distributed at true random. So as it turns out there's a pattern (as the graph indicates), it's just a pattern akin to the pattern of waterdrop intervals from the chaotically dripping faucet and so forth.
There's not even anything yet discovered as predictable as an attractor. Primes are not distributed by a dynamic map, so the analogy you're trying to draw is really not there. The notion of an attractor (which is, let's be honest, a lot more subtle than the idea you seem to have in your head) just doesn't apply the way you think it does. There's no motion so there's no attraction.

And besides, the entire notion of a "pattern" is that there's some amount of predictability. Not deterministic, maybe, but if there's no predictability at all there's no pattern.
Reply With Quote
  #31  
Old 08-15-2005, 12:14 AM
snailboy snailboy is offline
Guest
 
Join Date: Apr 2004
I can predict that the 1,000th prime number is an odd integer. Is that predictable enough for you? Perhaps not, but it's more than I can tell you about the 1,000th digit of pi.
Reply With Quote
  #32  
Old 08-15-2005, 01:21 AM
Omphaloskeptic Omphaloskeptic is offline
Guest
 
Join Date: Oct 2001
Quote:
Originally Posted by AHunter3
Why is an "explanation" needed? You're not graphing random numbers, you're graphing primes (or, more specifically, you're graphing the places that primes appear in the stream of integers). Why should it not form a pattern, simply because it does not form a simple cyclical/repetitive pattern? Anyone here ever read about chaos theory? Chaotic phenomena (i.e., phenomena not conforming to the kind of pattern that lets you predict the next occurrence) does tend to have patterns. Static in phone lines. Distribution of curves in shorelines. Etc. Old news at this point.
"Why is an explanation needed?" -- Well, because that's what mathematicians do: try to figure out why various mathematical structures exist. In this case in particular, mathematicians don't really know much about the distribution of primes, and they'd really like to know more. Some of the most famous unsolved mathematical conjectures involve primes: more specifically, primes and addition. Primes and prime factorizations, being defined multiplicatively, behave nicely under multiplication, but become very confusing when addition is involved. For example: Goldbach's conjecture (Every even number greater than 2 is the sum of two primes), the twin-primes conjecture (there exist an infinite number of prime pairs (p,p+2)), and the Riemann hypothesis (the nontrivial zeroes of the Riemann zeta function have real part 1/2--this is related in a somewhat subtle way to the distribution of primes) all are of this type.

Just calling this "chaos theory: old news" is too dismissive. The thing about chaos theory is that, although its name might suggest otherwise, it's really quite well understood. Once the governing equations of the system are known, they can be analyzed in a pretty straightforward way to see if the system is expected to be chaotic or not. For chaotic systems like the ones you mention above, there are dynamical models that predict the onset of chaotic behavior as various parameters are tweaked. (These can be more or less accurate depending on the fidelity of the underlying model, but we think we understand more or less why things become chaotic.)

But in this case we haven't got any good ideas what the underlying "dynamic" equations might look like. (Of course, the primes are not a dynamic system at all, but you might look at the sequence of primes, or the prime differences pn+1-pn, or maybe the prime differences divided by ln(n) to normalize out the obvious growth, and consider these to be samples from a Poincare section of some prime-namical system.) Without knowing what the equations are, there's no way to honestly call this a "chaotic" system, since we don't have any way of knowing whether what we're seeing is really the same lack of order as the lack of order seen in chaos.
Reply With Quote
  #33  
Old 08-15-2005, 11:28 AM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
I decided to recreate Omphaloskeptic's test, first with a 512x512 spiral and then a 2000x2000 spiral, not because I don't trust him, but just as an experiment so I could play around with the spiral on my own. (Call me a geek; I find this stuff fascinating). My results were quite similar to what he describes above: a small, dense "cloud" of points in the center surrounded by a diffusion of points which becomes less dense towards the edges. In short, nothing like the more flowerful picture to which I linked before.

And it does make sense, as Mathochist pointed out, the primes get less dense the higher one counts, so the dark lines in the "flower" image suggest clusterings of primes that simply are not there. Also, something I neglected to point out before, look at the center of the flower image: there's nothing there! Assuming the center represents the origin starting with 0 or one, there should be at least a dark cluster there representing all the early primes, but there's not.

Which gave me an idea: I tried a plot that "blotted" out the central cluster (a 50x50 square) on my plot (much like a weather radar eliminating ground clutter) in order to see if the outer diagonals that, as Omphaloskeptic notes, do seem to contain more primes than normal, were simply a function of my mind trying to extend the pattern it sees toward the center. The outer diagonals didn't stand out quite as much, but they're still definitely there. Still, nothing that makes you jump out of your seat.

Anyway, I'm only marginally interested in what the Christian Numerologists did to make the flower image; I mean, enough transforms and scaling and you could probably make the spiral look like Elvis, right? What I am interested in doing is extending the spiral out to a range where scaling would become necessary to view it as a 2000x2000 image.

So instead of showing the distribution of primes in the first 4 million numbers, the same size grid (2Kx2K) would show the primes in the first, say, 16 million numbers. In order to do that, we'd have a grid where 1 pixel represents 4 numbers instead of 1, yes? If we then made the image a 4-color greyscale instead of black, assigning the colors such that white = 0 primes.....black = 4 primes, would that make for an accurate representation, or am I completely off base?
Reply With Quote
  #34  
Old 08-15-2005, 11:49 AM
Mathochist Mathochist is offline
Member
 
Join Date: Feb 2004
Location: New Orleans, LA
Posts: 3,031
Quote:
Originally Posted by Sequent
Anyway, I'm only marginally interested in what the Christian Numerologists did to make the flower image; I mean, enough transforms and scaling and you could probably make the spiral look like Elvis, right?
Forget transforms and scaling. Occam's Razor tells you what they did: they lied. Plain and simple. Frankly, as would be the case with anyone else purporting to unseat the validity of mathematics, I'm entirely unsurprised.

Quote:
So instead of showing the distribution of primes in the first 4 million numbers, the same size grid (2Kx2K) would show the primes in the first, say, 16 million numbers. In order to do that, we'd have a grid where 1 pixel represents 4 numbers instead of 1, yes? If we then made the image a 4-color greyscale instead of black, assigning the colors such that white = 0 primes.....black = 4 primes, would that make for an accurate representation, or am I completely off base?
It could work. Two nits to pick, though. What you're suggesting would require five colors: 0, 1, 2, 3, and 4. On the other hand, three is all you really need, since in any 2x2 square at least two of the spaces can't be prime, since they represent even numbers.

So, call the colors w, g, and b for 0, 1, or 2 primes in the square. Up to 100, it looks like:

Code:
wgggw
bgwbg
wbbbg
bggww
bwggg
Reply With Quote
  #35  
Old 08-15-2005, 12:07 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Of course, five colors! The old off-by-one error. And yes, we'd be providing coverage for situations that couldn't possibly exists....it's just easier for me to think of it that way. Hardly nitpicks--those are valid points. A nitpick would be, say, me pointing out a subject-verb disagreement in your last post. :-)

And them Christians ain't supposed to bear false witness, neither.
Reply With Quote
  #36  
Old 08-15-2005, 12:20 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Quote:
Originally Posted by Mathochist
If we knew a pattern, factoring would be a lot easier, among other things.
I was thinking about this vis a vis the whole RSA thing: if we had a method for predicting the primes--let's say one that worked perfectly, always predicting the next prime accurately--factoring would be easier, but not so much easier that it wouldn't still be extremely difficult in some cases, right?

The only benefit I can think of right away is that trial division would become a lot faster if we could limit our trial divisors to numbers we could be sure were prime. Obviously, the discovery of such a pattern would probably lead to many other discoveries regarding the primes that might, in turn, make factoring much easier.

But aside from that, for the RSA thing...they could just keep choosing larger and larger keys, such that the set of possible prime divisors for a key--even if we had a way to know the contents of that set exactly--could still be so large as to make trial division impractical, right?
Reply With Quote
  #37  
Old 08-15-2005, 12:28 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Instead of having sqrt(n) trial divisors, you'd have roughly sqrt(n)/ln(sqrt(n)). You could still choose a large enough key that it would be difficult to factor by brute force, but it would become significantly less complex in a technical sense.
Reply With Quote
  #38  
Old 08-15-2005, 12:44 PM
Sequent Sequent is offline
Guest
 
Join Date: Jun 2000
Quote:
Originally Posted by ultrafilter
You could still choose a large enough key that it would be difficult to factor by brute force, but it would become significantly less complex in a technical sense.
How so? The process (trial division) hasn't changed--just the number of trial divisors? I mean, you could eliminate the need to check a trial divisor for primality, but other than that, how does it simplify things?
Reply With Quote
  #39  
Old 08-15-2005, 12:50 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Because there are asymptotically fewer trial divisors, as I mentioned in the first sentence of the post you quoted.
Reply With Quote
  #40  
Old 08-15-2005, 01:07 PM
The Controvert The Controvert is offline
Guest
 
Join Date: Sep 2001
Has anyone tried playing with the start parameter? How does shifting the spiral affect the patterns?
Reply With Quote
  #41  
Old 08-15-2005, 01:24 PM
Omphaloskeptic Omphaloskeptic is offline
Guest
 
Join Date: Oct 2001
Quote:
Originally Posted by ultrafilter
Instead of having sqrt(n) trial divisors, you'd have roughly sqrt(n)/ln(sqrt(n)). You could still choose a large enough key that it would be difficult to factor by brute force, but it would become significantly less complex in a technical sense.
Hmm. This would slightly speed up the naive O(sqrt(n)) algorithm, true, but not by enough to make it competitive with the best algorithms known. If all we can do is efficiently generate the primes in sequence, then it's not clear to me how that would substantially speed up algorithms like ECM which don't perform large numbers of trial divisions. (Primality testing is already polynomial, so it's not like the efficiency gain would be huge anyway.)
Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 08:52 AM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@chicagoreader.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Publishers - interested in subscribing to the Straight Dope?
Write to: sdsubscriptions@chicagoreader.com.

Copyright 2013 Sun-Times Media, LLC.