# 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:** 3
**Author:** ![yabob](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/yabob/32/2821_2.png) [@yabob](https://boards.straightdope.com/u/yabob)\ **Post date:** [March 2, 2003, 8:00pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/41 "2003-03-02T20:00:54Z")
> [@](#): > > \*Originally posted by Mangetout \* > \*\*Once you have tested for division by 2, you only need to test for division by the odd numbers less than sqrt(n) \*\* By extension, once you have tested explicitly for 2 and 3, you only need check division by numbers congruent to 1 or 5 modulo 6, which you can do by incrementing two candidate divisors by 6 at each loop iteration. I implemented “isPrime()” / “nextPrime()” routines this way once - it’s a good bit more efficient than simply eliminating all the even candidates, skipping over 9, 15, etc. By further extension, after checking 2, 3 and 5 one could use 8 candidates modulo 30 (congruent to 1, 7, 11, 13, 17, 19, 23, 29), but you start getting rather diminished returns for the added complexity. ---
**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, 8:50pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/42 "2003-03-02T20:50:42Z")
I read up on the twin primes. This is very interesting. I am learning much from all of you. ---
**Author:** ![dtilque](https://avatars.discourse-cdn.com/v4/letter/d/d6d6ee/32.png) [@dtilque](https://boards.straightdope.com/u/dtilque)\ **Post date:** [March 2, 2003, 11:35pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/43 "2003-03-02T23:35:25Z")
> [@](#): > > \*Originally posted by yabob \* > By further extension, after checking 2, 3 and 5 one could use 8 candidates modulo 30 (congruent to 1, 7, 11, 13, 17, 19, 23, 29), but you start getting rather diminished returns for the added complexity. Year ago, I had the idea that it might be significant to categorize the integers \> 1 based on how many factors were in their prime factorizations. No doubt someone else has had the same idea, but I never checked the literature. But what I realized was that the longest contiguous sequence with n prime factors would be 2[sup]n[/sup]-1, with the special exception of the 2,3 sequence for the primes. So I wrote a program to try to find the lowest such sequences for each n. I’ve put the results away, so I can’t give you them in detail, but for n=2 the first sequence is 33,34,35 and for n=3 it’s in the 200,000s. I didn’t find the sequence for any larger n. The thing is, I wrote the program on an original Mac (I said this was years ago) and because it was so slow at division, I optimized it by creating a modulo counter for each prime number below about 1000, I think. Plus counters for the powers of the low primes. By incrementing all the counters every time I incremented the number, I kept track of the modulo of the number for all those primes. Once the modulo counter reached the prime it was for, that prime was a factor in the number and the counter was reset. This may seem like a lot of work, but it actually made the program run faster. Of course, I was completely factoring all numbers, which is even more division-intensive than just finding primes. ---
**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, 11:46pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/44 "2003-03-02T23:46:36Z")
Well, I’ve done a little playing with the first ten thousand digits of pi and The _visual_ pattern of occurrence of some digits does seem to be more ordered than the occurence of the same digit in pseudo-random sequence, but it’s a little too early to decide if that is just coincidence or (more likely) wishful thinking… ---
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [March 3, 2003, 12:40am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/45 "2003-03-03T00:40:11Z")
**Mangetout** , what’s a good algorithm or source (online, preferrably) for the digits of pi? Given 65,536 of 'em, I can run them through the stuff I worked up last night, instead of the primes (see link above). That program creates the histograms and all automagically, so it’d be easy enough to just hand it a different input. ---
**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 3, 2003, 12:45am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/46 "2003-03-03T00:45:08Z")
[Here](http://www.escape.com/~paulg53/math/pi/links.html) is some good pi stuff, **DaveW** , including algorithms. ---
**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 3, 2003, 12:49am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/47 "2003-03-03T00:49:21Z")
Or not. Most of those links seem dead. [Here](http://mathforum.org/library/drmath/view/58286.html) is a better page with pi formulae. Yes, I checked this one. ---
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [March 3, 2003, 2:02am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/48 "2003-03-03T02:02:52Z")
Yeah, like I’ve got a math package that’ll handle those formulae out to 65536 decimal places, **Q.E.D.** 🙂 Actually, I looked at your previous offering, and did eventually find a page with [the first million digits](http://www2.tripnet.se/~nlg/pi0001.htm) on it, so not all the links were dead. This should work fine. Dunno if I’ll have a page with pi spirals up tonight, but I’ll try. ---
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [March 3, 2003, 4:49am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/49 "2003-03-03T04:49:30Z")
Okay, [here’s what I’ve done with pi so far](http://members.aol.com/stranglerw/primes/pi_index.html). ---
**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 3, 2003, 4:57am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/50 "2003-03-03T04:57:59Z")
Cool stuff, **Dave**. Good job with it. ---
**Author:** ![Enola\_Straight](https://avatars.discourse-cdn.com/v4/letter/e/dec6dc/32.png) [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)\ **Post date:** [March 3, 2003, 6:22am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/51 "2003-03-03T06:22:44Z")
Okay, I’ve seen the circular and square Ulam spirals, but how do triangular and hexagonal spirals look? Also, what would a prime distribution appear if expressed in 3 dimensions, instead of just a 2-D spiral? ---
**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 3, 2003, 2:44pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/52 "2003-03-03T14:44:41Z")
I wonder if **Dave** wants to do the same thing with [_e_](http://mathforum.org/dr.math/faq/faq.e.html)? My guess is the distribution would be similar to that of _pi_. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 3, 2003, 3:34pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/53 "2003-03-03T15:34:06Z")
Nuts. I typed up a long post last night, but it didn’t go through. Here’s the abridged version: Everything you’ve done so far has been really cool, Dave. You mentioned some strange property of the random dots you generated, and said it might just be bad luck–I think that’s probably right. Some other spirals that might be interesting: even and odd digits of pi, primes mod 4, primes mod 6. If you get a chance. ---
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [March 3, 2003, 9:02pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/54 "2003-03-03T21:02:26Z")
Wow. Thanks, folks. A lot. I thought I might get a “neat-o,” but I never imagined a “cool,” and definitely not a “really cool.” 🙂 Actually, what I really expected was for someone to say, “Hey, Dave, that looks just like what’s over on (insert URL of web site here).” I really can’t imagine that I’ve done anything that hasn’t been done before. Images like mine have gotta be out there, somewhere. (Perhaps in print?) Obviously, the Ulam spiral itself ain’t new, but I did histograms of differences between primes over 10 years ago (with millions of primes, not just thousands - 6 was still #1), and my dad, at the time, pointed out that that had been done ages before then. “Pi as an Ulam Spiral” sounds far too much like an undergrad thesis title for it _not_ to have been one already (several times), right? Anyway, e should be a snap (_if_ there’s a web site with the first million digits of it out there, too), now that all the routines for pi are in place and working (and I wouldn’t expect to see much of a difference). Even/odd digits of pi shouldn’t be too tough, either. And primes mod 4 or 6 shouldn’t be too much work. I just realized, though, thinking about the code I’ve written, that both of my linearity-calculating routines are missing some of the visually-linear dots. So all of the scores are low. By how much, I can’t guess, but they should all be higher (and probably porportionally, so it won’t make a difference to the _meaning_ of what’s up there already - it’s not going to raise the score of the random image more than it raises the score of the primes image). And yeah, I’ve gotta work on re-running a bunch of random images (using the randomizer from the pi routines) to see if the one on my web page now was just a fluke. I’m also thinking about going to a 1,000x1,000 spiral, to get the most out of that web page with the first million digits of pi on it, and I’ve re-written a quick-and-dirty prime-finder which has, in the last two hours, already stored the first 20 million primes (overkill, I know, but I’m going to let it go until it’s covered all primes in 32 bits or less - and I’m curious about the final histogram of all that, anyway). My code right now spits out these spirals and histograms in about a second per, so going to a million digits/primes should only slow it down to 15 seconds per (if the speed is linearly related to the number of dots - not sure about that). On second thought, going to a million digits/primes would require me to not have the big (and prettier) images (the ones which show each dot as four pixels instead of one), since 2,000x2,000 pixel bitmaps would be unweildy in a web browser (I figure lots of people have their displays at 1,024x768, anyway). Any thoughts? Er… Any thoughts other than the obvious “do a 65,536x65,536 Ulam spiral with all those primes!” A 4-gigabyte bitmap file? I don’t think so, no. 🙂 ---
**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 3, 2003, 9:09pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/55 "2003-03-03T21:09:35Z")
If you didn’t notice, **Dave** the _e_ in my post is a link to formulae for generating it to arbitrary precision. 😉 ---
**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 3, 2003, 9:17pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/56 "2003-03-03T21:17:39Z")
Good work **DaveW**. I’ve been working on the pi thing and I thought I’d play around with making the spacing of each point on the spiral path proportional to the sqrt of the index, but it makes very little difference to the final appearance. ---
**Author:** ![Lenny](https://avatars.discourse-cdn.com/v4/letter/l/ba8739/32.png) [@Lenny](https://boards.straightdope.com/u/Lenny)\ **Post date:** [March 3, 2003, 11:48pm UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/57 "2003-03-03T23:48:10Z")
Long time listener, first time caller here. There are no true patterns here. If there were “true patterns”, the gaps in the imagined “lines” could be explained. They can’t. No explanation? No patterns. Know explanation, know patterns. ---
**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 4, 2003, 12:15am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/58 "2003-03-04T00:15:25Z")
the gaps in the lines _can be explained_ - as an artifact of the plottting method, the lines represent equations such as Euler’s formula; if we were to plot the entire set of results from Euler’s, we would see unbroken lines, but Euler’s only produces a _high proportion_ of primes and it is only these we are plotting; the gaps are the non-prime results of the formulae. Know great mystery. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 4, 2003, 12:22am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/59 "2003-03-04T00:22:36Z")
> [@](#): > > \*Originally posted by Lenny \* > \*\*Long time listener, first time caller here. > > There are no true patterns here. If there were “true patterns”, the gaps in the imagined “lines” could be explained. They can’t. No explanation? No patterns. > Know explanation, know patterns. \*\* If somebody comes up with an explanation, will there be a pattern? ---
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [March 4, 2003, 12:48am UTC](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140/60 "2003-03-04T00:48:27Z")
Yes, **Q.E.D.** , I did notice – but the same difficulty applies here as it did with pi. At least, I didn’t notice that any of the formulae could be continued past the precision of the math packages I have to work with (namely, what Visual C++ provides). So I can get e out to a handful of decimal places using what I’ve got, as far as I can tell. 80 bits’ worth, I believe. Now I’ve played around with creating an arbitrary-precision floating-point package, myself, in order to have easy access not only to the far-right decimals, but also to huge integers, but I always seem to wind up getting bogged down on some point, and ditching the project for something else. While I once created a huge-integer package for looking for a subset of big prime numbers (thousands of digits was all I tested it with, but it could go as high as you could afford memory), it was too specialized to be generalized. Through the links provided on that e page, I did locate [the first 10,000 digits](http://www-history.mcs.st-and.ac.uk/HistTopics/e_10000.html), but that’s too few for my tastes. [Previous page](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140.md?page=2) [Next page](https://boards.straightdope.com/t/did-you-know-this-about-prime-numbers/158140.md?page=4)