Remember Me?

 Straight Dope Message Board Remember Me?

 Thread Tools Display Modes
#1
08-12-2005, 01:27 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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?
#2
08-12-2005, 07:02 PM
 kniz Guest Join Date: Mar 2001 Location: Pratts, Mississippi Posts: 6,246
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
#3
08-12-2005, 07:17 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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.
#4
08-12-2005, 08:20 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
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.
#5
08-12-2005, 08:44 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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.
#6
08-12-2005, 09:01 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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?
#7
08-12-2005, 09:13 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
not so unexplored

#8
08-12-2005, 09:19 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
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.
#9
08-12-2005, 09:22 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
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.
#10
08-12-2005, 09:55 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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.
#11
08-12-2005, 09:59 PM
 wolf_meister Guest Join Date: May 2003 Location: Where the owls say "Whom" Posts: 5,484
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.
#12
08-12-2005, 10:55 PM
 Bryan Ekers Guest Join Date: Nov 2000 Location: Montreal, QC Posts: 56,016
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.
#13
08-12-2005, 11:18 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
Montreal, eh?
#14
08-12-2005, 11:25 PM
 Bryan Ekers Guest Join Date: Nov 2000 Location: Montreal, QC Posts: 56,016
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.
#15
08-12-2005, 11:31 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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...
#16
08-12-2005, 11:36 PM
 Bryan Ekers Guest Join Date: Nov 2000 Location: Montreal, QC Posts: 56,016
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.
#17
08-13-2005, 12:32 AM
 wolf_meister Guest Join Date: May 2003 Location: Where the owls say "Whom" Posts: 5,484
I heard there was some youthful rebellion in Montreal. But the guy moved away.
#18
08-13-2005, 12:27 PM
 Mathochist 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.
#19
08-13-2005, 02:26 PM
 kniz Guest Join Date: Mar 2001 Location: Pratts, Mississippi Posts: 6,246
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.
#20
08-13-2005, 04:12 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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.
#21
08-13-2005, 04:25 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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.
#22
08-13-2005, 07:26 PM
 Derleth Guest Join Date: Apr 2000 Location: Missoula, Montana, USA Posts: 19,827
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.
#23
08-13-2005, 07:38 PM
 Omphaloskeptic Guest Join Date: Oct 2001 Posts: 1,263
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).
#24
08-13-2005, 08:06 PM
 kniz Guest Join Date: Mar 2001 Location: Pratts, Mississippi Posts: 6,246
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]
#25
08-14-2005, 01:14 PM
 Mathochist 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...
#26
08-14-2005, 02:48 PM
 AHunter3 Charter Member Join Date: Mar 1999 Location: NY (Manhattan) NY USA Posts: 19,120
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.
#27
08-14-2005, 03:03 PM
 AHunter3 Charter Member Join Date: Mar 1999 Location: NY (Manhattan) NY USA Posts: 19,120
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.
#28
08-14-2005, 04:19 PM
 Mathochist 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.
#29
08-14-2005, 09:53 PM
 AHunter3 Charter Member Join Date: Mar 1999 Location: NY (Manhattan) NY USA Posts: 19,120
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.
#30
08-14-2005, 10:54 PM
 Mathochist 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.
#31
08-15-2005, 01:14 AM
 snailboy Guest Join Date: Apr 2004 Location: Dallas, TX Posts: 1,573
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.
#32
08-15-2005, 02:21 AM
 Omphaloskeptic Guest Join Date: Oct 2001 Posts: 1,263
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.
#33
08-15-2005, 12:28 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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?
#34
08-15-2005, 12:49 PM
 Mathochist 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```
#35
08-15-2005, 01:07 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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.
#36
08-15-2005, 01:20 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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?
#37
08-15-2005, 01:28 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
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.
#38
08-15-2005, 01:44 PM
 Sequent Guest Join Date: Jun 2000 Location: Savannah, Georgia Posts: 658
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?
#39
08-15-2005, 01:50 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
Because there are asymptotically fewer trial divisors, as I mentioned in the first sentence of the post you quoted.
#40
08-15-2005, 02:07 PM
 The Controvert Guest Join Date: Sep 2001 Location: Austin, TX Posts: 3,757
Has anyone tried playing with the start parameter? How does shifting the spiral affect the patterns?
#41
08-15-2005, 02:24 PM
 Omphaloskeptic Guest Join Date: Oct 2001 Posts: 1,263
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.)

 Bookmarks

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     General Questions     Great Debates     Elections     Cafe Society     The Game Room     Thread Games     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit

All times are GMT -5. The time now is 09:44 PM.

 -- Straight Dope v3.7.3 -- Sultantheme's Responsive vB3-blue Contact Us - Straight Dope Homepage - Archive - Top
Copyright ©2000 - 2017, vBulletin Solutions, Inc.

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