# Did you know this about prime numbers? **URL:** \ **Category:** Factual Questions\ **Created:** [February 28, 2003, 3:15pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140 "2003-02-28T15:15:59Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![The\_Flying\_Dutchman](https://avatars.discourse-cdn.com/v4/letter/t/9fc348/32.png) [@The\_Flying\_Dutchman](https://boards.straightdope.com/u/The_Flying_Dutchman)\ **Post date:** [March 1, 2003, 2:00am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/21 "2003-03-01T02:00:49Z")
> [@](#): > > \*Originally posted by buckyogi \* > \*\*The author of the following site: > > [http://fdonea.tripod.com/primes.htm](http://fdonea.tripod.com/primes.htm) > > says that, as far as he knows, _no one_ can “explain the occurance of straight lines in an otherwise apparently random pattern.” I’ll bet someone here can! I see nothing at all suggesting prime numbers as random. we have this rule that applies to all prime numbers "For each prime number p \> 3, there exists a natural number n such that p = 6n - 1 or p = 6n + 1. " Plug in any n, and most of the time you’ll get two primes, but you’ll always get at least one prime. ---
**Author:** ![bonzer](https://avatars.discourse-cdn.com/v4/letter/b/45deac/32.png) [@bonzer](https://boards.straightdope.com/u/bonzer)\ **Post date:** [March 1, 2003, 2:09am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/22 "2003-03-01T02:09:22Z")
If only for the sake of my sanity, can anybody come up with a specific cite for Ulam discovering it while “doodling during a boring lecture” ? I’m sure I’ve read a first-hand account by him of discovering this in just such circumstances, but I really don’t remember where. I’d have sworn it was in _Adventures of a Mathematician_, but, no, it doesn’t look as if that’s it. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 1, 2003, 2:14am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/23 "2003-03-01T02:14:03Z")
> [@](#): > > \*Originally posted by Hari Seldon \* > **And if anyone thinks a random collection of numbers with the same average distribution of primes will produce such patterns, I would sure like to see it.** While I can’t exhibit, there’s a whole field of study revolving around this sort of thing. It’s called Kolmogorov (or descriptive) complexity. One of the most striking results is that truly random sequences exhibit patterns, but not on any large enough scale. That’s why I don’t think that this diagram shows that the primes have some large-scale order, or that there’s any deep reason why those lines should exist. One of the basic results of Chaitin’s work (a related area called algorithmic information theory) is that in any theory, there are statements which are true for no reason. If I’m not mistaken, these correspond to Godel’s undecidable statements. This pattern may be analogous–it may exist at random. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [March 1, 2003, 2:45am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/24 "2003-03-01T02:45:15Z")
> [@](#): > > "For each prime number p \> 3, there exists a natural number n such that p = 6n - 1 or p = 6n + 1. " > > Plug in any n, and most of the time you’ll get two primes, but you’ll always get at least one prime. The first part of the quote is correct, but only because 6n, 6n+2, 6n+3, and 6n+4 are divisible by 2, 2, 3, and 2, respectively. All that’s left are numbers of the form 6n-1 and 6n+1. The second part of the quote is incorrect. Neither 6_20 + 1, nor 6_20 - 1 are prime. > [@](#): > > …can anybody come up with a specific cite for Ulam discovering it while “doodling during a boring lecture” ? My copy of _Archimedes’ Revenge_ by Paul Hoffman mentions that Ulam discovered it while doodling, but doesn’t mention anything about it happening during a boring lecture. As has already been mentioned, the “prime diagonals” correspond to “prime producing” quadratic polynomials, such as Euler’s. Apparently, it is understood why Euler’s polynomial produces so many primes, though I personally am not familiar with the theory behind it: > [@](#): > > Actually, it is known why Euler’s polynomial x^2 - x + 41 produces so many primes . Its discriminant is -163, which is the largest negative integer for which the associated quadratic number ring has unique factorization. Another curious fact, related to the same property, is that exp(pi\*sqrt(163)) is very nearly an integer; you need to calculate at least 31 significant figures to see that it isn’t, so on an ordinary pocket calculator it will look like an integer. [http://www.maproom.demon.co.uk/keeps.html](http://www.maproom.demon.co.uk/keeps.html) ---
**Author:** ![MysteryFellow63427](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@MysteryFellow63427](https://boards.straightdope.com/u/MysteryFellow63427)\ **Post date:** [March 1, 2003, 2:58am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/25 "2003-03-01T02:58:08Z")
What would a graph of the distance between prime numbers look like? That seems like it would be an interesting graph to look at. x:1 y: 1 (2-1) x:2 y: 1 (3-2) x:3 y: 2 (5-3) etc. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 1, 2003, 6:40pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/26 "2003-03-01T18:40:19Z")
> [@](#): > > \*Originally posted by neuroman \* > \*\*What would a graph of the distance between prime numbers look like? That seems like it would be an interesting graph to look at. > > x:1 y: 1 (2-1) > x:2 y: 1 (3-2) > x:3 y: 2 (5-3) > etc. \*\* The number of primes less than or equal to n is asymptotic to n/ln(n), so on the large scale, it would look a bit like the finite differences of that equation, which are roughly 1/2ln(n). ---
**Author:** ![Scott\_Dickerson](https://avatars.discourse-cdn.com/v4/letter/s/f04885/32.png) [@Scott\_Dickerson](https://boards.straightdope.com/u/Scott_Dickerson)\ **Post date:** [March 1, 2003, 11:15pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/27 "2003-03-01T23:15:53Z")
To bring forward a couple points that have been touched on, so as to emphasize them: (1) Prime numbers are not “random” in the strict sense. (I believe they are what is called “pseudo-random”.) Though there is no formula that will generate them in sequence, there certainly is a formula that will allow one to determine whether a given number is prime: namely the formula-ization of the “Sieve of Eratosthenes” (think of it as organized and efficient trial and error). (2) As the “lines” figure expands, it begins to resemble the outline of a flower–perhaps a poppy. I’m not joking! But it’s not a “clean” line-drawing, but something impressionistic embedded in a “haze” of nonincluded dots. The implication is that, whereas individual PNs are unpredictable, they do show a very definite tendency toward strong probabilistic “clustering.” I have read this described as “an underlying second- and third-degree order.” DOPERS–I would love to know if a similar “Ulam spiral” shows some kind of order to the decimal expansion of Pi! (There is no truth to the rumor that it shows as a visual image: YOG-SUTTHOTH WAS HERE!) ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 1, 2003, 11:22pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/28 "2003-03-01T23:22:49Z")
> [@](#): > > \*Originally posted by Scott Dickerson \* > **DOPERS–I would love to know if a similar “Ulam spiral” shows some kind of order to the decimal expansion of Pi!** Sounds interesting; I’ll give it a go How about I do it on a proper spiral with each digit 0-9 being represented by a corresponding shade of grey? ---
**Author:** ![Q.E.D](https://avatars.discourse-cdn.com/v4/letter/q/51bf81/32.png) [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)\ **Post date:** [March 1, 2003, 11:28pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/29 "2003-03-01T23:28:20Z")
Sounds interesting, **Mangetout**. I was thinking it would be interesting to do ten different plots, one for each digit 0-9 to better see the distribution of each digit. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 2, 2003, 12:01am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/30 "2003-03-02T00:01:07Z")
Sure; it’s all doable. trouble is with a regular spiral plot is that the spacing of the points is going to make a big difference; [this](http://www.numberspiral.com/) page has one method (for primes), but I think I’ll have to play around a bit with the pi thing. ---
**Author:** ![PurplePerson](https://avatars.discourse-cdn.com/v4/letter/p/ec9cab/32.png) [@PurplePerson](https://boards.straightdope.com/u/PurplePerson)\ **Post date:** [March 2, 2003, 12:21am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/31 "2003-03-02T00:21:16Z")
I am going to doodle a chart of prime numbers tonight while I watch tv and find out what it looks like. Being a bit obsessive compulsive, I only listen to tv volumes that are prime numbers. I might as well use that compulsion for a good use. I’ll tell you what I find. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 2, 2003, 12:24am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/32 "2003-03-02T00:24:41Z")
> [@](#): > > \*Originally posted by Scott Dickerson \* > **(1) Prime numbers are not “random” in the strict sense. (I believe they are what is called “pseudo-random”.) Though there is no formula that will generate them in sequence, there certainly is a formula that will allow one to determine whether a given number is prime: namely the formula-ization of the “Sieve of Eratosthenes” (think of it as organized and efficient trial and error).** Not quite true. Here’s an algorithm which, if left to run forever, will eventually output every prime number, and no others: (1) Start with n = 2. (2) Divide n by every natural number k \< sqrt(n). (3) If any k divides n, go to (5). (4) Output n. (5) Increment n and go to (2). “pseudorandom” refers to something completely different. ---
**Author:** ![Q.E.D](https://avatars.discourse-cdn.com/v4/letter/q/51bf81/32.png) [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)\ **Post date:** [March 2, 2003, 12:31am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/33 "2003-03-02T00:31:31Z")
Almost, **ultrafilter**. Step (2) should be: Divide n by every natural number 2 \> k \< sqrt(n). Otherwise division by 1 will pass every number. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 2, 2003, 12:36am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/34 "2003-03-02T00:36:29Z")
Once you have tested for division by 2, you only need to test for division by the odd numbers less than sqrt(n) ---
**Author:** ![Q.E.D](https://avatars.discourse-cdn.com/v4/letter/q/51bf81/32.png) [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)\ **Post date:** [March 2, 2003, 12:39am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/35 "2003-03-02T00:39:17Z")
If we keep this up, we’ll have an O(log n) solution in no time 😃 ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 2, 2003, 5:54pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/36 "2003-03-02T17:54:23Z")
I knew all that…no, really. 😃 Good points. ---
**Author:** ![KarmaComa](https://avatars.discourse-cdn.com/v4/letter/k/e36b37/32.png) [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)\ **Post date:** [March 2, 2003, 7:14pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/37 "2003-03-02T19:14:33Z")
I see a disconcerting lack of faith in the Riemann Hypothesis here 😃 ---
**Author:** ![PurplePerson](https://avatars.discourse-cdn.com/v4/letter/p/ec9cab/32.png) [@PurplePerson](https://boards.straightdope.com/u/PurplePerson)\ **Post date:** [March 2, 2003, 7:23pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/38 "2003-03-02T19:23:36Z")
I am ignorant about higher Math, but have an aptitude and curiosity about it. When I sat and wrote out prime numbers the other night, there is a definite pattern to it. There always seems to come a point where there are 2 prime numbers only separated by one other number. For example 29 and 31. Most prime numbers stick out like a sore thumb to me. Obvious are the ones divisible by 2, 3 or 5. I am glad you are having this discussion. ---
**Author:** ![KarmaComa](https://avatars.discourse-cdn.com/v4/letter/k/e36b37/32.png) [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)\ **Post date:** [March 2, 2003, 7:26pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/39 "2003-03-02T19:26:52Z")
Do a web search on “twin primes”… an interesting subset of the whole prime number deal. ---
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [March 2, 2003, 7:28pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/40 "2003-03-02T19:28:59Z")
Well, I couldn’t avoid playing with this stuff. [Here are some of my results.](http://members.aol.com/stranglerw/primes/) (And, of course, step 2 should read “Divide n by every prime number k \< sqrt(n),” since they’ve already been determined by the time you need 'em for this step.) [Previous page](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140.md?page=1) [Next page](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140.md?page=3)